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...

Full description

Saved in:
Bibliographic Details
Published in:Journal of algorithms 1999-05, Vol.31 (2), p.271-290
Main Authors: Bender, Edward A, Canfield, E.Rodney
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Computer science
control theory
systems
Exact sciences and technology
Mathematics
Numerical analysis
Numerical analysis. Scientific computation
Numerical linear algebra
Sciences and techniques of general use
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0196-6774
1090-2678
DOI:10.1006/jagm.1999.1008