An Approximate Probabilistic Model for Structured Gaussian Elimination

Many of the fast methods for factoring integers and computing discrete logarithms require the solution of large sparse linear systems of equations over finite fields. Structured Gaussian elimination has been proposed as a first step in solving such sparse systems. It is a method for selecting pivots in an attempt to preserve the sparseness of the coefficient matrix. Eventually it terminates with a (smaller) residual linear system which must be solved by some other method. In many cases, the original column density is roughly proportional to the reciprocal of the of the column index. We discuss the asymptotic behavior of structured Gaussian elimination for this situation. One result is the observation that, for the column density just mentioned, the size of the residual system grows linearly with the size of the problem. This makes it possible to extrapolate the results of Monte Carlo simulation to much larger problems.