`rank` is very slow for some matrices

[matthias314]

I'm computing the rank of matrices with coefficients in a multivariate polynomial ring over ZZ/2. Most of the time this is quick, but sometimes it takes much longer. For instance, Macaulay2 1.18 needs about 4min to figure out that this 32x32 matrix over a polynomial ring in 5 variables has full rank. Sage can do it 150 times faster. Is this a bug?

[mahrud]

I wonder if Sage uses Flint for this. I believe we do polynomial operations in the engine and use fflas_ffpack? Is this right @mikestillman ?

[matthias314]

Here is another example. It's again a full-rank 32x32 matrix with coefficients in a polynomial ring in 5 variables over ZZ/2. On the same computer, Macaulay2 needs 692 seconds to compute the rank and Sage only 76 milliseconds.

[kschwede]

This is a case where transposing the matrix allows rank to run massively faster than without transposing the matrix. I've seen this with a bunch of examples but don't know how to tell which matrices will be better with a transpose first.

i1 : load "rankbug.txt"

i2 : elapsedTime rank transpose M
 -- 0.002485 seconds elapsed

o2 = 32

i3 : elapsedTime rank M
 -- 56.0241 seconds elapsed

o3 = 32

i4 : load "rankbug2.txt"

i5 : elapsedTime rank transpose M
 -- 0.33643 seconds elapsed

o5 = 32

i6 : elapsedTime rank M
 -- 201.133 seconds elapsed

o6 = 32

i7 : elapsedTime det M;
 -- 0.953097 seconds elapsed

i8 : elapsedTime det M
 -- 0.8422 seconds elapsed

      14 18 16 22 10    16 16 16 20 12    14 18 16 16 16    16 16 16 14 18
o8 = p  p  p  p  p   + p  p  p  p  p   + p  p  p  p  p   + p  p  p  p  p
      0  1  2  3  4     0  1  2  3  4     0  1  2  3  4     0  1  2  3  4

o8 : R

i9 : elapsedTime det(M, Strategy=>Cofactor)
 -- 1.96916 seconds elapsed

      14 18 16 22 10    16 16 16 20 12    14 18 16 16 16    16 16 16 14 18
o9 = p  p  p  p  p   + p  p  p  p  p   + p  p  p  p  p   + p  p  p  p  p
      0  1  2  3  4     0  1  2  3  4     0  1  2  3  4     0  1  2  3  4

o9 : R

It would be nice to be able to run several strategies simultaneously in cases like this.