On Wiedemann's Method of Solving Sparse Linear Systems
Douglas Wiedemann’s (1986) landmark approach to solving sparse linear systems over finite fields provides the symbolic counterpart to non-combinatorial numerical methods for solving sparse linear systems, such as the Lanczos or conjugate gradient method (see Golub and van Loan (1983)). The problem is to solve a sparse linear system, when the individual entries lie in a generic field, and the only operations possible are field arithmetic; the solution is to be exact. Such is the situation, for instance, if one works in a finite field. Wiedemann bases his approach on Krylov subspaces, but projects further to a sequence of individual field elements. By making a link to the Berlekamp/Massey problem from coding theory — the coordinate recurrences — and by using randomization an algorithm is obtained with the following property. On input of an n×n coefficient matrix A given by a so-called black box, which is a program that can multiply the matrix by a vector (see Figure 1), and of a vector b, the algorithm finds, with high probability in case the system is solvable, a random solution vector x with Ax = b. It is assumed that the field has sufficiently many elements, say no less than 50n log(n), otherwise one goes to a finite algebraic extension. The complexity of the method is in the general singular case O(n log(n)) calls to the black box for A and an additional O(n log(n)) field arithmetic operations. Note that the black box model for matrix sparsity is a significant abstraction. For a matrix that has an abundance of zero entries, multiplying the matrix by a vector may cost no more than O(n) field operations, in which case the algorithm becomes almost quadratic. However, the model also applies to structured matrices with few or no zero entries, such as Toeplitzand Vandermonde-like matrices, or matrices that correspond to resultants (Canny