ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 10 Apr 2020 14:17:21 +0200Compute dimension of vector subspacehttps://ask.sagemath.org/question/50626/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)
See also: [this thread on sage-devel](https://groups.google.com/forum/#!topic/sage-devel/vUJMpEqfXz0).Tue, 07 Apr 2020 17:47:33 +0200https://ask.sagemath.org/question/50626/compute-dimension-of-vector-subspace/Comment by rburing for <p>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).</p>
<p>If I go through (K^30).subspace([...]) then Sage runs the echelon_form and produces me matrices with coefficients of size 10^(100000).</p>
<p>Here is an example showing the issue</p>
<pre><code>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
</code></pre>
<p>Alternatively, you can consider the non streamed version</p>
<pre><code>sage: K = NumberField(x^20 - 3, 'a')
sage: M = MatrixSpace(K, 20)
sage: m = M.random_element()
sage: m.rank()
</code></pre>
<p>This is not practical at all and basically stops around dim 15. Is there any alternative?</p>
<p>Note that for problems of the same size over rational numbers, Sage does succeed</p>
<pre><code>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
</code></pre>
<p>(if the matrix is full rank the problem is way easier)</p>
<p>See also: <a href="https://groups.google.com/forum/#!topic/sage-devel/vUJMpEqfXz0">this thread on sage-devel</a>.</p>
https://ask.sagemath.org/question/50626/compute-dimension-of-vector-subspace/?comment=50627#post-id-50627How about this matrix? `m2 = block_matrix([[m[i,j].matrix() for j in range(M.ncols())] for i in range(M.nrows())], subdivide=False)`Tue, 07 Apr 2020 19:46:26 +0200https://ask.sagemath.org/question/50626/compute-dimension-of-vector-subspace/?comment=50627#post-id-50627Comment by vdelecroix for <p>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).</p>
<p>If I go through (K^30).subspace([...]) then Sage runs the echelon_form and produces me matrices with coefficients of size 10^(100000).</p>
<p>Here is an example showing the issue</p>
<pre><code>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
</code></pre>
<p>Alternatively, you can consider the non streamed version</p>
<pre><code>sage: K = NumberField(x^20 - 3, 'a')
sage: M = MatrixSpace(K, 20)
sage: m = M.random_element()
sage: m.rank()
</code></pre>
<p>This is not practical at all and basically stops around dim 15. Is there any alternative?</p>
<p>Note that for problems of the same size over rational numbers, Sage does succeed</p>
<pre><code>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
</code></pre>
<p>(if the matrix is full rank the problem is way easier)</p>
<p>See also: <a href="https://groups.google.com/forum/#!topic/sage-devel/vUJMpEqfXz0">this thread on sage-devel</a>.</p>
https://ask.sagemath.org/question/50626/compute-dimension-of-vector-subspace/?comment=50628#post-id-50628The 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)!Tue, 07 Apr 2020 20:24:07 +0200https://ask.sagemath.org/question/50626/compute-dimension-of-vector-subspace/?comment=50628#post-id-50628Answer by rburing for <p>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).</p>
<p>If I go through (K^30).subspace([...]) then Sage runs the echelon_form and produces me matrices with coefficients of size 10^(100000).</p>
<p>Here is an example showing the issue</p>
<pre><code>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
</code></pre>
<p>Alternatively, you can consider the non streamed version</p>
<pre><code>sage: K = NumberField(x^20 - 3, 'a')
sage: M = MatrixSpace(K, 20)
sage: m = M.random_element()
sage: m.rank()
</code></pre>
<p>This is not practical at all and basically stops around dim 15. Is there any alternative?</p>
<p>Note that for problems of the same size over rational numbers, Sage does succeed</p>
<pre><code>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
</code></pre>
<p>(if the matrix is full rank the problem is way easier)</p>
<p>See also: <a href="https://groups.google.com/forum/#!topic/sage-devel/vUJMpEqfXz0">this thread on sage-devel</a>.</p>
https://ask.sagemath.org/question/50626/compute-dimension-of-vector-subspace/?answer=50643#post-id-50643Take 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)`.Thu, 09 Apr 2020 14:41:52 +0200https://ask.sagemath.org/question/50626/compute-dimension-of-vector-subspace/?answer=50643#post-id-50643Comment by vdelecroix for <p>Take the block matrix over $\mathbb{Q}$ defined by</p>
<pre><code>m2 = block_matrix([[m[i,j].matrix() for j in range(M.ncols())] for i in range(M.nrows())])
</code></pre>
<p>and divide its rank by <code>K.degree()</code>.</p>
<p>P.S. To get random matrices of lower rank you can use e.g. <code>M.random_element(density=0.1)</code>.</p>
https://ask.sagemath.org/question/50626/compute-dimension-of-vector-subspace/?comment=50652#post-id-50652As 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.Fri, 10 Apr 2020 13:04:17 +0200https://ask.sagemath.org/question/50626/compute-dimension-of-vector-subspace/?comment=50652#post-id-50652Comment by vdelecroix for <p>Take the block matrix over $\mathbb{Q}$ defined by</p>
<pre><code>m2 = block_matrix([[m[i,j].matrix() for j in range(M.ncols())] for i in range(M.nrows())])
</code></pre>
<p>and divide its rank by <code>K.degree()</code>.</p>
<p>P.S. To get random matrices of lower rank you can use e.g. <code>M.random_element(density=0.1)</code>.</p>
https://ask.sagemath.org/question/50626/compute-dimension-of-vector-subspace/?comment=50653#post-id-50653(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.0714Fri, 10 Apr 2020 14:17:21 +0200https://ask.sagemath.org/question/50626/compute-dimension-of-vector-subspace/?comment=50653#post-id-50653