Certifying inconsistency of sparse linear systems
Mark W. Giesbrecht, Austin A. Lobo, B. David Saunders · 1998
Randomized black b o x algorithms provide a very ecient means for solving sparse linear systems over arbitrary elds.However, when these probabilistic algorithms fail, it is not revealed whether no solution exists or whether the algorithm simply made unlucky random choices.Here we give a n ecient algorithm to compute a certi cate of inconsistency for a black b o x linear system over a eld.Our method requires a black box for the transpose of the matrix.The cost of producing the certi cate is shown to be about the same as that of solving the system in the black b o x model, while the cost of applying a given certi cate to prove inconsistency is much smaller.We also give an ecient algorithm for certifying that a sparse Diophantine linear system of integer equations has no integer solutions, even when it may h a v e rational solutions.