search

linbox-team / linbox

LinBox - C++ library for exact, high-performance linear algebra
https://linbox-team.github.io/linbox
GNU Lesser General Public License v2.1
83 stars 27 forks source link

solve seems broken for rectangular sparse modular matrices #105

Open videlec opened 6 years ago

videlec commented 6 years ago

Similar to #56 I have troubles with solving modular sparse systems over GF(p). More precisely when using the function solve with the following field, matrix and vector classes

Givaro::Modular<unsigned int>
LinBox::SparseMatrix<Givaro::Modular<unsigned int>, LinBox::SparseMatrixFormat::SparseSeq>
LinBox::DenseVector<Givaro::Modular<unsigned int>>

I encountered these problems trying to do better integration within SageMath (see ticket 24544).

  1. The default solve (without method specification) and BlasElimination writes System is inconsistent on the stdout (or stderr I am not sure) when the system has no solution.

  2. Wiedemann and Blackbox do not always find solution for rectangular system (this randomly might fail or not). Example tested in Sage

    • 1x3 matrix A = [[0,1,2]] and vector b = [1].
    • 2x3 matrix A = [[1,1,1],[0,1,2]] and vector b = [0, 1].

  3. SparseElimination finds solution when there is none. Tested with

    • 1x1 matrix A = [[0]] and vector b = [1]

  4. Wiedemann and Blackbox segfaults with A the zero matrix and b the zero vector (tested on 2x2 matrices)

jgdumas commented 6 years ago

test-regression now shows it for the 1x3 matrix. with -D DEBUG there are at least: sparse elim: explicit catching of non square matrix within nonsingular solve blas elim: ERROR (at next in ../linbox/algorithms/lifting-container.h:461): Precondition not met:digit.size() == _lc._matA.rowdim()

jgdumas commented 6 years ago

Also: ERROR (at operator() in ../linbox/matrix/matrixdomain/blas-matrix-domain.inl:1190): Precondition not met:A.size() == B.getOrder()

jgdumas commented 6 years ago

also with sparse elim: ERROR (at LiftingContainerBase in ../linbox/algorithms/lifting-container.h:383): Precondition not met:m == n

jgdumas commented 5 years ago

With BLAS Elimination inconsistency is well catched.

There remains 2 Isolated problems: 1/ Solve on integer system with Wiedemann, never calls solve wiedemann but switches to BLAS or SparseLU 2/ SparseDixon does not handle inconsistent systems. One should be able to use the same code used for BLAS (QLUP factorization is there for both)