Solving
Linear Systems
An Analysis of Matrix
Prefactorization Iterative Methods
by Zbigniew
Ignacy Woźnicki
Preface
Iterative methods for solving systems of
linear equation form a beautiful, living, and
useful field of numerical linear algebra. Beautiful, because
it is full of powerful ideas and theoretical results, and living,
because it is a rich source of well-established algorithms for accurate
solutions of many large and sparse linear systems. Useful,
because solutions of large systems of linear equations are essential in
many fields.
The recent literature on iterative methods has been dominated
by Krylov subspace methods, currently the most common group
of techniques used in applications. The combination of preconditioning
and Krylov subspace iterations for solving nonsymmetric linear systems
has become a central area of research and new techniques are still
emerging. In the vast literature there are a thousand different
algorithms, and many derivations and estimates of error
bounds; it is difficult for a typical reader or user (and
sometimes even the specialist) to identify the basic principles
involved and estimate the performance of particular algorithms.
These new techniques are called parameter-free methods, because they can be applied without
knowing the inner properties of the matrices that one must know in the case of traditional methods.
There is a general feeling that traditional iterative methods, based on
matrix splittings, are usually less efficient than the Krylov methods,
and that to use these methods effectively one must resort to rather
complicated procedures for determining optimal acceleration
parameters. Therefore, in current applications, the traditional
methods have generally been relegated to the role of
preconditioners. However, as can be concluded from numerical
experiments described in this book, such an opinion is unjustified in
many cases.
This book is devoted to the description and convergence analysis
of iterative methods based on matrix splittings and their
implementation in mesh structures. It is in some sense a summary
of the author's results and experience gained in this important field
of numerical linear algebra.
Matrix splitting iterative methods are especially attractive for
solving linear equations with nonsymmetric matrices because these methods yield more
accurate solutions, with significantly less computational work,
than Krylov subspace methods. Special attention is paid to
developing efficient techniques for {\itshape a priori} estimations of optimal
acceleration parameters, as useful tools when solving many problems of
practical interest.
The book is organized as follows. Chapter 1
summarizes fundamentals of numerical linear algebra and matrix
computations. Chapter 2 discusses matrix splitting theory, providing
comparison theorems proved for different types of splittings, as useful
tools in convergence analysis of iterative methods. Chapter 3
deals with discretization aspects of elliptic partial differential
equations. Standard iterative methods and useful procedures for
determining optimal acceleration parameters are presented in chapter 4.
Chapters 5--7 are devoted to the study of a large family of prefactorization iterative methods, introduced by the author, and divided into
three groups: explicit prefactorization algorithms,
semiexplicit algorithms with implicit backward sweep, and
semiexplicit algorithms with implicit forward sweep. Recent
advances obtained by the author for solving large Sylvester and
algebraic Riccati equations are discussed in chapter 8.
To order (United States)
To order (other countries)
Return to main page for Solving
Linear Systems |