how does weak_popov_form work?

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

iieOtto
1 ●1 ●2

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

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

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 ( 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.

iieOtto ( 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.

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

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

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

add a comment

Please add the code with your examples/tests.

rburing ( 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.

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

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

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

Comments

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

how does weak_popov_form work? edit

Comments

1 Answer

Comments