What is the fastest algorithm (a link to C or C++ example would be cool) to check if a small square matrix (<16*16 elements) is singular (non-invertible, det = 0) ?
相关问题
- Extract matrix elements using a vector of column i
- Reshape matrix by rows
- Finding k smallest elements in a min heap - worst-
- binary search tree path list
- High cost encryption but less cost decryption
相关文章
- Numpy matrix of coordinates
- What are the problems associated to Best First Sea
- Coin change DP solution to keep track of coins
- Algorithm for partially filling a polygonal mesh
- Robust polygon normal calculation
- Algorithm for maximizing coverage of rectangular a
- C++: How to use unnamed template parameters in cla
- How to compute the power of a matrix in R [duplica
I agree with Gaussian elimination. http://math.nist.gov/javanumerics/jama/doc/Jama/LUDecomposition.html documents LU decomposition - after constructing the LU decomposition from a matrix you can call a method on it to get the determinant. My guess is that it is at least worth timing this to compare it with any more specialised scheme.
Best way is to compute the condition number via SVD and check if it is greater than 1 / epsilon, where epsilon is the machine precision.
If you allow false negatives (ie. a matrix is defective, but your algorithm may not detect it), you can use the max(a_ii) / min(a_ii) formula from the Wikipedia article as a proxy for the condition number, but you have to compute the QR decomposition first (the formula applies to triangular matrices): A = QR with R orthogonal, then cond(A) = cond(Q). There are also techniques to compute the condition number of Q with O(N) operations, but there are more complex.
The fastest way is probably to hard code a determinant function for each size matrix you expect to deal with.
Here is some psuedo-code for N=3, but if you check out The Leibniz formula for determinants the pattern should be clear for all N.