Compute dimension of vector subspace

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)

edit retag close merge delete

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)

( 2020-04-07 19:46:26 +0200 )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)!

( 2020-04-07 20:24:07 +0200 )edit

Sort by » oldest newest most voted

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

more

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.

( 2020-04-10 13:04:17 +0200 )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

( 2020-04-10 14:17:21 +0200 )edit