Direct Methods for Sparse Linear Systems (Fundamentals of Algorithms)
by Timothy A. Davis
Society for Industrial and Applied Mathematic | English | 2006 | ISBN: 0898716136 | 217 pages | PDF | 10.5 MB
table class="quote"trtd class="quote_left"“/tdtd class="quote_center"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 practice of sparse matrix algorithms, so that you will have the foundation to understand more complex (but faster) algorithms. Methods that operate on dense sub matrices of a larger sparse matrix ( multifrontal and supermodel 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=A\b 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./tdtd class="quote_right"”/td/tr/table

Download: