Numerical Analysis 2000 – serie

/homepage/sac/cam/na2000/index.html7-Volume Set now available at special set price !Over the second half of the 20th century the subject area loosely referred to as numerical analysis of partial differential equations (PDEs) has undergone unprecedented development. At its practical end, the vigorous growth and steady diversification of the field were stimulated by the demand for accurate and reliable tools for computational modelling in physical sciences and engineering, and by the rapid development of computer hardware and architecture. At the more theoretical end, the analytical insight into the underlying stability and accuracy properties of computational algorithms for PDEs was deepened by building upon recent progress in mathematical analysis and in the theory of PDEs. To embark on a comprehensive review of the field of numerical analysis of partial differential equations within a single volume of this journal would have been an impossible task. Indeed, the 16 contributions included here, by some of the foremost world authorities in the subject, represent only a small sample of the major developments. We hope that these articles will, nevertheless, provide the reader with a stimulating glimpse into this diverse, exciting and important field. The opening paper by Thomée reviews the history of numerical analysis of PDEs, starting with the 1928 paper by Courant, Friedrichs and Lewy on the solution of problems of mathematical physics by means of finite differences. This excellent survey takes the reader through the development of finite differences for elliptic problems from the 1930s, and the intense study of finite differences for general initial value problems during the 1950s and 1960s. The formulation of the concept of stability is explored in the Lax equivalence theorem and the Kreiss matrix lemmas. Reference is made to the introduction of the finite element method by structural engineers, and a description is given of the subsequent development and mathematical analysis of the finite element method with piecewise polynomial approximating functions. The penultimate section of Thomée's survey deals with `other classes of approximation methods', and this covers methods such as collocation methods, spectral methods, finite volume methods and boundary integral methods. The final section is devoted to numerical linear algebra for elliptic problems. The next three papers, by Bialecki and Fairweather, Hesthaven and Gottlieb and Dahmen, describe, respectively, spline collocation methods, spectral methods and wavelet methods. The work by Bialecki and Fairweather is a comprehensive overview of orthogonal spline collocation from its first appearance to the latest mathematical developments and applications. The emphasis throughout is on problems in two space dimensions. The paper by Hesthaven and Gottlieb presents a review of Fourier and Chebyshev pseudospectral methods for the solution of hyperbolic PDEs. Particular emphasis is placed on the treatment of boundaries, stability of time discretisations, treatment of non-smooth solutions and multidomain techniques. The paper gives a clear view of the advances that have been made over the last decade in solving hyperbolic problems by means of spectral methods, but it shows that many critical issues remain open. The paper by Dahmen reviews the recent rapid growth in the use of wavelet methods for PDEs. The author focuses on the use of adaptivity, where significant successes have recently been achieved. He describes the potential weaknesses of wavelet methods as well as the perceived strengths, thus giving a balanced view that should encourage the study of wavelet methods. Aspects of finite element methods and adaptivity are dealt with in the three papers by Cockburn, Rannacher and Suri. The paper by Cockburn is concerned with the development and analysis of discontinuous Galerkin (DG) finite element methods for hyperbolic problems. It reviews the key properties of DG methods for nonlinear hyperbolic conservation laws from a novel viewpoint that stems from the observation that hyperbolic conservation laws are normally arrived at via model reduction, by elimination of dissipation terms. Rannacher's paper is a first-rate survey of duality-based a posteriori error estimation and mesh adaptivity for Galerkin finite element approximations of PDEs. The approach is illustrated for simple examples of linear and nonlinear PDEs, including also an optimal control problem. Several open questions are identified such as the efficient determination of the dual solution, especially in the presence of oscillatory solutions. The paper by Suri is a lucid overview of the relative merits of the hp and p versions of the finite element method over the h version. The work is presented in a non-technical manner by focusing on a class of problems concerned with linear elasticity posed on thin domains. This type of problem is of considerable practical interest and it generates a number of significant theoretical problems. Iterative methods and multigrid techniques are reviewed in a paper by Silvester, Elman, Kay and Wathen, and in three papers by Stüben, Wesseling and Oosterlee and Xu. The paper by Silvester et al. outlines a new class of robust and efficient methods for solving linear algebraic systems that arise in the linearisation and operator splitting of the Navier-Stokes equations. A general preconditioning strategy is described that uses a multigrid V-cycle for the scalar convection-diffusion operator and a multigrid V-cycle for a pressure Poisson operator. This two-stage approach gives rise to a solver that is robust with respect to time-step-variation and for which the convergence rate is independent of the grid. The paper by Stüben gives a detailed overview of algebraic multigrid. This is a hierarchical and matrix-based approach to the solution of large, sparse, unstructured linear systems of equations. It may be applied to yield efficient solvers for elliptic PDEs discretised on unstructured grids. The author shows why this is likely to be an active and exciting area of research for several years in the new millennium. The paper by Wesseling and Oosterlee reviews geometric multigrid methods, with emphasis on applications in computational fluid dynamics (CFD). The paper is not an introduction to multigrid: it is more appropriately described as a refresher paper for practitioners who have some basic knowledge of multigrid methods and CFD. The authors point out that textbook multigrid efficiency cannot yet be achieved for all CFD problems and that the demands of engineering applications are focusing research in interesting new directions. Semi-coarsening, adaptivity and generalisation to unstructured grids are becoming more important. The paper by Xu presents an overview of methods for solving linear algebraic systems based on subspace corrections. The method is motivated by a discussion of the local behaviour of high-frequency components in the solution of an elliptic problem. Of novel interest is the demonstration that the method of subspace corrections is closely related to von Neumann's method of alternating projections. This raises the question as to whether certain error estimates for alternating directions that are available in the literature may be used to derive convergence estimates for multigrid and/or domain decomposition methods. Moving finite element methods and moving mesh methods are presented, respectively, in the papers by Baines and Huang and Russell. The paper by Baines reviews recent advances in Galerkin and least-squares methods for solving first- and second-order PDEs with moving nodes in multidimensions. The methods use unstructured meshes and they minimise the norm of the residual of the PDE over both the computed solution and the nodal positions. The relationship between the moving finite element method and L2 least-squares methods is discussed. The paper also describes moving finite volume and discrete l2 least-squares methods. Huang and Russell review a class of moving mesh algorithms based upon a moving mesh partial differential equation (MMPDE). The authors are leading players in this research area, and the paper is largely a review of their own work in developing viable MMPDEs and efficient solution strategies. The remaining three papers in this special issue are by Budd and Piggott, Ewing and Wang and van der Houwen and Sommeijer. The paper by Budd and Piggott on geometric integration is a survey of adaptive methods and scaling invariance for discretisations of ordinary and partial differential equations. The authors have succeeded in presenting a readable account of material that combines abstract concepts and practical scientific computing. Geometric integration is a new and rapidly growing area which deals with the derivation of numerical methods for differential equations that incorporate qualitative information in their structure. Qualitative features that may be present in PDEs might include symmetries, asymptotics, invariants or orderings and the objective is to take these properties into account in deriving discretisations. The paper by Ewing and Wang gives a brief summary of numerical methods for advection-dominated PDEs. Models arising in porous medium fluid flow are presented to motivate the study of the advection-dominated flows. The numerical methods reviewed are applicable not only to porous medium flow problems but second-order PDEs with dominant hyperbolic behaviour in general. The paper by van der Houwen and Sommeijer deals with approximate factorisation for time-dependent PDEs. The paper begins with some historical notes and it proceeds to present various approximate factorisation techniques. The objective is to show that the linear system arising from linearisation and discretisation of the PDE may be solved more efficiently if the coefficient matrix is replaced by an approximate factorisation based on splitting. The paper presents a number of new stability results obtained by the group at CWI Amsterdam for the resulting time integration methods.