Normal forms for univariate matrices: performance issue for unbalanced shifts

[vneiger]

For two almost identical situations, the computation of a shifted-weak Popov form of a univariate matrix will have significantly diverging performances. An example is showed below for a specific form of input matrix which often arises in univariate matrix computations, and for a shift leading to either the upper triangular Hermite normal form, or to the lower triangular one; a similar performance discrepancy can be expected more generally as soon as the shift is unbalanced (e.g. to lead to a block-triangular form). It would be worth taking a thorough look at what happens for these cases in the current _weak_popov_form implementation, to see if there is some way to mitigate this issue.

field = GF(997)
pring.<x> = field[]

m = 10
n = 5
d = 50

F1 = matrix.block([[matrix.identity(m), matrix.random(pring, m, n, degree=d-1)], [0, matrix.random(pring, n, n, degree=d)]])
F2 = matrix.block([[matrix.random(pring, n, n, degree=d), 0], [matrix.random(pring, m, n, degree=d-1), matrix.identity(m)]])

shdn = [+m*d*i for i in range(m)] + [m*m*d for i in range(n)]
shup = [m*d*(m-1)-m*d*i for i in range(m)] + [m*d*m for i in range(n)]

tstart = time.time()
P1dn = F1.weak_popov_form(shifts=shdn, ordered=True)
tend = time.time()
print(tend-tstart)
tstart = time.time()
P1up = F1.weak_popov_form(shifts=shup, ordered=True)
tend = time.time()
print(tend-tstart)

tstart = time.time()
P2dn = F2.weak_popov_form(shifts=shdn, ordered=True)
tend = time.time()
print(tend-tstart)
tstart = time.time()
P2up = F2.weak_popov_form(shifts=shup, ordered=True)
tend = time.time()
print(tend-tstart)

Running times show a large discrepancy between the two computations (factor around 20-25):

1.1891660690307617
0.041374921798706055

0.027834177017211914
0.826286792755127