如何找到大矩阵的行列式

Question

我找到了一些用于查找矩阵行列式的C++代码,用于4x4到8x8.它工作正常,但我的项目需要18x18或更多的矩阵,而且代码太慢.代码是递归的,但递归是处理18x18矩阵的正确概念吗？我怎么能找到决定因素？

Answer 1

我假设你正在使用扩展拉普拉斯公式的天真方法.如果你想获得速度,你可以使用LU分解(分成两个低对角线和高对角线矩阵)来分解矩阵,你可以通过改进的Gauss-Jordan消除来实现,然后将行列式计算为:M2*n^3/3 FLOPS

det(M) = det(L) * det(U)对于三角矩阵而言,它只是对角线中条目的乘积.

这个过程仍然会比O(n!).

编辑:你也可以使用广泛实现的Crout方法.

Answer 2

好吧,我们在这个领域工作的人并不是很多人会认为18x18是一个大矩阵,几乎任何你选择的技术都应该在任何现代计算机上足够快.我们很多人也不会用递归算法来处理矩阵问题,更有可能使用迭代算法 - 但这可能反映了许多研究矩阵问题的人是科学家和工程师而不是计算机科学家.

我建议你看一下C++中的Numerical Recipes.不一定是你能找到的最好的代码,但它是一个学习和学习的文本.为了获得更好的代码,BOOST具有良好的声誉,并且总是有BLAS以及Intel Maths Kernel Library或AMD Core Maths Library等.我认为所有这些都具有行列式查找例程的实现,它将非常快速地处理18x18矩阵.