I need an recursive algorithm to calculate determinant of n*n matrix.
+3
A:
Wikipedia has a formula for calculating determinants. It involves permutations, which can easily be generated recursively. Google has plenty of results on "permutation algorithm".
IVlad
2010-07-02 09:33:36
The formula with permutations has *n!* terms and is not usable for large n.
lhf
2010-07-02 10:43:45
It's most likely homework and probably what his teachers expect, so it doesn't really matter.
IVlad
2010-07-02 11:19:33
+2
A:
I don't see the point in recursiveness here.
This matrix operation can easily be implemented in a SIMD operation, can be divided into threads, can be very well calculated on the GPU.
Recursiveness consumes a lot of memory, and some systems have limits in recursion depths.
Alexander
2010-07-02 09:37:19
+1
A:
|a b c d ...|
det |...........|
|...........|
|...........|
= a * det(M1) - b * det(M2) + c * det(M3) - d * det(M4) + ... - ...
where Mn is the remaining Matrix if you drop the first row and the n-th column
Landei
2010-07-02 09:45:37
+1
A:
The Standard Method for computing the determinant is LU decomposition. Use a library like LAPACK in production code. There is absolutely no point in using recursion, LU decomposition is usually implemented with a variant of Gauss pivot method.
Alexandre C.
2010-07-02 09:46:38