Slug #1187
Matrix rank is slow (over QQ)
Description
The rank function is too slow:
M := mat([[ random(-99,99) | j in 1..100] | i in 1..100]); rk(M); -- takes about 1s det(M) <> 0; -- takes about 0.1s
Make it faster (at least for some cases).
History
#1 Updated by John Abbott almost 6 years ago
A potentially fast heuristic is to reduce mod p and compute the rank of the reduced matrix. This should be quick; if the reduced matrix has full rank then so did the original. The rank of the reduced matrix is <= true rank. A heuristic could try a few primes and then take the max of the ranks of the reduced matrices.
Maybe another heuristic for "long, thin" matrices would be to pick a "squarer" submatrix...
#2 Updated by John Abbott almost 6 years ago
Rank is slower than det even for matrices over a small finite field.
For example a random 500x500 matrix: det takes 0.06s, but rank takes about 1.2s.