applications.runtime_circuits¶
Runtime of Circuits
Runtime of Circuits¶
We demonstrate how to test the runtime of the package elementary_vectors:
sage: from elementary_vectors import *
Integers¶
We generate a random integer matrix and time the computation of its circuits:
sage: M = random_matrix(ZZ, 5, 10)
sage: circuits(M) # random
[(5793, -22553, -2686, -24007, 47617, -4117, 0, 0, 0, 0),
(-1334, 6440, 10028, -3496, -1265, 0, -4117, 0, 0, 0),
...
(0, 0, 0, 0, -136964, -112190, -13088, 53344, -197942, -57082)]
sage: timeit("circuits(M)") # random
125 loops, best of 3: 5.7 ms per loop
Field Extensions¶
Next, we generate a matrix over \(\mathbb{Z}[\sqrt{2}]\):
sage: F = NumberField(x^2 - 2, name="a")
sage: M = random_matrix(F, 3, 6)
sage: circuits(M) # random
[(-10659*a - 23372, -136*a + 446, -512*a - 810, -456*a - 5746, 0, 0),
(8924*a + 2132, 52*a - 34, 376*a + 496, 0, -456*a - 5746, 0),
(48606*a - 769809, 21852*a - 4798, -421*a - 34678, 0, 0, -456*a - 5746),
(892*a + 1380, -20*a - 22, 0, 376*a + 496, 512*a + 810, 0),
(-917*a - 42614, -3441*a, 0, -421*a - 34678, 0, 512*a + 810),
(11626*a - 47760, 1727*a + 1974, 0, 0, -421*a - 34678, -376*a - 496),
(-817*a + 332, 0, -20*a - 22, -52*a + 34, -136*a + 446, 0),
(-103317*a + 16895, 0, -3441*a, -21852*a + 4798, 0, -136*a + 446),
(3136*a + 60163, 0, 1727*a + 1974, 0, -21852*a + 4798, 52*a - 34),
(6913*a + 42, 0, 0, 1727*a + 1974, 3441*a, -20*a - 22),
(0, -817*a + 332, -892*a - 1380, 8924*a + 2132, 10659*a + 23372, 0),
(0, -103317*a + 16895, 917*a + 42614, 48606*a - 769809, 0, 10659*a + 23372),
(0, 3136*a + 60163, -11626*a + 47760, 0, 48606*a - 769809, -8924*a - 2132),
(0, 6913*a + 42, 0, -11626*a + 47760, -917*a - 42614, -892*a - 1380),
(0, 0, 6913*a + 42, -3136*a - 60163, -103317*a + 16895, 817*a - 332)]
sage: timeit("circuits(M)") # random
625 loops, best of 3: 709 μs per loop
Now, we generate a matrix over \(\mathbb{Z}[\sqrt{2}, \sqrt{3}, \sqrt{5}]\):
sage: F = NumberField([x^2 - 2, x^2 - 3, x^2 - 5], names="a, b, c")
sage: M = random_matrix(F, 2, 4)
sage: circuits(M) # random
[(((441128595124/275*c - 5410997011718/165)*b + 1397114905746/55*c - 1708489033121/275)*a + (-3422411437886/165*c + 4185440154527/825)*b - 216135874313/55*c + 4418318864108/55, ((-280761812186/5*c - 5511848243593/165)*b + 4269466941457/165*c + 71767672680823/330)*a + (-3486251122813/165*c - 3907001222229/22)*b + 45395383767619/330*c + 13502216755034/165, ((1783954714769/165*c + 553693027861/45)*b - 428889083597/45*c - 13818489673507/330)*a + (3852230860787/495*c + 3761329602991/110)*b - 8740562824321/330*c - 14919636705194/495, 0),
(((30710666997607/52780*c - 18315973151543/15660)*b + 184437150638723/203580*c - 1070476793577397/475020)*a + (-1054249243359233/1425060*c + 72845084241856/39585)*b - 48364755373661/33930*c + 4083084027628873/1425060, ((-1993572075345761/1045044*c + 3383607804169625/348348)*b - 102115815259631/13572*c + 15441487463462339/2090088)*a + (2140820698179533/348348*c - 12606271379020973/2090088)*b + 887669622052387/190008*c - 24874481365108619/1045044, 0, ((1783954714769/165*c + 553693027861/45)*b - 428889083597/45*c - 13818489673507/330)*a + (3852230860787/495*c + 3761329602991/110)*b - 8740562824321/330*c - 14919636705194/495),
(((-416516184701629/67860*c + 17304645330576509/1741740)*b - 1148918013348013/149292*c + 31053437036113418/1306305)*a + (10944420311086517/1741740*c - 99933899161219/5148)*b + 15713970380496259/1045044*c - 127161935230607131/5225220, 0, ((-1993572075345761/1045044*c + 3383607804169625/348348)*b - 102115815259631/13572*c + 15441487463462339/2090088)*a + (2140820698179533/348348*c - 12606271379020973/2090088)*b + 887669622052387/190008*c - 24874481365108619/1045044, ((280761812186/5*c + 5511848243593/165)*b - 4269466941457/165*c - 71767672680823/330)*a + (3486251122813/165*c + 3907001222229/22)*b - 45395383767619/330*c - 13502216755034/165),
(0, ((-416516184701629/67860*c + 17304645330576509/1741740)*b - 1148918013348013/149292*c + 31053437036113418/1306305)*a + (10944420311086517/1741740*c - 99933899161219/5148)*b + 15713970380496259/1045044*c - 127161935230607131/5225220, ((-30710666997607/52780*c + 18315973151543/15660)*b - 184437150638723/203580*c + 1070476793577397/475020)*a + (1054249243359233/1425060*c - 72845084241856/39585)*b + 48364755373661/33930*c - 4083084027628873/1425060, ((441128595124/275*c - 5410997011718/165)*b + 1397114905746/55*c - 1708489033121/275)*a + (-3422411437886/165*c + 4185440154527/825)*b - 216135874313/55*c + 4418318864108/55)]
sage: timeit("circuits(M)") # random
625 loops, best of 3: 400 μs per loop
Polynomial Rings¶
Next, we consider a polynomial matrix with three variables:
sage: M = random_matrix(PolynomialRing(ZZ, "a, b, c"), 2, 4)
sage: circuits(M) # random
[(-a^3*b - 4*a^2*b^2 - 5*a^3*c - 18*a^2*b*c + b^3*c - 6*a^2*c^2 + 8*a*b*c^2 - 2*b^2*c^2 + 2*a*c^3 + 9*b*c^3 - 18*c^4 - 2*a^3 - 6*a^2*b + 2*b^3 - 4*a*b*c - 12*a*c^2 + 18*b*c^2 + 6*c^3 + 3*a^2 + 4*a*b + 2*a*c - 2*b*c + c^2 + 2*a - 4*b + 2*c - 1, -4*a^4 + a^3*b + 11*a^2*b^2 - a*b^3 + a^3*c + 208*a^2*b*c - 7*a*b^2*c + 23*b^3*c - 9*a^2*c^2 - 102*a*b*c^2 - 43*b^2*c^2 - 4*a*c^3 + b*c^3 + c^4 + 76*a^2*b - 4*a*b^2 + 46*b^3 + 10*a*c^2 + 2*b*c^2 - 6*c^3 - 34*a*b + b^2 + 4*a*c + c^2 - 2*c, 4*a^4 + 11*a^3*b + 20*a^2*b^2 + 103*a*b^3 - b^4 - a^3*c - 37*a^2*b*c + a*b^2*c + a^2*c^2 + 309*a*b*c^2 - 10*b^2*c^2 + a*c^3 - 9*c^4 + 8*a^2*c - 2*a*b*c + 48*b^2*c - 4*a*c^2 + 20*c^3 - 4*a^2 - 67*a*b - 21*b^2 + a*c + c^2 - 4*c, 0),
(a^4 + 19*a^3*b + 50*a^2*b^2 + 13*a*b^3 + 4*a^3*c + 5*a^2*b*c - 34*a^2*c^2 - 39*a*b*c^2 + 2*a^2*c + 32*a*b*c + 15*b^2*c - 3*a*c^2 + 31*c^3 + 7*a^2 - 6*a*b - 6*b^2 - 2*c^2 - 6*c, -16*a^4 - 50*a^3*b - 630*a^2*b^2 - 303*a*b^3 + 6*b^4 + 4*a^3*c + 5*a^2*b*c - 3*a^2*c^2 - 57*a*b*c^2 + 8*b^2*c^2 + 2*c^4 + 10*a^2*c - 35*a*b*c + 57*b^2*c - 3*a*c^2 - c^3, 0, 4*a^4 + 11*a^3*b + 20*a^2*b^2 + 103*a*b^3 - b^4 - a^3*c - 37*a^2*b*c + a*b^2*c + a^2*c^2 + 309*a*b*c^2 - 10*b^2*c^2 + a*c^3 - 9*c^4 + 8*a^2*c - 2*a*b*c + 48*b^2*c - 4*a*c^2 + 20*c^3 - 4*a^2 - 67*a*b - 21*b^2 + a*c + c^2 - 4*c),
(a^4 + 20*a^3*b + 11*a^2*b^2 + 24*a^3*c + 29*a^2*b*c - 16*a*b^2*c - 6*b^3*c - 8*a^2*c^2 + 17*a*b*c^2 + 12*b^2*c^2 - 2*b*c^3 + 4*c^4 + 8*a^3 + 8*a^2*b - 32*a*b^2 - 12*b^3 - 3*a*b*c - 18*a*c^2 - 4*b*c^2 + 9*c^3 - 4*a^2 - 5*a*b - 6*a*c + 3*c, 0, -16*a^4 - 50*a^3*b - 630*a^2*b^2 - 303*a*b^3 + 6*b^4 + 4*a^3*c + 5*a^2*b*c - 3*a^2*c^2 - 57*a*b*c^2 + 8*b^2*c^2 + 2*c^4 + 10*a^2*c - 35*a*b*c + 57*b^2*c - 3*a*c^2 - c^3, 4*a^4 - a^3*b - 11*a^2*b^2 + a*b^3 - a^3*c - 208*a^2*b*c + 7*a*b^2*c - 23*b^3*c + 9*a^2*c^2 + 102*a*b*c^2 + 43*b^2*c^2 + 4*a*c^3 - b*c^3 - c^4 - 76*a^2*b + 4*a*b^2 - 46*b^3 - 10*a*c^2 - 2*b*c^2 + 6*c^3 + 34*a*b - b^2 - 4*a*c - c^2 + 2*c),
(0, a^4 + 20*a^3*b + 11*a^2*b^2 + 24*a^3*c + 29*a^2*b*c - 16*a*b^2*c - 6*b^3*c - 8*a^2*c^2 + 17*a*b*c^2 + 12*b^2*c^2 - 2*b*c^3 + 4*c^4 + 8*a^3 + 8*a^2*b - 32*a*b^2 - 12*b^3 - 3*a*b*c - 18*a*c^2 - 4*b*c^2 + 9*c^3 - 4*a^2 - 5*a*b - 6*a*c + 3*c, -a^4 - 19*a^3*b - 50*a^2*b^2 - 13*a*b^3 - 4*a^3*c - 5*a^2*b*c + 34*a^2*c^2 + 39*a*b*c^2 - 2*a^2*c - 32*a*b*c - 15*b^2*c + 3*a*c^2 - 31*c^3 - 7*a^2 + 6*a*b + 6*b^2 + 2*c^2 + 6*c, -a^3*b - 4*a^2*b^2 - 5*a^3*c - 18*a^2*b*c + b^3*c - 6*a^2*c^2 + 8*a*b*c^2 - 2*b^2*c^2 + 2*a*c^3 + 9*b*c^3 - 18*c^4 - 2*a^3 - 6*a^2*b + 2*b^3 - 4*a*b*c - 12*a*c^2 + 18*b*c^2 + 6*c^3 + 3*a^2 + 4*a*b + 2*a*c - 2*b*c + c^2 + 2*a - 4*b + 2*c - 1)]
sage: timeit("circuits(M)") # random
625 loops, best of 3: 739 μs per loop
Algebraic Numbers¶
Finally, we take matrices over the algebraic numbers:
sage: M = random_matrix(QQbar, 2, 4)
sage: circuits(M) # random
[(1.274456264653803?, 0.09005494464025914? - 0.5634713834792323?*I, -0.2231173769906498?, 0),
(0, 0.2586992821070093?, 0, -0.2231173769906498?),
(-1.477701670706430?, 0, 0.2586992821070093?, -0.09005494464025914? + 0.5634713834792323?*I)]
sage: timeit("circuits(M)") # random
625 loops, best of 3: 547 μs per loop
Especially, for matrices over the algebraic numbers, the determinants can occupy a huge amount of memory. Therefore, we only compute the support of the circuits:
sage: circuit_supports(M) # random
[[0, 1, 2, 3],
[0, 1, 2, 4],
[0, 1, 2, 5],
[0, 1, 3, 4],
[0, 1, 3, 5],
[0, 1, 4, 5],
[0, 2, 3, 4],
[0, 2, 3, 5],
[0, 2, 4, 5],
[0, 3, 4, 5],
[1, 2, 3, 4],
[1, 2, 3, 5],
[1, 2, 4, 5],
[1, 3, 4, 5],
[2, 3, 4, 5]]
sage: timeit("circuit_supports(M)") # random
125 loops, best of 3: 1.94 ms per loop