计算具有非常大和非常小的特征值的密集非对称 100x100 矩阵的行列式

计算科学 线性代数 本征系统 稀疏矩阵 精确 密集矩阵
2021-12-02 13:32:18

我的问题的动机如下:在 Project Euler 问题之一中,需要计算尺寸为 100x500 的矩形网格图的生成树。根据矩阵树定理,这个数等于通过取图拉普拉斯算子并删除其第一行和第一列而获得的矩阵的行列式。拉普拉斯算子非常稀疏且正定,但它是一个 50000x50000 矩阵,在我看来,以所需的精度计算行列式是不可行的(指数符号中的 5 个有效数字:我可能错了吗?)。

我发现了以下有趣的参考

http://arXiv.org/abs/0712.0681v3

它允许将行列式计算为 100x100 矩阵的行列式,该矩阵作为 500 个 200x200 稀疏矩阵的乘积的左上角,使用拉普拉斯算子是块三对角的事实(并从拉普拉斯算子派生出一个非奇异的 50000x50000 矩阵,其行列式是等于删除了第一行和第一列的拉普拉斯算子的行列式),这似乎是一件好事。然而,生成的真实 100x100 矩阵是非对称的、密集的,有一些非常大的条目和一些非常小的 (e^(- ...)) 特征值(我尝试了更小的网格)。由于特征值非常小,如果我不保留矩阵条目的所有数字,我不确定任何数值方法(高斯消元、SVD 等)是否能正常工作。

我的问题是:有没有人知道在这种情况下可以使用一种实用的方法来计算具有所需精度的行列式(再次,指数符号中的 5 个有效数字)?

我以三角项乘积的形式知道原始欧拉计划问题的答案,所以我真正感兴趣的不是解决方案本身,而是当我尝试直接应用矩阵树定理时自然出现的这些线性代数问题.

4个回答

整数值矩阵行列式的计算一直是大量研究的主题。使用精确算术可以计算史密斯范式,并且从这个对角线形式很容易找到行列式。

Saunders 和 Wan (2004), Smith Normal Form of Dense Integer Matrices, Fast Algorithms into Practice说:“在过去的三十年里,Smith 形式的算法取得了稳步进展。” 他们为渐近最快的已知方法(但“可能不实用”)提供了参考,然后深入探讨了 W. Eberly、M. Giesbrecht 和 G. Villard 对算法的改进细节。

本质上,一个人想要找到矩阵条目的最大公约数,通过一系列行和列操作形成它,并使用它来消除其列中的所有其他非零条目。


这个未回答的关于计算整数矩阵行列式(大致与您询问的大小)的“最快方法”的Math.SE 问题吸引了一些好的评论,其中一个建议(并报告了成功的 100x100 实验) Maple 的行列式函数使用方法= 整数尽管他们的算法使用(精确的)模运算,但它需要一个概率元素(给出错误答案的可能性很小但积极)。这样做的原因是,计算是针对一系列素数进行的,从而降低了每次特定运行所需的精度,并且在没有达到行列式的先验界限(使答案具有确定性)的情况下,“收敛”可能是通过在几次这样的运行后获得相同的结果来决定(概率情况)。

维基百科实际上对方法有一个很好的概述: http ://en.wikipedia.org/wiki/Determinant#Calculation 作为一般评论,人们不计算大矩阵的行列式(大矩阵的大小> 10或> 50)因为这在数值上很困难,而且很可能无论如何都不是很稳定。如果你需要这样做,我会看看是否有随机算法,就像你可以使用蒙特卡洛方法来近似跟踪一样。

我一直在使用 pari/gp(配置显示在下面的输出中)来计算大型密集矩阵的行列式。例如,我在 Linux 笔记本电脑上使用四核 i7、16GB RAM、32GB 交换空间来计算 1700x1700 的矩阵,精度略低于 3000 位。这需要大约 17 个小时,使用所有八个线程,100% 的时间,但只有一点 RAM。然后,它在另外六个小时内执行行列式,一个核心使用 100% 的行列式,而 kswapd 使用另一个核心,100% 的时间(并且似乎能够跟上并使用所有交换空间)。行列式在 pari/gp 中没有并行化(据我所知,除了 kswapd 和 gp 实例使用单独的内核)。这是一个具体示例(不使用并行代码),计算随机(浮点),1000 位精度,

我知道这不是 matlab,但在我看来,这是一种更好的方法。

=========================== cut here
default(nbthreads,2); \\this example sets up two but uses only one thread.
default(threadsize,  500 000 000);
default(parisize,  1 800 000 000); \\ make sure there is enough RAM allocated

initrand()=
{
  cmd = "date +\"%s\"";           \\ a linux command to get the time
  seed = eval(externstr(cmd)[1]); \\ evaluate the external command
  setrand(seed);                  \\ set the random seed in pari/gp
  print ("Random Number Seed = ", seed); \\ this is what it is
  return(seed);                   \\ don't really use this value any more
}
{
  default(realprecision, 1000);  \\ accurate to 1000 digits of precision
  initrand();                    \\ pari/gp seems to need a different seed every time
  M = matrix(300,300,i,j,random(1.0)); \\ some small random matrix
  printf ("%10.7f\n", M[1,1]);   \\ print the first matrix element
  detM = matdet(M);              \\ calculate the determinant
  print (detM);                  \\ print the result of the determinant
  quit(); 
}
========================================= cut here

这是输出,在这台使用了八年的笔记本电脑(双核,2GB 内存,不是快速的 ThinkPad)上花了一分钟左右的时间。

                        GP/PARI CALCULATOR Version 2.7.3 (released)
                amd64 running linux (x86-64/GMP-6.0.0 kernel) 64-bit version
             compiled: Mar 20 2015, gcc version 4.8.2 (Ubuntu 4.8.2-19ubuntu1) 
                                 threading engine: pthread
                       (readline v6.3 enabled, extended help enabled)

                           Copyright (C) 2000-2015 The PARI Group

PARI/GP is free software, covered by the GNU General Public License, and comes WITHOUT ANY WARRANTY WHATSOEVER.

Type ? for help, \q to quit.
Type ?12 for how to get moral (and possibly technical) support.

 parisize = 8000000, primelimit = 500000
   ***   Warning: new stack size = 1800000000 (1716.614 Mbytes).
 Random Number Seed = 1442728837
 0.1458753
 -34107869659292788498041296259204073212856192996487539539650250444333175626443030051167504275069295850290060165906721403518710248631573270877318755.16606345550957294257524953917496320048631959234301670865079024142295995123023952749154306602088800645390346232704746782547685913565513791084278569243333238872632785910522536912572116356801097060790810716175151647494785903522152367435398630683566431045727806979724702836066399155098909578586486867501579225868835988817237083450602429253202805656099228929576538193846647490928888795367874033893827126923874835063405546089363260880884557106553366031910609740691344849673406340416580053579023527252144631532815837507760281113528779522639792441184911588021824240226126036961995649658869925314847019638680109421905217088024624421267647700950443089481208575217193882687232501653341331383260930401032570115570957029275695235564734394098177016567882258012726222978777317463869837697774536180341558237759707887932943904115121644125119662351721076540409972736105729
Goodbye!

当然,在这种情况下,“-341......05729”是浮点结果。我没有玩过整数矩阵元素,但我确信它同样好,如果不是更好的话。

整数矩阵库提供了一个C函数mDeterminant (const FiniteField p, Double *A, const long n)来计算det(A) mod p整数矩阵的行列式A使用行梯形变换),这可能很有用。