# how does weak_popov_form work?

I want to transform the lower triangular polynomial matrix into weak popov form, when I use the command .weak_popov_form in sage, something strange happened.

I construct a 100*100 lower triangular polynomial matrix A and B, the degree of elements in A( or B) are bounded 50(or 80).

[MS03] pointed out that the reduction of polynomial matrix is related to the dimension of the matrix and the exponent of its elements.According to the complexity formula, the running time of input A should less than that of input B.

But when I use the algorithm to transform A,B into weak popov form, the opposite result was obtained, Time A = 700+ sec is greater than Time B = 500+ sec !!

I experimented with several groups of random polynomial matrices and got similar results. Is my question too stupid? I hope I made a mistake.

edit retag close merge delete

( 2021-09-26 14:28:49 +0200 )edit

Complexity bounds tend to be asymptotic, so in particular cases an O(n^2) algorithm can outperform an O(n) algorithm, and actual run times need not be monotone-increasing in the complexity parameter. So a single example never provides a counterexample to a complexity estimate. It may still be worth investigating what's going on, though.

( 2021-09-26 20:17:05 +0200 )edit

thx! I did some experiments, and the output are placed below.

( 2021-09-27 03:11:08 +0200 )edit

Sort by ยป oldest newest most voted

example 1: I generated a 25*25 lower triangular polynomial matrices A, and B = A/x^15(degree less than 15 are rounded off) their exponential matrix are:

matrix A
[90 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[87 85 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[84 82 80 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[81 79 77 75 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[78 76 74 72 70 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[75 73 71 69 67 65 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[72 70 68 66 64 62 60 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[69 67 65 63 61 59 57 55 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[66 64 62 60 58 56 54 52 50 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[63 61 59 57 55 53 51 49 47 45 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[60 58 56 54 52 50 48 46 44 42 40 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[57 55 53 51 49 47 45 43 41 39 37 35 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[54 52 50 48 46 44 42 40 38 36 34 32 30 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[51 49 47 45 43 41 39 37 35 33 31 29 27 25 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[45 43 41 39 37 35 33 31 29 27 25 23 21 19 17 15 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[-1 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 16 -1 -1 -1 -1 -1 -1 -1 -1]
[-1 -1 47 45 43 41 39 37 35 33 31 29 27 25 23 21 19 17 -1 -1 -1 -1 -1 -1 -1]
[-1 -1 -1 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 18 -1 -1 -1 -1 -1 -1]
[-1 -1 -1 -1 49 47 45 43 41 39 37 35 33 31 29 27 25 23 21 19 -1 -1 -1 -1 -1]
[-1 -1 -1 -1 -1 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 20 -1 -1 -1 -1]
[-1 -1 -1 -1 -1 -1 51 49 47 45 43 41 39 37 35 33 31 29 27 25 23 21 -1 -1 -1]
[-1 -1 -1 -1 -1 -1 -1 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24 22 -1 -1]
[-1 -1 -1 -1 -1 -1 -1 -1 53 51 49 47 45 43 41 39 37 35 33 31 29 27 25 23 -1]
[-1 -1 -1 -1 -1 -1 -1 -1 -1 54 52 50 48 46 44 42 40 38 36 34 32 30 28 26 24]
matrix B
[75 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[72 70 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[69 67 65 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[66 64 62 60 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[63 61 59 57 55 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[60 58 56 54 52 50 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[57 55 53 51 49 47 45 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[54 52 50 48 46 44 42 40 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[51 49 47 45 43 41 39 37 35 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[48 46 44 42 40 38 36 34 32 30 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[45 43 41 39 37 35 33 31 29 27 25 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[42 40 38 36 34 32 30 28 26 24 22 20 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[39 37 35 33 31 29 27 25 23 21 19 17 15 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[36 34 32 30 28 26 24 22 20 18 16 14 12 10 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[33 31 29 27 25 23 21 19 17 15 13 11  9  7  5 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[30 28 26 24 22 20 18 16 14 12 10  8  6  4  2  0 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[-1 31 29 27 25 23 21 19 17 15 13 11  9  7  5  3  1 -1 -1 -1 -1 -1 -1 -1 -1]
[-1 -1 32 30 28 26 24 22 20 18 16 14 12 10  8  6  4  2 -1 -1 -1 -1 -1 -1 -1]
[-1 -1 -1 33 31 29 27 25 23 21 19 17 15 13 11  9  7  5  3 -1 -1 -1 -1 -1 -1]
[-1 -1 -1 -1 34 32 30 28 26 24 22 20 18 16 14 12 10  8  6  4 -1 -1 -1 -1 -1]
[-1 -1 -1 -1 -1 35 33 31 29 27 25 23 21 19 17 15 13 11  9  7  5 -1 -1 -1 -1]
[-1 -1 -1 -1 -1 -1 36 34 32 30 28 26 24 22 20 18 16 14 12 10  8  6 -1 -1 -1]
[-1 -1 -1 -1 -1 -1 -1 37 35 33 31 29 27 25 23 21 19 17 15 13 11  9  7 -1 -1]
[-1 -1 -1 -1 -1 -1 -1 -1 38 36 34 32 30 28 26 24 22 20 18 16 14 12 10  8 -1]
[-1 -1 -1 -1 -1 -1 -1 -1 -1 39 37 35 33 31 29 27 25 23 21 19 17 15 13 11  9]

In [MS03], for n*m polynomial matrix(rank=r, degree bound=d), it requires $O(nmrd^2)$ operations to transform to weak popov form. Obviously, the running time of input B is shorter than that of input A.

Let's look the output:

cost of A:  0.19062423706054688
cost of B:  2.67919921875

I really don't know why :(

example 2:

L.<x> = PolynomialRing(ZZ)

n = 25
d = 50
d_R = 30

lattice = matrix(L, n)
lattice_R = matrix(L, n)
for i in range(n):
for j in range(n):
if i >= j:
lattice[i,j] = (ZZ[x].random_element(degree=d-randint(0,10)))
lattice_R[i,j] = (ZZ[x].random_element(degree=d_R-randint(0,10)))

deg = matrix(ZZ, n)
deg_R = matrix(ZZ, n)
for i in range(n):
for j in range(n):
deg[i,j] = lattice[i,j].degree()
deg_R[i,j] = lattice_R[i,j].degree()

print(deg)
print("-------------------------------------------------------------")
print(deg_R)

pR.<z> = QQ[]
M = Matrix(pR,lattice)
M_R = Matrix(pR,lattice_R)

print("-------------------------------------------------------------")

import time
start = time.time()
W = M.weak_popov_form()
end = time.time()
print("cost of A: ", end-start)

import time
start = time.time()
W_R = M_R.weak_popov_form()
end = time.time()

print("cost of B: ", end-start)

and the output:

[43 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[49 50 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[50 44 49 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[50 42 40 42 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[43 41 43 49 49 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[46 47 42 42 41 46 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[50 47 43 47 44 49 40 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[40 47 41 42 49 40 40 40 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[40 42 42 41 41 48 42 50 40 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[41 45 44 46 50 49 45 43 46 48 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[49 41 47 43 50 43 46 44 41 40 41 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[49 50 44 44 47 41 43 46 46 45 43 50 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[49 42 41 44 41 45 49 48 50 44 45 42 47 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[41 40 44 43 40 46 49 43 49 45 43 49 42 42 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[49 45 46 40 41 45 46 45 48 43 49 41 40 44 41 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[49 46 50 48 46 44 47 50 49 45 42 47 50 50 49 40 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[40 44 50 50 48 50 40 48 48 41 45 42 50 48 44 44 44 -1 -1 -1 -1 -1 -1 -1 -1]
[49 44 49 46 40 43 50 42 40 41 47 42 46 46 48 44 43 43 -1 -1 -1 -1 -1 -1 -1]
[40 49 41 50 42 42 45 45 45 42 46 49 50 40 43 44 45 44 44 -1 -1 -1 -1 -1 -1]
[40 47 41 45 43 46 50 40 47 48 47 41 49 41 40 48 40 45 48 41 -1 -1 -1 -1 -1]
[47 48 41 47 46 50 41 44 41 42 47 40 49 42 43 50 50 41 49 40 40 -1 -1 -1 -1]
[46 45 48 40 49 49 44 41 43 42 43 47 43 41 49 43 44 43 48 40 50 45 -1 -1 -1]
[48 43 40 44 45 41 47 47 41 48 45 43 49 42 47 43 48 41 47 41 50 42 46 -1 -1]
[43 43 41 41 43 44 49 44 41 45 44 42 41 50 43 40 42 43 49 46 49 41 42 48 -1]
[44 43 46 49 44 43 40 49 49 41 48 44 43 40 44 47 49 46 47 48 41 44 50 48 44]
-------------------------------------------------------------
[25 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[29 27 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[23 23 21 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[25 24 21 24 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[26 23 29 20 22 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[29 20 30 25 30 22 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[20 23 21 22 22 28 28 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[22 24 21 30 24 25 22 28 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[22 29 30 24 24 27 22 30 27 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[24 26 30 23 22 26 26 20 26 28 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[26 28 21 25 30 28 22 26 30 23 25 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[24 20 30 20 30 20 28 24 30 26 25 30 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[27 20 27 25 27 20 23 23 28 26 20 26 25 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[25 30 20 27 22 29 28 26 24 24 29 27 21 29 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[22 25 21 23 25 29 28 26 30 21 30 20 27 23 20 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[30 28 30 21 22 21 23 30 25 24 22 25 24 27 22 28 -1 -1 -1 -1 -1 -1 -1 -1 -1]
[21 21 25 24 23 24 22 29 21 28 29 30 22 30 24 30 29 -1 -1 -1 -1 -1 -1 -1 -1]
[30 29 29 21 21 26 21 20 26 29 29 20 22 30 26 21 24 30 -1 -1 -1 -1 -1 -1 -1]
[25 25 26 24 25 23 23 25 23 27 24 24 20 21 28 26 28 24 30 -1 -1 -1 -1 -1 -1]
[29 30 24 23 26 20 21 29 25 22 25 22 24 27 24 24 20 28 24 26 -1 -1 -1 -1 -1]
[26 28 28 21 22 26 26 29 27 21 30 21 28 25 22 30 29 24 28 20 25 -1 -1 -1 -1]
[24 25 30 21 29 21 20 23 21 26 27 30 21 22 27 27 28 27 25 27 23 20 -1 -1 -1]
[21 30 26 26 28 29 21 20 26 22 26 20 27 24 27 20 28 24 29 25 24 24 29 -1 -1]
[23 24 26 20 28 22 24 30 28 28 22 20 25 26 26 21 23 20 22 27 30 24 20 25 -1]
[30 28 20 26 23 26 30 25 29 28 22 26 27 28 26 26 26 22 22 23 23 28 25 26 23]
-------------------------------------------------------------
cost of A:  2.8042526245117188
cost of B:  0.32115912437438965
more

That complexity bound must be assuming constant time coefficient arithmetic, which will not be true over Q or Z. Furthermore, with just a degree bound it is basically assuming dense polynomial arithmetic, which is generally not how multivariate polynomial arithmetic is implemented. Even for dense univariate polynomials, depending on the algorithm, having many low degree entries in your matrix and/or whether the entries have interesting properties (perhaps monomials behave differently?) will probably affect actual runtime quite a bit.

( 2021-09-27 20:18:41 +0200 )edit

thx! The matrix in example 1 is generated by me according to some rules. But what I don't understand is why I randomly generate two matrices with different orders, but their running time conforms to the complexity formula? The code and output of the example are shown in example 2.

( 2021-09-28 03:13:01 +0200 )edit

If you really want to know the answer, trace through the algorithm by hand and see why sometimes the execution is faster than expected. It's quite usual for this to happen in algorithms that have conditional execution and loops in them. For instance, integer GCD(a,b) with a>b is guaranteed to finish in O(log(a)) divisions, but GCD(a,a-1) always needs just one division. Perhaps you can prove a theorem about "best case performance" of computing weak Popov form and classify a set of inputs for which you get better-than-worst-case performance.

( 2021-09-28 21:10:58 +0200 )edit

( 2021-09-29 03:13:27 +0200 )edit