Ask Your Question
2

Compute dimension of vector subspace

asked 2020-04-07 10:47:33 -0500

vdelecroix gravatar image

updated 2020-04-07 11:06:41 -0500

I have a reasonably looking number field K of degree 20 (by reasonably looking I mean that the defining polynomial has coefficients < 1000). I have a stream that produces me reasonably looking vectors in K^30, that I call v1, v2, .... For each n I want to compute the dimension of V_n := span (v1, ..., vn).

If I go through (K^30).subspace([...]) then Sage runs the echelon_form and produces me matrices with coefficients of size 10^(100000).

Here is an example showing the issue

sage: x = polygen(QQ, 'x')
sage: K = NumberField(x^20 - 3, 'a')
sage: V = K**20
sage: U = V.subspace([])
....: for _ in range(20):
....:     U += V.subspace([V.random_element()])
....:     s = max(max(abs(coeff.numerator()) + abs(coeff.denominator()) for coeff in z.polynomial()) for z in U.matrix().list() if z)
....:     print("coeff size: %d" % len(str(s)))
....:     print("space dim: %d" % U.dimension())
....: 
coeff size: 131
space dim: 1
coeff size: 301
space dim: 2
coeff size: 487
space dim: 3
coeff size: 640
space dim: 4
coeff size: 877
space dim: 5
coeff size: 1141
space dim: 6
coeff size: 1501
space dim: 7
coeff size: 1959
space dim: 8

Alternatively, you can consider the non streamed version

sage: K = NumberField(x^20 - 3, 'a')
sage: M = MatrixSpace(K, 20)
sage: m = M.random_element()
sage: m.rank()

This is not practical at all and basically stops around dim 15. Is there any alternative?

Note that for problems of the same size over rational numbers, Sage does succeed

sage: M = MatrixSpace(QQ, 2000)
sage: m = M.random_element()
sage: m[1400] = m[0] - 30 * m[18] + 25 * m[1500]
sage: %time m.rank()
CPU times: user 22.6 s, sys: 149 ms, total: 22.8 s
Wall time: 22.8 s
1999

(if the matrix is full rank the problem is way easier)

See also: this thread on sage-devel.

edit retag flag offensive close merge delete

Comments

How about this matrix? m2 = block_matrix([[m[i,j].matrix() for j in range(M.ncols())] for i in range(M.nrows())], subdivide=False)

rburing gravatar imagerburing ( 2020-04-07 12:46:26 -0500 )edit

The operation matrix over K of size n x n -> matrix over Q of size (n * deg(K)) x (n * deg(K)) is only Q-linear. In particular, I don't think there is a way to extract the rank of m given the one of m'.

EDIT: you were correct (this was also suggested by N. Bruin on sage-devel)!

vdelecroix gravatar imagevdelecroix ( 2020-04-07 13:24:07 -0500 )edit

1 answer

Sort by ยป oldest newest most voted
2

answered 2020-04-09 07:41:52 -0500

rburing gravatar image

Take the block matrix over $\mathbb{Q}$ defined by

m2 = block_matrix([[m[i,j].matrix() for j in range(M.ncols())] for i in range(M.nrows())])

and divide its rank by K.degree().

P.S. To get random matrices of lower rank you can use e.g. M.random_element(density=0.1).

edit flag offensive delete link more

Comments

As I also commented on sage-devel this is not ideal since this method artificially multiply the size of the problem by deg(K).

PS: Of course, I don't have random matrices.

vdelecroix gravatar imagevdelecroix ( 2020-04-10 06:04:17 -0500 )edit

(lot) slower

sage: x = polygen(QQ)
sage: K = NumberField(x**15 - 3, 'a')
sage: n = 13
sage: V = VectorSpace(K, n)
sage: Vrat = VectorSpace(QQ, n * K.degree())
sage: U = V.subspace([])
sage: Urat = Vrat.subspace([])
sage: for i in range(n):
....:     v = V.random_element()
....:     t0 = time()
....:     U += V.subspace([v])
....:     t0 = time() - t0
....:     t1 = time()
....:     m = block_matrix([x.matrix() for x in v], subdivide=False, nrows=1, ncols=n)
....:     Urat += m.row_space()
....:     t1 = time() - t1
....:     print("%d %.4f %.4f" % (i, t0, t1))
0 0.0026 0.1442
1 0.0110 0.8616
2 0.0185 1.9340
3 0.0365 5.6868
4 0.0519 6.8069
5 0.0659 17.4297
6 0.0984 35.8414
7 0.1317 85.0714
vdelecroix gravatar imagevdelecroix ( 2020-04-10 07:17:21 -0500 )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: 2020-04-07 10:47:33 -0500

Seen: 139 times

Last updated: Apr 09