A practical handbook for understanding and using fast adaptive composite grid (FAC) methods for discretization and solution of partial differential equations (PDEs). Contains fundamental concepts. These so-called FAC are characterized by their use of a composite grid, which is nominally the union of various uniform grids. FAC is capable of producing a composite grid with tailored resolution, and a corresponding solution with commensurate accuracy, at a cost proportional to the number of composite grid points. Moreover, special asynchronous versions of the fast adaptive composite grid methods (AFAC) studied here have seemingly optimal complexity in a parallel computing environment. Most of the methods treated in this book were discovered only within the last decade, and in many cases their development is still in its infancy. While this is not meant to be comprehensive, it does provide a theoretical and practical guide to multilevel adaptive methods and relevant discretization techniques.

The multilevel projection method is a new formalism that provides a framework for the development of multilevel algorithms in a very general setting. This methodology guides the choices of all the major multilevel processes, including relaxation and coarsening, and it applies directly to global or locally-refined discretizations. This book was developed from lectures at the CBMS-NSF Regional Conference on Multigrid and Multilevel Adaptive Methods for Partial Differential Equations in June 1991, and is a supplement to Multilevel Adaptive Methods for Partial Differential Equations, also written by Stephen F. McCormick.

List of participants; Elliptic equations; Parabolic equations; Hyperbolic equations.

Nowadays there is an increasing emphasis on all aspects of adaptively gener ating a grid that evolves with the solution of a PDE. Another challenge is to develop efficient higher-order one-step integration methods which can handle very stiff equations and which allow us to accommodate a spatial grid in each time step without any specific difficulties. In this monograph a combination of both error-controlled grid refinement and one-step methods of Rosenbrock-type is presented. It is my intention to impart the beauty and complexity found in the theoretical investigation of the adaptive algorithm proposed here, in its realization and in solving non-trivial complex problems. I hope that this method will find many more interesting applications. Berlin-Dahlem, May 2000 Jens Lang Acknowledgements I have looked forward to writing this section since it is a pleasure for me to thank all friends who made this work possible and provided valuable input. I would like to express my gratitude to Peter Deuflhard for giving me the oppor tunity to work in the field of Scientific Computing. I have benefited immensly from his help to get the right perspectives, and from his continuous encourage ment and support over several years. He certainly will forgive me the use of Rosenbrock methods rather than extrapolation methods to integrate in time.

The general Method of Lines (MOL) procedure provides a flexible format for the solution of all the major classes of partial differential equations (PDEs) and is particularly well suited to evolutionary, nonlinear wave PDEs. Despite its utility, however, there are relatively few texts that explore it at a more advanced level and reflect the method's

Main aspects of the efficient treatment of partial differential equations are discretisation, multilevel/multigrid solution and parallelisation. These distinct topics are covered from the historical background to modern developments. It is demonstrated how the ingredients can be put together to give an adaptive and parallel multilevel approach for the solution of elliptic boundary value problems. Error estimators and adaptive grid refinement techniques for ordinary and for sparse grid discretisations are presented. Different types of additive and multiplicative multilevel solvers are discussed with respect to parallel implementation and application to adaptive refined grids. Efficiency issues are treated both for the sequential multilevel methods and for the parallel version by hash table storage techniques. Finally, space-filling curve enumeration for parallel load balancing and processor cache efficiency are discussed.