Ask Your Question
0

how does weak_popov_form work?

asked 2021-09-26 09:34:40 +0100

iieOtto gravatar image

updated 2021-09-27 05:00:18 +0100

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 flag offensive close merge delete

Comments

Please add the code with your examples/tests.

rburing gravatar imagerburing ( 2021-09-26 14:28:49 +0100 )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.

nbruin gravatar imagenbruin ( 2021-09-26 20:17:05 +0100 )edit

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

iieOtto gravatar imageiieOtto ( 2021-09-27 03:11:08 +0100 )edit

1 Answer

Sort by ยป oldest newest most voted
0

answered 2021-09-27 03:31:10 +0100

iieOtto gravatar image

updated 2021-09-28 03:18:53 +0100

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
edit flag offensive delete link more

Comments

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.

nbruin gravatar imagenbruin ( 2021-09-27 20:18:41 +0100 )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.

iieOtto gravatar imageiieOtto ( 2021-09-28 03:13:01 +0100 )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.

nbruin gravatar imagenbruin ( 2021-09-28 21:10:58 +0100 )edit

Good idea! Thank you again for your answer. I'll try it

iieOtto gravatar imageiieOtto ( 2021-09-29 03:13:27 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2021-09-26 09:31:49 +0100

Seen: 320 times

Last updated: Sep 28 '21