Direct Methods for Sparse Linear Systems







Preface

This book presents the fundamentals of sparse matrix algorithms, from theory

to algorithms and data structures to working code. The focus is on direct methods

for solving systems of linear equations; iterative methods and solvers for eigenvalue

problems are beyond the scope of this book.

The goal is to impart a working knowledge of the underlying theory and prac-

tice of sparse matrix algorithms, so that you will have the foundation to understand

more complex (but faster) algorithms. Methods that operate on dense submatrices

of a larger sparse matrix (multifrontal and supernodal methods) are much faster, but

a complete sparse matrix package based on these methods can be tens of thousands

of lines long. The sparse LU, Cholesky, and QR factorization codes in MATLAB®,

for example, total about 100,000 lines of code. Trying to understand the sparse

matrix technique by starting with such huge codes is a daunting task. To overcome

this obstacle, a sparse matrix package, CSparse,1 has been written specifically for

this book.2 It can solve Ax = b when A is unsymmetric, symmetric positive definite,

or rectangular, using about 2,200 lines of code. Although simple and concise,

it is based on recently developed methods and theory. All of CSparse is printed in

this book. Take your time to read and understand these codes; do not gloss over

them. You will find them much easier to comprehend and learn from than their larger

(yet faster) cousins. The larger packages you may use in practice

are based on much of the theory and some of the algorithms presented more concisely and

simply in CSparse. For example, the MATLAB statement x=Ab relies on the theory

and algorithms from almost every section of this book. Parallel

sparse matrix algorithms are excluded, yet they too rely on the theory discussed here.

For the computational scientist with a problem to solve using sparse matrix

methods, these larger packages may be faster, but you need to understand how

they work to use them effectively. They might not have every function needed to

interface them into your application. You may need to write some code of your own

to manipulate your matrix prior to or after using a large sparse matrix package.

One of the goals of this book is to equip you for these tasks. The same question

applies to MATLAB. You might ask, "What is the most efficient way of solving

my sparse matrix problem in MATLAB?" The short answer is to always operate on

whole matrices, large submatrices, or column vectors in MATLAB and to not rely



Download

*