Building an Old-Fashioned Sparse Solver

A sparse matrix is a matrix with very few nonzero elements. Manyapplications in diverse fields give rise to linear systems of the form
$Ax = b$, where $A$ is sparse. The problem in solving these systems
is to take advantage of the preponderance of zero elements to reduce
both memory use and comutation time. The purpose of this paper is to
introduce students (and perhaps their teachers) to sparse matrix
technology. It is impossible to treat all the techniques developed
since the subject started in the 1960's. Instead, this paper
constructs a sparse solver for positive definite systems that would
have been state of the art around 1980, emphasizing equally theory and
computational practice. It is hoped that a mastery of this material
will allow the reader to study the subject independently.
(UMIACS-TR-2003-95)