Project

General

Profile

Slug #1187

Matrix rank is slow (over QQ)

Added by John Abbott almost 6 years ago. Updated almost 6 years ago.

Status:
New
Priority:
Normal
Assignee:
-
Category:
Improving
Target version:
Start date:
19 Jun 2018
Due date:
% Done:

0%

Estimated time:
Spent time:

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.

Also available in: Atom PDF