Opened 2 years ago

broken solving a linear system over GF(3)

Reported by: Owned by: dimpase critical sage-9.6 linear algebra N/A

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

comment:1 Changed 2 years ago by gh-DaveWitteMorris

• Description modified (diff)

Corrected a typo in the sage code.

comment:2 Changed 2 years ago by gh-DaveWitteMorris

Ticket 24544 has a commit called "fix matrix_modn_sparse" (and this commit is also mentioned in ticket 23214). To a naive observer, it seems that this could be related.

comment:3 Changed 2 years ago by dimpase

#24544 got into 8.4, which is still OK (I tested on cocalc).

comment:4 Changed 2 years ago by dimpase

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 dimpase

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 vdelecroix

• Description modified (diff)

comment:7 Changed 2 years ago by vdelecroix

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
Last edited 2 years ago by vdelecroix (previous) (diff)

comment:8 Changed 2 years ago by dimpase

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)

Last edited 2 years ago by dimpase (previous) (diff)

comment:9 Changed 2 years ago by vdelecroix

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 dimpase

so the error happens in conversion of the answer obtained from the backend?

comment:11 Changed 2 years ago by vdelecroix

No. Just read 7. The backend is never called.

comment:12 Changed 2 years ago by dimpase

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 vdelecroix

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 embray

• Milestone changed from sage-9.0 to sage-9.1

Ticket retargeted after milestone closed

comment:15 Changed 21 months ago by mkoeppe

• Milestone changed from sage-9.1 to sage-9.2

comment:16 Changed 15 months ago by mkoeppe

• Milestone changed from sage-9.2 to sage-9.3

comment:17 Changed 9 months ago by mkoeppe

• 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 mkoeppe

• Milestone changed from sage-9.4 to sage-9.5

comment:19 Changed 5 weeks ago by mkoeppe

• Milestone changed from sage-9.5 to sage-9.6
Note: See TracTickets for help on using tickets.