Opened 2 years ago
Last modified 5 weeks ago
#28586 new defect
broken solving a linear system over GF(3)
Reported by: | dimpase | Owned by: | |
---|---|---|---|
Priority: | critical | Milestone: | sage-9.6 |
Component: | linear algebra | Keywords: | |
Cc: | Merged in: | ||
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
In Sage 8.5, the following got broken
B=matrix(GF(3), 2,2,[1,0,1,0], sparse=True) v=vector(GF(3), [1,1]) B.solve_right(v)
raises
--------------------------------------------------------------------------- TypeError Traceback (most recent call last) <ipython-input-1-f9262e2737d4> in <module>() 3 B=matrix(GF(Integer(3)), Integer(2),Integer(2),[Integer(1),Integer(0),Integer(1),Integer(0)], sparse=True) 4 v=vector(GF(Integer(3)), [Integer(1),Integer(1)]) ----> 5 B.solve_right(v) /opt/sage/local/lib/python3.7/site-packages/sage/matrix/matrix2.pyx in sage.matrix.matrix2.Matrix.solve_right (build/cythonized/sage/matrix/matrix2.c:8029)() 467 468 if self.rank() != self.nrows(): --> 469 X = self._solve_right_general(C, check=check) 470 else: 471 X = self._solve_right_nonsingular_square(C, check_rank=False) /opt/sage/local/lib/python3.7/site-packages/sage/matrix/matrix2.pyx in sage.matrix.matrix2.Matrix._solve_right_general (build/cythonized/sage/matrix/matrix2.c:8821)() 570 pivot_rows = A.pivot_rows() 571 A = A.matrix_from_rows(pivot_rows) --> 572 X = A.solve_right(B.matrix_from_rows(pivot_rows), check=False) 573 if len(pivot_cols) < self.ncols(): 574 # Now we have to put in zeros for the non-pivot ROWS, i.e., /opt/sage/local/lib/python3.7/site-packages/sage/matrix/matrix2.pyx in sage.matrix.matrix2.Matrix.solve_right (build/cythonized/sage/matrix/matrix2.c:8065)() 469 X = self._solve_right_general(C, check=check) 470 else: --> 471 X = self._solve_right_nonsingular_square(C, check_rank=False) 472 473 if not matrix: /opt/sage/local/lib/python3.7/site-packages/sage/matrix/matrix_modn_sparse.pyx in sage.matrix.matrix_modn_sparse.Matrix_modn_sparse._solve_right_nonsingular_square (build/cythonized/sage/matrix/matrix_modn_sparse.cpp:10291)() 929 from sage.rings.rational_field import QQ 930 from sage.matrix.special import diagonal_matrix --> 931 m, d = self._solve_matrix_linbox(B, algorithm) 932 return m * diagonal_matrix([QQ((1,x)) for x in d]) 933 else: /opt/sage/local/lib/python3.7/site-packages/sage/matrix/matrix_modn_sparse.pyx in sage.matrix.matrix_modn_sparse.Matrix_modn_sparse._solve_matrix_linbox (build/cythonized/sage/matrix/matrix_modn_sparse.cpp:11611)() 1113 1114 cdef givaro.ZRing givZZ -> 1115 cdef linbox.SparseMatrix_integer * A = new_linbox_matrix_integer_sparse(givZZ, self) 1116 cdef linbox.DenseVector_integer * b = new linbox.DenseVector_integer(givZZ, <size_t> self._nrows) 1117 cdef linbox.DenseVector_integer * res = new linbox.DenseVector_integer(givZZ, <size_t> self._ncols) TypeError: Cannot convert sage.matrix.matrix_modn_sparse.Matrix_modn_sparse to sage.matrix.matrix_integer_sparse.Matrix_integer_sparse
This still works in 8.4, as tested on cocalc, but is broken in later Sage versions
Change History (19)
comment:1 Changed 2 years ago by
- Description modified (diff)
comment:2 Changed 2 years ago by
comment:3 Changed 2 years ago by
#24544 got into 8.4, which is still OK (I tested on cocalc).
comment:4 Changed 2 years ago by
however, #23214 is a prime suspect. Doing git bisect now, I reckon 8.5.beta2 should still be OK.
comment:5 Changed 2 years ago by
OK, this got in in Sage 8.5.beta3 (no error in beta2, but the error in beta3).
So this is most likely #23214.
comment:6 Changed 2 years ago by
- Description modified (diff)
comment:7 Changed 2 years ago by
The code for solving linear systems in matrix_modn_sparse
is an exact copy/paste of the one in matrix_integer_sparse
. Even the tests! This is the reason why it is a complete (untested) failure.
To make it works it is some work...
- write the appropriate declarations for dense modular vectors and the solve interface in
libs/linbox/linbox.pxd
- write sage-linbox converters for dense modular vectors in
libs/linbox/conversion.pxd
- rewrite the solve interface to linbox in
matrix/matrix_modn_sparse.pyx
comment:8 Changed 2 years ago by
Hmm, what does this have to do with dense matrices/vectors? For dense matrices solving still works, for any A in [True,False]:
sage: B=matrix(GF(3), 2,2,[1,0,1,0], sparse=False) ....: v=vector(GF(3), [1,1], sparse=A) ....: B.solve_right(v) ....: ....: (1, 0)
(as well as sparse and dense matrices over non-prime fields)
comment:9 Changed 2 years ago by
The dense matrix is the solution to the linear system not the equations. When you solve a linear system you rarely expect a sparse solution. This is why you need an interface to dense vector and matrices.
comment:10 Changed 2 years ago by
so the error happens in conversion of the answer obtained from the backend?
comment:11 Changed 2 years ago by
No. Just read 7. The backend is never called.
comment:12 Changed 2 years ago by
Thanks. Do we actually have a specialised backend for solving sparse linear systems over GF(p), p prime?
comment:13 Changed 2 years ago by
linbox does that. Sage used to have a dirty linbox interface in Cython (in Sage) and C++ (directly implemented in linbox) that was rewritten using Cython only (everything in Sage). There is a bunch of tickets about that. The solving of sparse systems over GF(p) was overlooked. That is my fault.
comment:14 Changed 2 years ago by
- Milestone changed from sage-9.0 to sage-9.1
Ticket retargeted after milestone closed
comment:15 Changed 21 months ago by
- Milestone changed from sage-9.1 to sage-9.2
comment:16 Changed 15 months ago by
- Milestone changed from sage-9.2 to sage-9.3
comment:17 Changed 9 months ago by
- Milestone changed from sage-9.3 to sage-9.4
Moving to 9.4, as 9.3 has been released.
comment:18 Changed 5 months ago by
- Milestone changed from sage-9.4 to sage-9.5
comment:19 Changed 5 weeks ago by
- Milestone changed from sage-9.5 to sage-9.6
Corrected a typo in the sage code.