In the second edition of this classic monograph, complete with four new chapters and updated references, readers will now have access to content describing and analysing classical and modern methods with emphasis on the algebraic structure of linear iteration, which is usually ignored in other literature. The necessary amount of work increases dramatically with the size of systems, so one has to search for algorithms that most efficiently and accurately solve systems of, e.g., several million equations. The choice of algorithms depends on the special properties the matrices in practice have. An important class of large systems arises from the discretization of partial differential equations. In this case, the matrices are sparse (i.e., they contain mostly zeroes) and well-suited to iterative algorithms. The first edition of this book grew out of a series of lectures given by the author at the Christian-Albrecht University of Kiel to students of mathematics. The second edition includes quite novel approaches.

In April 2007, the Deutsche Forschungsgemeinschaft (DFG) approved the Priority Program 1324 "Mathematical Methods for Extracting Quantifiable Information from Complex Systems." This volume presents a comprehensive overview of the most important results obtained over the course of the program. Mathematical models of complex systems provide the foundation for further technological developments in science, engineering and computational finance. Motivated by the trend toward steadily increasing computer power, ever more realistic models have been developed in recent years. These models have also become increasingly complex, and their numerical treatment poses serious challenges. Recent developments in mathematics suggest that, in the long run, much more powerful numerical solution strategies could be derived if the interconnections between the different fields of research were systematically exploited at a conceptual level. Accordingly, a deeper understanding of the mathematical foundations as well as the development of new and efficient numerical algorithms were among the main goals of this Priority Program. The treatment of high-dimensional systems is clearly one of the most challenging tasks in applied mathematics today. Since the problem of high-dimensionality appears in many fields of application, the above-mentioned synergy and cross-fertilization effects were expected to make a great impact. To be truly successful, the following issues had to be kept in mind: theoretical research and practical applications had to be developed hand in hand; moreover, it has proven necessary to combine different fields of mathematics, such as numerical analysis and computational stochastics. To keep the whole program sufficiently focused, we concentrated on specific but related fields of application that share common characteristics and as such, they allowed us to use closely related approaches.

In this book, the author compares the meaning of stability in different subfields of numerical mathematics. Concept of Stability in numerical mathematics opens by examining the stability of finite algorithms. A more precise definition of stability holds for quadrature and interpolation methods, which the following chapters focus on. The discussion then progresses to the numerical treatment of ordinary differential equations (ODEs). While one-step methods for ODEs are always stable, this is not the case for hyperbolic or parabolic differential equations, which are investigated next. The final chapters discuss stability for discretisations of elliptic differential equations and integral equations. In comparison among the subfields we discuss the practical importance of stability and the possible conflict between higher consistency order and stability.

This self-contained monograph presents matrix algorithms and their analysis. The new technique enables not only the solution of linear systems but also the approximation of matrix functions, e.g., the matrix exponential. Other applications include the solution of matrix equations, e.g., the Lyapunov or Riccati equation. The required mathematical background can be found in the appendix. The numerical treatment of fully populated large-scale matrices is usually rather costly. However, the technique of hierarchical matrices makes it possible to store matrices and to perform matrix operations approximately with almost linear cost and a controllable degree of approximation error. For important classes of matrices, the computational cost increases only logarithmically with the approximation error. The operations provided include the matrix inversion and LU decomposition. Since large-scale linear algebra problems are standard in scientific computing, the subject of hierarchical matrices is of interest to scientists in computational mathematics, physics, chemistry and engineering.

In April 2007, the Deutsche Forschungsgemeinschaft (DFG) approved the Priority Program 1324 "Mathematical Methods for Extracting Quantifiable Information from Complex Systems." This volume presents a comprehensive overview of the most important results obtained over the course of the program. Mathematical models of complex systems provide the foundation for further technological developments in science, engineering and computational finance. Motivated by the trend toward steadily increasing computer power, ever more realistic models have been developed in recent years. These models have also become increasingly complex, and their numerical treatment poses serious challenges. Recent developments in mathematics suggest that, in the long run, much more powerful numerical solution strategies could be derived if the interconnections between the different fields of research were systematically exploited at a conceptual level. Accordingly, a deeper understanding of the mathematical foundations as well as the development of new and efficient numerical algorithms were among the main goals of this Priority Program. The treatment of high-dimensional systems is clearly one of the most challenging tasks in applied mathematics today. Since the problem of high-dimensionality appears in many fields of application, the above-mentioned synergy and cross-fertilization effects were expected to make a great impact. To be truly successful, the following issues had to be kept in mind: theoretical research and practical applications had to be developed hand in hand; moreover, it has proven necessary to combine different fields of mathematics, such as numerical analysis and computational stochastics. To keep the whole program sufficiently focused, we concentrated on specific but related fields of application that share common characteristics and as such, they allowed us to use closely related approaches.

In this book, the author compares the meaning of stability in different subfields of numerical mathematics.

Concept of Stability in numerical mathematics opens by examining the stability of finite algorithms. A more precise definition of stability holds for quadrature and interpolation methods, which the following chapters focus on. The discussion then progresses to the numerical treatment of ordinary differential equations (ODEs). While one-step methods for ODEs are always stable, this is not the case for hyperbolic or parabolic differential equations, which are investigated next. The final chapters discuss stability for discretisations of elliptic differential equations and integral equations.

In comparison among the subfields we discuss the practical importance of stability and the possible conflict between higher consistency order and stability.

"

Englischer Text: The volume contains 21 contributions to the 12th GAMM-Seminar (Kiel, January 1996), which was devoted to advanced algorithms in the field of boundary element methods. The topics were e. g. cubature techniques, multiscale methods, hp-discretisation, error estimation, domain decomposition, and programm design. Deutscher Text: Der Band enthalt die 21 Beitrage zum 12. GAMM-Seminar (Kiel, Jaunuar 1996), welches sich mit fortgeschrittenen Algorithmen auf dem Gebiet der Randwertprobleme befasste.

The coupling considered in this volume may be of physical or numerical nature. Examples of the first kind are the solid-fluid interactions, microelectronic systems, and the coupled modelling in groundwater flow. Examples of the latter kind are the domain or subspace decomposition, the local defect correction method, and the very important FEM-BEM coupling.

Special numerical techniques are already needed to deal with nxn matrices for large n.Tensor data are of size nxnx...xn=n DEGREESd, where n DEGREESd exceeds the computer memory by far. They appear for problems of high spatial dimensions. Since standard methods fail, a particular tensor calculus is needed to treat such problems. The monograph describes the methods how tensors can be practically treated and how numerical operations can be performed. Applications are problems from quantum chemistry, approximation of multivariate functions, solution of pde, e.g., with stochastic coefficie

The theory of integral equations has been an active research field for many years and is based on analysis, function theory, and functional analysis. On the other hand, integral equations are of practical interest because of the "boundary integral equation method", which transforms partial differential equations on a domain into integral equations over its boundary. This book grew out of a series of lectures given by the author at the Ruhr-Universitat Bochum and the Christian-Albrecht-Universitat zu Kiel to students of mathematics. The contents of the first six chapters correspond to an intensive lecture course of four hours per week for a semester. Readers of the book require background from analysis and the foundations of numeri cal mathematics. Knowledge of functional analysis is helpful, but to begin with some basic facts about Banach and Hilbert spaces are sufficient. The theoretical part of this book is reduced to a minimum; in Chapters 2, 4, and 5 more importance is attached to the numerical treatment of the integral equations than to their theory. Important parts of functional analysis (e. g. , the Riesz-Schauder theory) are presented without proof. We expect the reader either to be already familiar with functional analysis or to become motivated by the practical examples given here to read a book about this topic. We recall that also from a historical point of view, functional analysis was initially stimulated by the investigation of integral equations.

C. F. GauS in a letter from Dec. 26, 1823 to Gerling: 3c~ empfe~le 3~nen biegen IDlobu9 aur 9tac~a~mung. ec~werlic~ werben eie ie wieber bi- reet eliminiren, wenigftens nic~t, wenn eie me~r als 2 Unbefannte ~aben. :Da9 inbirecte 93erfa~ren 109st sic~ ~alb im ec~lafe ausfii~ren, ober man fann wo~renb be9gelben an anbere :Dinge benfen. [CO F. GauS: Werke vol. 9, Gottingen, p. 280, 1903] What difference exists between solving large and small systems of equations? The standard methods well-known to any student oflinear algebra are appli- cable to all systems, whether large or small. The necessary amount of work, however, increases dramatically with the size, so one has to search for algo- rithms that most efficiently and accurately solve systems of 1000, 10,000, or even one million equations. The choice of algorithms depends on the special properties the matrices in practice have. An important class of large systems arises from the discretisation of partial differential equations. In this case, the matrices are sparse (i. e. , they contain mostly zeros) and well-suited to iterative algorithms. Because of the background in partial differential equa- tions, this book is closely connected with the author's Theory and Numerical Treatment of Elliptic Differential Equations, whose English translation has also been published by Springer-Verlag. This book grew out of a series of lectures given by the author at the Christian-Albrecht University of Kiel to students of mathematics.

The contributions in this book by leading international experts in the field of electromagnetic field computation cover a wide area of contemporary research activities. They clearly underline the important role of modeling, analysis and numerical methods to provide powerful tools for the simulation of electromagnetic phenomena. The main topics range from the mathematical analysis of Maxwell's equations including its proper spatial discretizations (edge elements, boundary element methods, finite integration), and efficient iterative solution techniques (multigrid, domain decomposition) to multiscale aspects in micromagnetics. The reader will get acquainted with many facets of modern computational techniques and its applications to relevant problems in electromagnetism.

This volume contains a selection from the papers presented at the Fifth European Multigrid Conference, held in Stuttgart, October 1-4, 1996. There were 88 registered participants from 14 different countries worldwide, and 65 lectures were given. Earlier European Multigrid Conferences were held in Cologne in 1981 and 1985, in Bonn in 1990, and in Amsterdam in 1993. The next European Conference is planned in 1999 in Gent. The European Multigrid Conference '96 was organized by the Institut fUr Computer- anwendungen (ICA) of Stuttgart University, in cooperation with the GAMM Com- mittee for "Scientific Computing", SFB 359 and 404 and the research network WiR Ba- Wii. The list of topics contained lectures on Multigrid Methods: robustness, adaptivity, wavelets, parallelization, application in computational fluid dynamics, porous media flow, optimisation and computational mechanics. A considerable part of the talks fo- cused on algebraic multigrid methods. The remaining contributions will be published by the Institut fUr Computeranwen- dungen (ICA) in Stuttgart in a special ICA report. Special thanks are due to Oktavia Klassen, who carefully compiled the contributions to this volume.

The GAMM Committee for "Efficient Numerical Methods for Partial Differential Equations" organises seminars on subjects concerning the algorithmic treatment of par tial differential equations. The topics are discretisation methods like the finite element and the boundary element method for various types of applications in structural and fluid mechanics. Particular attention is devoted to the advanced solution methods. The series of such seminars was continued in 1994, January 14-16, with the 10th Kiel-Seminar on the special topic Fast Solvers for Flow Problems at the Christian-Albrechts-University of Kiel. The seminar was attended by 100 scientist from 9 countries. 23 lectures were given, including two invited survey lectures. The central topic of most of the contributions are the Navier-Stokes equations. The authors discuss robust methods, parallel implementations, defect correction techniques, adaptive methods including error estimators, domain decompositions and FEM-BEM coupling. The invited lectures concern the hierarchical multigrid method for unstruc tured grids and structured adaptive finite-volume multigrid for compressible flows."

The theory of integral equations has been an active research field for many years and is based on analysis, function theory, and functional analysis. On the other hand, integral equations are of practical interest because of the -boundary integral equation method-, which transforms partial differential equations on a domain into integral equations over its boundary. This book grew out of a series of lectures given by the author at the Ruhr-Universitat Bochum and the Christian-Albrecht-Universitat zu Kiel to students of mathematics. The contents of the first six chapters correspond to an intensive lecture course of four hours per week for a semester. Readers of the book require background from analysis and the foundations of numeri cal mathematics. Knowledge of functional analysis is helpful, but to begin with some basic facts about Banach and Hilbert spaces are sufficient. The theoretical part of this book is reduced to a minimum; in Chapters 2, 4, and 5 more importance is attached to the numerical treatment of the integral equations than to their theory. Important parts of functional analysis (e. g., the Riesz-Schauder theory) are presented without proof. We expect the reader either to be already familiar with functional analysis or to become motivated by the practical examples given here to read a book about this topic. We recall that also from a historical point of view, functional analysis was initially stimulated by the investigation of integral equations."

The GAMM Committee for "Efficient Numerical Methods for Partial Differential Equations" organizes workshops on subjects concerning the algorithmical treat ment of partial differential equations. The topics are discretization methods like the finite element and finite volume method for various types of applications in structural and fluid mechanics. Particular attention is devoted to advanced solu tion techniques. th The series of such workshops was continued in 1993, January 22-24, with the 9 Kiel-Seminar on the special topic "Adaptive Methods Algorithms, Theory and Applications" at the Christian-Albrechts-University of Kiel. The seminar was attended by 76 scientists from 7 countries and 23 lectures were given. The list of topics contained general lectures on adaptivity, special discretization schemes, error estimators, space-time adaptivity, adaptive solvers, multi-grid me thods, wavelets, and parallelization. Special thanks are due to Michael Heisig, who carefully compiled the contribu tions to this volume. November 1993 Wolfgang Hackbusch Gabriel Wittum v Contents Page A. AUGE, G. LUBE, D. WEISS: Galerkin/Least-Squares-FEM and Ani- tropic Mesh Refinement. 1 P. BASTIAN, G. WmUM: Adaptive Multigrid Methods: The UG Concept. 17 R. BEINERT, D. KRONER: Finite Volume Methods with Local Mesh Alignment in 2-D. 38 T. BONK: A New Algorithm for Multi-Dimensional Adaptive Nume- cal Quadrature. 54 F. A. BORNEMANN: Adaptive Solution of One-Dimensional Scalar Conservation Laws with Convex Flux. 69 J. CANU, H. RITZDORF: Adaptive, Block-Structured Multigrid on Local Memory Machines. 84 S. DAHLKE, A. KUNaTH: Biorthogonal Wavelets and Multigrid. 99 B. ERDMANN, R. H. W. HOPPE, R."

This volume contains 22 papers presented at the Kiel Seminar in 1992. The Kiel Seminars are well known, and cover special areas in numerical methods for partial differential equations, numerical linear algebra, numerical methods for integral equations and related areas. The papers cover a broad range of topics from mathematical theory to practical applications of incomplete decompositions as smoothers in multi-grid methods, as preconditioners for conjugate gradient-type methods and the use of ILU for systems of partial differential equations.

The most frequently used method for the numerical integration of parabolic differential equa tions is the method of lines, where one first uses a discretization of space derivatives by finite differences or finite elements and then uses some time-stepping method for the the solution of resulting system of ordinary differential equations. Such methods are, at least conceptually, easy to perform. However, they can be expensive if steep gradients occur in the solution, stability must be controlled, and the global error control can be troublesome. This paper considers a simultaneaus discretization of space and time variables for a one-dimensional parabolic equation on a relatively long time interval, called 'time-slab'. The discretization is repeated or adjusted for following 'time-slabs' using continuous finite element approximations. In such a method we utilize the efficiency of finite elements by choosing a finite element mesh in the time-space domain where the finite element mesh has been adjusted to steep gradients of the solution both with respect to the space and the time variables. In this way we solve all the difficulties with the classical approach since stability, discretization error estimates and global error control are automatically satisfied. Such a method has been discussed previously in 3] and 4]. The related boundary value techniques or global time integration for systems of ordinary differential equations have been discussed in several papers, see 12] and the references quoted therein."

In full multigrid methods for elliptic difference equations one works on a sequence of meshes where a number of pre- and/or postsmoothing steps are performed on each level. As is well known these methods can converge very fast on problems with a smooth solution and a regular mesh, but the rate of convergence can be severely degraded for problems with unisotropy or discontinuous coefficients unless some form of robust smoother is used. Also problems can arise with the increasingly coarser meshes because for some types of discretization methods, coercivity may be lost on coarse meshes and on massively parallel computers the computation cost of transporting information between computer processors devoted to work on various levels of the mesh can dominate the whole computing time. For discussions about some of these problems, see (11). Here we propose a method that uses only two levels of meshes, the fine and the coarse level, respec tively, and where the corrector on the coarse level is equal to a new type of preconditioner which uses an algebraic substructuring of the stiffness matrix. It is based on the block matrix tridiagonal structure one gets when the domain is subdivided into strips. This block-tridiagonal form is used to compute an approximate factorization whereby the Schur complements which arise in the recursive factorization are approximated in an indirect way, i. e."

The GAMM Committee for Efficient Numerical Methods for Par tial Differential Equations (GAMM-FachausschuB "Effiziente numerische Verfahren fUr partielle Differenzialgleichungen") organizes conferences and seminars on subjects concerning the algorithmic treatment of partial differential equation prob lems. The first seminar "Efficient Solution of Elliptic Systems" was followed by a second one held at the University of Kiel from January 17th to January 19th, 1986. The title was "Efficient Numerical Methods in Continuum Mechanics." The equations arising in continuum mechanics have many con nections to those of fluid mechanics, but are usually more complex. Therefore, much attention has to be paid to the ef ficient discretization, postprocessing and extrapolation. The seminar was attended by 66 scientists from 10 countries. Most of the 21 lectures presented at the seminar treated the discretization of equations in continuum mechanics by finite elements, methods for improving the accuracy of these approx imations and the use of boundary elements. Other contribu tions presented efficient methods for investigating bifurca tions which play an essential role in practical applications. These proceedings contain 11 contributions in alphabetical order. The editors and organizers of the seminar would like to thank the land Schleswig-Holstein and the DFG (Deutsche Forschungs gemeinschaft) for their support. Kiel, November 1986 W. Hackbusch K. Witsch v Contents Page K. ERIKSSON, C. JOHNSON, J. LENNBLAD: Optimal error estimates and adaptive time and space step control for linear parabolic problems ....................... ."

In the second edition of this classic monograph, complete with four new chapters and updated references, readers will now have access to content describing and analysing classical and modern methods with emphasis on the algebraic structure of linear iteration, which is usually ignored in other literature. The necessary amount of work increases dramatically with the size of systems, so one has to search for algorithms that most efficiently and accurately solve systems of, e.g., several million equations. The choice of algorithms depends on the special properties the matrices in practice have. An important class of large systems arises from the discretization of partial differential equations. In this case, the matrices are sparse (i.e., they contain mostly zeroes) and well-suited to iterative algorithms. The first edition of this book grew out of a series of lectures given by the author at the Christian-Albrecht University of Kiel to students of mathematics. The second edition includes quite novel approaches.

Das Vieweg+Teubner Taschenbuch der Mathematik erfullt aktuell, umfassend und kompakt alle Erwartungen, die an ein mathematisches Nachschlagewerk gestellt werden. Es vermittelt ein lebendiges und modernes Bild der heutigen Mathematik. Als Taschenbuch begleitet es die Bachelor-Studierenden vom ersten Semester bis zur letzten Prufung und der Praktiker nutzt es als standiges und unentbehrliches Nachschlagewerk in seinem Berufsalltag. Das Taschenbuch bietet alles, was in Bachelor-Studiengangen im Haupt- und Nebenfach Mathematik benotigt wird. Der Text fur diese Ausgabe wurde stark uberarbeitet. Zu spezielle Inhalte wurden herausgenommen und dafur Themen der Wirtschaftsmathematik und Algorithmik hinzugenommen. Das Vieweg+Teubner Handbuch der Mathematik (eAusgabe) enthalt daruberhinaus erganzendes und weiterfuhrendes Material fur das
Masterstudium.
"

Special numerical techniques are already needed to deal with n x n matrices for large n. Tensor data are of size n x n x...x n=nd, where nd exceeds the computer memory by far. They appear for problems of high spatial dimensions. Since standard methods fail, a particular tensor calculus is needed to treat such problems. This monograph describes the methods by which tensors can be practically treated and shows how numerical operations can be performed. Applications include problems from quantum chemistry, approximation of multivariate functions, solution of partial differential equations, for example with stochastic coefficients, and more. In addition to containing corrections of the unavoidable misprints, this revised second edition includes new parts ranging from single additional statements to new subchapters. The book is mainly addressed to numerical mathematicians and researchers working with high-dimensional data. It also touches problems related to Geometric Algebra.