Certified sparse linear system solving

In (Wiedemann, 1986) an algorithm is described for solving sparse lin- ear systems over nite elds. When the system does not have the desired properties for the algorithm to work, it is preconditioned to enforce these properties. In (Kaltofen and Saunders, 1991) another way of preconditioning for this problem is described. In (Giesbrecht et al., 1998) these techniques are used to obtain an algorithm for solving diophantine sparse systems over Z, including inconsistency certication. All these algorithms need coeÆcient elds/rings of suÆcient size. Otherwise nite eld/ring extensions have to be introduced. In (Mulders and Storjohann, 2000) an extended version of the diophantine solver is developed for dense systems. In this paper we will do the same for sparse systems. The algorithms will work for elds/rings of any size, so no eld/ring extensions are needed