This book is intended for multigrid practitioners and multigrid students: for engineers, mathematicians, physicists, chemists etc.
We will give a systematic introduction to basic and advanced multigrid. Our intention is to give sufficient detail on multigrid for model problems so that the reader can solve further applications and new problems with appropriate multigrid techniques. In addition, we will cover advanced techniques (adaptive and parallel multigrid) and we will present applications based on these new developments.
Clearly, we would not have written this book if we had thought that there was a better book that fulfilled the same purpose. No doubt, there are a number of excellent multigrid books available. However, in our opinion all the other books emphasize multigrid aspects different from those that we are interested in and which we want to emphasize.
Mathematical results that can be rigorously proved may be formulated in different ways. Practically oriented mathematicians often prefer a presentation in which the assumptions and results are motivated by some typical examples and applications. These assumptions are usually not the most general ones, and thus the results may not be the strongest that can be obtained. We prefer such a presentation of results, as we want to provide as much motivation and direct understanding as possible. However, in many cases, we add some remarks about generalizations and extensions, and about weaker assumptions.
With respect to multigrid theory, we give (elementary) proofs, wherever we regard them as helpful for multigrid practice. All the theoretical tools which we use should be understood by mathematicians, scientists and engineers who have a general background in analysis, linear algebra, numerical analysis and partial differential equations (PDEs). Wherever more sophisticated mathematical tools are needed to derive practically relevant theoretical results, we cite the appropriate literature. However, we are not interested in theory as an end in itself.
This book has three authors and, in addition, three guest authors. While the guest contributions are supposed to be fully consistent with the contents of the book and fit with its general philosophy and message, they are still independent and self-contained. The guest authors are experts in the fields they present here and they use their own style to express their views and approaches to multigrid.
The three main authors, on the other hand, have agreed on all the material that is presented in this book. They did not distribute the chapters among themselves and did not distribute the responsibility. They also agreed on the way the material is presented.
Multigrid methods are generally accepted as being the fastest numerical methods for the solution of elliptic partial differential equations. Furthermore, they are regarded as among the fastest methods for many other problems, like other types of partial differential equations, integral equations etc. If the multigrid idea is generalized to structures other than grids, one obtains multilevel, multiscale or multiresolution methods, which can also be used successfully for very different types of problems, e.g. problems which are characterized by matrix structures, particle structures, lattice structures etc. However, the literature does not have a uniform definition of the terms multigrid, multilevel etc.
This book is devoted to PDEs and to the "algebraic multigrid approach" for matrix problems. We assume that the reader has some basic knowledge of numerical methods for PDEs. This includes fundamental discretization approaches and solution methods for linear and nonlinear systems of algebraic equations. Implicitly, this also means that the reader is familiar with basics of PDEs (type classification, characteristics, separation of variables etc. see, for example, [395]) and of direct and iterative solvers for linear systems.
We will not, however, assume detailed knowledge about existence theories for PDEs, Sobolev spaces and the like. In this respect, the book is addressed to students and practitioners from different disciplines. On the other hand, in some sections, advanced applications are treated, in particular from computational fluid dynamics. For a full understanding of these applications, a basic knowledge of general PDEs may not be sufficient. In this respect, we will assume additional knowledge in these sections and we will give references to background material in the corresponding fields.
We do not assume that the reader works "linearly" with this book from the beginning to the end though this is suitable to obtain a good insight into multigrid and its relation to similar approaches. The multigrid beginner may well skip certain sections. We will lead the reader in this respect through the book, pointing out what can be skipped and what is needed.
The overall structure of the book is determined by its chapters. The first half of the book (Chapters 1-6) discusses standard multigrid, the second half (Chapters 7-10) deals with advanced approaches up to real-life applications. Accordingly, the style and presentation in the first half is more detailed. In addition to the basic techniques introduced in the first six chapters, we add many more specific remarks and algorithmical details. These may not be so interesting for beginners but should be helpful for practitioners who want to write efficient multigrid programs. Mistakes that are easily made are mentioned in several places.
The second part of the book (Chapters 7-10) is presented in a more condensed form, i.e. in a more research oriented style.
This structure of the book is also reflected by the nature of the equations and applications we deal with. There is no doubt about the fact that multigrid methods work excellently for "nicely" elliptic PDEs. This is confirmed by rigorous mathematical theory.
For typical real-life applications (PDE systems with nonelliptic features and nonlinear terms), however, such a theory is generally not available. Nevertheless, as we will see in this book, multigrid can be applied to such problems although they may not be "nicely" elliptic or even not elliptic at all. In answering the question "when does multigrid work?", we will give insight, based on 20 years of multigrid practice and multigrid software development.
