Solving sparse linear equations over finite fields
Doug Wiedemann · IEEE Transactions on Information Theory · 1986
A "coordinate recurrence" method for solving sparse systems of linear equations over finite fields is described. The algorithms discussed all requireO(n_{1}(\omega + n_{1})\log^{k}n_{1})field operations, wheren_{1}is the maximum dimension of the coefficient matrix,\omegais approximately the number of field operations required to apply the matrix to a test vector, and the value ofkdepends on the algorithm. A probabilistic algorithm is shown to exist for finding the determinant of a square matrix. Also, probabilistic algorithms are shown to exist for finding the minimum polynomial and rank with some arbitrarily small possibility of error.