区域分解方法（DDM）.pdf-资料库

第1页 / 共454页

第2页 / 共454页

第3页 / 共454页

第4页 / 共454页

第5页 / 共454页

第6页 / 共454页

第7页 / 共454页

第8页 / 共454页

34 Springer Series in Computational Mathematics Editorial Board R. Bank, La Jolla, (CA) R.L. Graham, La Jolla, (CA) J. Stoer, Würzburg R. Varga, Kent, (Ohio) H. Yserentant, Berlin

Andrea Toselli Olof Widlund DomainDecomposition Methods – Algorithms and Theory With 33 Figures 123

Andrea Toselli ETH Zentrum Seminar for Applied Mathematics Rämistrasse 101 8092 Zürich Switzerland email: toselli@sam.math.ethz.ch Olof B. Widlund Courant Institute of Mathematical Sciences 251 Mercer Street New York, NY 10012 USA e-mail: widlund@cims.nyu.edu Library of Congress Control Number: 2004113304 Mathematics Subject Classiﬁcation (2000): 65F10 65N22 65N30 65N55 ISSN 0179-3632 ISBN 978-3-540-20696-5 Springer Berlin Heidelberg New York This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable for prosecution under the German Copyright Law. Springer is a part of Springer Science+Business Media springeronline.com © Springer-Verlag Berlin Heidelberg 2005 The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Cover design: design&production, Heidelberg Typeset by the authors using a Springer LATEX macro package Production: LE-TEX Jelonek, Schmidt & Vöckler GbR, Leipzig Printed on acid-free paper 46/3142YL-5 4 3 2 1 0

Preface The purpose of this text is to offer a comprehensive and self-contained pre sentation of some of the most successful and popular domain decomposition methods for partial differential equations. Strong emphasis is put on both al gorithmic and mathematical aspects. In addition, we have wished to present a number of methods that have not been treated previously in other mono graphs and surveys. We believe that this monograph will offer something new and that it will complement those of Smith, Bj0rstad, and Gropp [424] and Quarteroni and Valli [392]. Our monograph is also more extensive and broader than the surveys given in Chan and Mathew [132], Farhat and Roux [201], Le Tallec [308], the habilitation thesis by Wohlmuth [469], and the well-known SIAM Review articles by Xu [472] and Xu and Zou [476]. Domain decomposition generally refers to the splitting of a partial differen tial equation, or an approximation thereof, into coupled problems on smaller subdomains forming a partition of the original domain. This decomposition may enter at the continuous level, where different physical models may be used in different regions, or at the discretization level, where it may be con venient to employ different approximation methods in different regions, or in the solution of the algebraic systems arising from the approximation of the partial differential equation. These three aspects are very often interconnected in practice. This monograph is entirely devoted to the third aspect of domain decompo sition. In practical applications, finite element or other discretizations reduces the problem to the solution of an often huge algebraic system of equations. Direct factorization of such systems might then not be a viable option and the use of basic iterative methods, such as the conjugate gradient algorithm, can result in very slow convergence. The basic idea of domain decomposition is that instead of solving one huge problem on a domain, it may be conve nient (or necessary) to solve many smaller problems on single subdomains a certain number of times. Much of the work in domain decomposition relates to the selection of subproblems that ensure that the rate of convergence of the

VI Preface new iterative method is fast. In other words, domain decomposition methods provide preconditioners that can be accelerated by Krylov space methods. The development of the field, and the increased interest in domain decom position methods, is closely related to the growth of high speed computing. We note that in the June 2004 edition of the "Top 500" list, there are no fewer than 242 computer systems sustaining at least 1.0 Teraflop/sec. Scien tific computing is therefore changing very fast and many scientists are now developing codes for parallel and distributed systems. The development of numerical methods for large algebraic systems is cen tral in the development of efficient codes for computational fluid dynamics, elasticity, and other core problems of continuum mechanics. Many other tasks in such codes parallelize relatively easily. The importance of the algebraic system solvers is therefore increasing with the appearance of new computing systems, with a substantial number of fast processors, each with relatively large memory. In addition, robust algebraic solvers for many practical prob lems and discretizations cannot be constructed by simple algebraic techniques, such as approximate inverses or incomplete factorizations, but the partial dif ferential equation and the discretization must be taken into account. A very desirable feature of domain decomposition algorithms is that they respect the memory hierarchy of modern parallel and distributed computing systems, which is essential for approaching peak floating point performance. The devel opment of improved methods, together with more powerful computer systems, is making it possible to carry out simulations in three dimensions, with quite high resolution, relatively easily. This work is now supported by high qual ity software systems, such as Argonne's PETSc library, which facilitates code development as well as the access to a variety of parallel and distributed com puter systems. In chapters 6 and 9, we will describe numerical experiments with codes developed using this library. A powerful approach to the analysis and development of domain decompo sition is to view the procedure in terms of subspaces, of the original solution space, and with suitable solvers on these subspaces. Typically these subspaces are related to the geometrical objects of the subdomain partition (subdo mains, subdomain boundaries, interfaces between subdomains, and vertices, edges, and faces of these interfaces). The abstract Schwarz theory, presented in Chap. 2, relies on these ideas and the convergence of the resulting iterative method is related to the stability of the decomposition into subspaces, certain stability properties of the local solvers, and a measure of the 'orthogonality' of these subspaces. The strong connection between stable decompositions of discrete functions in terms of Sobolev norms and the performance of the cor responding domain decomposition algorithm is not a mere way of giving an elegant mathematical description of a method that already works well in prac tice, but it is often the way in which new powerful algorithms are actually developed, especially for less standard discretizations such as edge elements for electromagnetic problems.

Preface VII The book is addressed to mathematicians, computer scientists, and in general to people who are involved in the numerical approximation of partial differential equations, and who want to learn the basic ideas of domain de composition methods both from a mathematical and an algorithmic point of view. The mathematical tools needed for the type of analysis essentially con sist in some basic results on Sobolev spaces, which are reviewed in appendix A. The analysis also employs discrete Sobolev-type inequalities valid for finite element functions and polynomials. These tools are developed in Chap. 4. A basic knowledge of finite element theory and iterative methods is also required and two additional appendices summarize the results that are needed for the full understanding of the analysis of the algorithms developed in the main part of this monograph. The literature of the field is now quite extensive and it has developed rapidly over the past twenty years. We have been forced to make some impor tant omissions. The most important one is that we do not consider multilevel or multigrid methods, even though many of these algorithms can also be viewed, and then analyzed, using similar techniques as domain decomposition methods; the decomposition into subspaces is now related to a hierarchy of finite element meshes. The inclusion of these methods would have required a large effort and many pages and is likely to have duplicated efforts by real specialists in that field; the authors fully realizes the importance of these al gorithms, which provide efficient and robust algorithms for many very large problems. Other omissions have also been necessary: • As already mentioned, we only consider domain decomposition as a way of building iterative methods for the solution of algebraic systems of equa tions. • While we describe a number of algorithms in such a way as to simplify their implementation, we do not discuss other practical aspects of the development of codes for parallel and distributed computer systems. • We only consider linear elliptic scalar and vector problems in full detail. Indeed, the methods presented in this monograph can be applied to the solution of linear systems arising from implicit time step discretizations of time-dependent problems or arising from Newton-type iterations for non-linear problems. • Our presentation and analysis is mainly confined to low-order finite ele ment (h version) and spectral element (a particular p version) approxima tions. Some domain decomposition preconditioners have also been applied to other types of p and to certain hp approximations and we only briefly comment on some of them in Sect. 7.5. We believe that many important issues remain to be addressed in this field. • We have not touched the important problems of preconditioning plate and shell problems.

VIII Preface • Our presentation is restricted to conforming approximations. No precon ditioner is presented for, e.g., mortar methods or other approximations on nonmatching grids. • We have also been unable to cover the recent work on domain decom position methods in time and space which has originated with work by Jacques-Louis Lions and Yvon Maday. The authors wish to thank, besides the anonymous referees, the many friends that have gone over this monograph or part of it and provided us with important and helpful suggestions, references, and material. They are: Xiao-Chuan Cai, Maksymilian Dryja, Bernhard Hientzsch, Axel Klawonn, Rolf Krause, Frederic Nataf, Luca Pavarino, Alfio Quarteroni, Marcus Sarkis, Christoph Schwab, Daniel Szyld, Xavier Vasseur, and last, but not least, Barbara Wohlmuth. We would also like to thank Charbel Farhat and Oliver Rheinbach for providing us with several figures. The authors also wish to thank different funding agencies for their support. In particular, the first author acknowledges the partial support of the Swiss National Science Foundation under Project 20-63397.00. The second author has greatly benefited, over many years, from support from the US Department of Energy and the National Science Foundation. Without this support, for many students and short term visitors, etc., our progress would undoubtedly been much slower. The second author also wishes to thank over a dozen of doctoral students, who has contributed extensively to the development of the field both in graduate school and in their careers. We end this preface by summarizing the contents of the various chapters in order to facilitate for the reader and to accommodate his/her specific interests. In Chap. 1, Introduction, we present some basic ideas of domain decompo sition. In particular, we show how matching conditions for traces and fluxes of the differential problems give rise to conditions on the finite element algebraic system, how simple subdomain iterations can be devised which contain many of the ideas employed by more recent and powerful preconditioners for large scale computations on many sub domains, and how some of the ideas employed in the discussion of the Schwarz alternating method and block Jacobi precon ditioners naturally lead up to the abstract Schwarz theory. This is a chapter that requires little in terms of mathematical background. We recommend it to the reader who would like to understand the basic ideas of domain de composition without entering the specifics of the more complicated, practical algorithms. The last section, Sect. 1.6 contains some less standard and earlier results on overlapping methods and can be bypassed initially. Chapter 2, Abstract Theory of Schwarz Methods, contains the standard abstract theory of additive and multiplicative Schwarz algorithms, together with some additional topics, such as coloring arguments and some hybrid algo rithms. The three basic ideas of stable decompositions, strengthened Cauchy inequalities, and stable local solvers contained in three assumptions in Sect.

资料库

区域分解方法（DDM）.pdf

相关推荐

课程资源

热门标签

最新资料