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
Please add the code with your examples/tests.
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.
thx! I did some experiments, and the output are placed below.