Many problems in physics or other areas of science lead to solving partial differential equations or systems of partial differential equations. Many of these equations are nonlinear. The discretization of these equations lead to linear and nonlinear equations in finite dimensional euclidian spaces. Two important steps now follows:
1. Establishing existence and uniqueness criteria for the linear and nonlinear equations obtained as a result of the discretization process.
2. Establishing algorithms for finding solutions of the linear and nonlinear equations.
The second step lead to solving sparse linear systems. In the nonlinear case the problem of solving linear syastems occurs as a result of the application of the Newton method which require the inversion of the Jacobian matrix.
Very large sparse systems are now solved due to the progress of numerical simulation and also of computers'speed and increases in the amounts of memory available. Consequently, the problem of solving sparse linear systems is a problem of paramount importance for numerical computation.
The present book is a result of the lectures of the author given in Paris VI University during the period 1984-1995, and is based on research and review papers of the author written since 1982. It covers most of the best algorithms known so far for solving sparse linear systems.
Many methods for solving sparse linear systems have been invented over the years. Unfortunately, some of the older methods are not so efficient anymore when applied to very large systems and there is still the need for a very active research in this area.
During the last years, there has been a rapid development of parallel computers. The author put some emphasis on the adaptation of the known methods to parallel computations and also on the development of new parallel algorithms. He tries to cover most of the best algorithms known so far for solving sparse linear systems.
There are two main classes of algorithms used to compute the solution of a linear system: direct methods and iterative methods.
Direct methods obtain the solution after a finite number of floating point operations by doing combinations and modifications of the given equations. Of course, as computer floating point operations can only be obtained to a certain given precision, the computed solution is generally different from the exact solution, even with a direct method.
Iterative methods define a sequence of approximations that are expected to be closer and closer to the exact solution in some given norm, stopping the iterations by using some predefined criterion, obtaining a vector which is only an approximation of the solution.
The first chapter recalls some definitions, mathematical results and tools that are needed in the next chapters. The direct methods considered in the second and third chapter are different versions of Gaussian elimination. The fourth chapter is devoted to fast solvers for separable PDE. The fifth chapter studies the classical iterative methods: Jacobi, Gauss-Siedel, SOR, SSOR, alternating direction methods, Richardson, etc. Some acceleration techniques and stability problems are briefly discussed. A particular emphasis is put in the sixth chapter on the conjugate gradient and related methods. Krylov methods for non-symmetric systems are studied in the seventh chapter. Chapter 8 is devoted to the preconditioning. Most efficient preconditioners used to speed up convergence are studied. The nineth chapter presents the multigrid methods. The last chapter (the tenth) is devoted to domain decomposition algorithms that are well suited for solving linear systems on parallel computers.
At the end of each chapter are interesting historical and bibliographical comments. The book ends with a comprehensive list of references on the subject (it contains 1368 items).
The book is very well written and can be used by mathematicians, engineers as well as by graduated students interested in numerical computation.
I consider the book a marvelous introduction in the computer solution of large linear systems. The author should be congratulated for his excellent work. I enthusiastically recommend the book.
December, 1999
Dr. Marius Radulescu