How to find determinant of large matrix

Question

I found some C++ code for finding the determinant of matrix, for 4x4 to 8x8. It works ok, but my project needs matrices that are 18x18 or more, and the code is too slow. The code is recursive, but is recursion the right concept to deal with an 18x18 matrix? How else can I find the determinant?

Answer 1

I assume you're using the naive method of expanding Laplace's formula. If you want to gain in speed, you can decompose your matrix M using LU decomposition (into two lower- and upper-diagonal matrices) which you can achieve with a modified Gauss-Jordan elimination in 2*n^3/3 FLOPS and then calculate the determinant as:

det(M) = det(L) * det(U), which for triangular matrices is just the product of the entries in their diagonal.

This process will still be faster than O(n!).

Edit: you can also use Crout's method, which is widely implemented.

Answer 2

Well, not many of us working in the field would regard 18x18 as a large matrix and almost any technique you choose should be fast enough on any modern computer. Nor would many of us tackle matrix questions with recursive algorithms, much more likely to use iterative ones -- but that could be a reflection of the fact that a lot of people working on matrix problems are scientists and engineers not computer scientists.

I suggest you look at Numerical Recipes in C++. Not necessarily the best code you'll find, but it is a text for studying and learning from. For better codes, BOOST has a good reputation and there's always BLAS and things like the Intel Maths Kernel Library or the AMD Core Maths Library. I think all of these have implementations of determinant-finding routines which will tackle an 18x18 matrix very quickly.