Revision history [back]

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

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

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?

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?

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?

See also: https://groups.google.com/forum/#!topic/sage-devel/vUJMpEqfXz0this thread on sage-devel.

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.

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.