Asymptotics of 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 (SGE), which selects pivots in an attempt to preserve sparseness, has been proposed as a first step in solving such systems. We propose an idealized inconsistent model for such systems and the action of SGE on them. The predictions of the model are in fair agreement with Monte Carlo computer simulations. In particular, the model predicts that most aspects scale linearly with the number of equations, including the size of the matrix obtained after SGE. Due to the density of this matrix, SGE can be iterated at most once or twice to obtain a smaller matrix. Since the model is idealized and inconsistent, none of the results are rigorous. Joint work with Rod Canfield.