Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben

2016 | Buch

Introduction Kapitel lesen Erstes Kapitel lesen

Iterative Solution of Large Sparse Systems of Equations

verfasst von: Wolfgang Hackbusch

Verlag: Springer International Publishing

Buchreihe : Applied Mathematical Sciences

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

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.

Inhaltsverzeichnis

Frontmatter

Linear Iterations

Frontmatter
Chapter 1. Introduction
Abstract
After some historical comments in Section 1.1, we introduce a model problem (Section 1.2) serving as a first test example of the various iterative methods. Deliberately, a simply structured problem is chosen since this allows us to determine all required quantities explicitly. The role of the ordering of the unknowns is explained. Section 1.3 introduces the notation for vectors and matrices. Besides the behaviour of an iterative method for a single system, one is often more interested in the behaviour with respect to a whole family of systems (see Section 1.4). In Section 1.5, the cost of the direct solution by the Gauss elimination is determined. This cost can be compared with the cost of the iterative methods introduced later. In Section 1.6, the Gauss–Seidel and SOR iteration are presented as first examples of linear iterations. Finally, in Section 1.7, sparsity of the underlying matrix discussed.
Wolfgang Hackbusch
Chapter 2. Iterative Methods
Abstract
In this chapter we consider general properties of iterative methods. Such properties are consistency, ensuring the connection between the iterative method and the given system of equations, as well as convergence, guaranteeing the success of the iteration. The most important result of this chapter is the characterisation of the convergence of linear iterations by the spectral radius of the iteration matrix (cf. §2.1.4). Since we only consider iterative methods for systems with regular matrices, iterative methods for singular systems or those with rectangular matrices will not be studied (Concerning this topic, we refer, e.g., to Björck [47], Marek [275], Kosmol–Zhou [241], Berman–Plemmons [46], and Remark 5.17). The quality of a linear iteration depends on both the cost and the convergence speed. The resulting efficacy is discussed in Section 2.3. Finally, Section 2.4 explains how to test iterative methods numerically.
Wolfgang Hackbusch
Chapter 3. Classical Linear Iterations in the Positive Definite Case
Abstract
The methods of Jacobi and Gauss–Seidel and the SOR method are closely connected and therefore they will be analysed simultaneously. The analysis, however, is essentially different for the case of positive definite matrices A discussed below and other cases studied in Chapter 4. The introductory Section 3.1 underlines the fact that the positive definite case is of practical interest. The Poisson model matrix is an example of a positive definite matrix. Section 3.2 describes the traditional iterations of Richardson, Jacobi, Gauss–Seidel, and the SOR iteration. Block versions of these iterations are discussed in Section 3.3. The computational work required by the mentioned iterations is described in Section 3.4. Convergence results of qualitative and quantitative kind are given in Section 3.5. The convergence analysis of the Richardson iteration leads to convergence criteria for general positive definite iterations. The Gauss–Seidel and SOR iteration is analysed. In particular the improvement of the order of convergence by SOR is investigated. The convergence statements are illustrated in Section 3.6 for the Poisson model case and numerical examples are given.
Wolfgang Hackbusch
Chapter 4. Analysis of Classical Iterations Under Special Structural Conditions
Abstract
The central part of this chapter is the theorem of Young about SOR convergence. It requires ‘consistently ordered matrices’. This is a more involved structural matrix property. In Section 4.1, we consider the simpler structure of 2-cyclic matrices. Sections 4.3–4.5 investigate the Richardson, Jacobi, and Gauss–Seidel iteration in this case. Section 4.6 contains the analysis of the SOR iteration. Finally, Section 4.7 presents numerical results for the model problem.
Wolfgang Hackbusch
Chapter 5. Algebra of Linear Iterations
Abstract
Most of the interesting iterative schemes are built from simpler units. The background is the fact that the set \(\mathcal {L}\) of consistent linear iterations form an algebra, i.e., there are several operations defined on \(\mathcal {L}\). In this chapter we define the following operations: Transposition of a linear iteration \(\varPhi \) produces the adjoint iteration \(\varPhi ^{*}\). This gives rise to the definition of symmetric and positive definite iterations in Section 5.1. Damping of a linear iteration \(\varPhi \) by a scalar is often used to enforce convergence (cf. Section 5.2). Addition \(\,\varPhi +\varPsi \,\) of two linear iterations is defined in §5.3. Multiplication \(\varPhi \circ \varPsi \) of two linear iterations leads to the important construction of the product iteration: \(\varPhi ,\,\varPsi \mapsto \varPhi \circ \varPsi \) (cf. Section 5.4). For instance, iterations can be symmetrised (cf. Section 5.4.2). Secondary iterations are needed for solving auxiliary problems (cf. Section 5.5). Multiplication of \(\varPhi \) by a left, right, or two-sided transformation is described in Section 5.6. Using these operations, we can construct new linear iterations.
Wolfgang Hackbusch
Chapter 6. Analysis of Positive Definite Iterations
Abstract
This chapter gathers convergence statements about iterations satisfying suitable requirements connected with positive definiteness. Section 6.1 enumerates six cases which are analysed in Section 6.2. In several cases, convergence holds for a suitably damped version of the iteration. Of particular interest are symmetric and positive definite iterations constructed in the previous chapter. In Section 6.3 we analyse traditional symmetric iterative methods: the symmetric Gauss–Seidel iteration and the symmetric SOR method, abbreviated by SSOR. The convergence properties of SSOR are investigated in §§6.3.1–6.3.2, while modifications are described in §§6.3.3–6.3.4. Finally, in §6.3.5, numerical examples illustrate the convergence behaviour.
Wolfgang Hackbusch
Chapter 7. Genenration of Iterations
Abstract
The algebraic operations described in Chapter 5 are tools for generating linear iterations. In this chapter we discuss how these tools can be used to build new iterative methods. The product of iterations is recalled in Section 7.1 and refers to later applications in Part III. Many traditional iterations are constructed by the additive splitting technique of Section 7.2. The regular splitting and weakly regular splitting defined in §7.2.2 yield sufficient convergence criteria. Another kind of splitting is the P-regular splitting defined in §7.2.4. A special kind of additive splitting is the incomplete triangular decomposition (ILU) discussed in Section 7.3. The transformations introduced in §5.6 will reappear in Section 7.4 under the name preconditioning.
Wolfgang Hackbusch

Semi-Iterations and Krylov Methods

Frontmatter
Chapter 8. Semi-Iterative Methods
Abstract
The semi-iteration comes in three formulations. The first one in Section 8.1 is the most general and associates each semi-iterate with a polynomial. Using the notion of Krylov spaces, we only require that the errors of the semi-iterates \(y^{m}\) be elements of the Krylov space \(x^{0}+N\mathcal {K}_{m}(AN,r^{0})\). In the second formulation of Section 8.2, the polynomials \(p_{m}\) associated with \(y^{m}\) are related either by a two-term or by a three-term recursion. Section 8.3 tries to determine the optimal polynomials. Here the result depends on what quantity we want to minimise. Three minimisation problems are discussed. The last formulation is practically solvable and leads to (transformed) Chebyshev polynomials. The corresponding semi-iteration is called the Chebyshev method (cf. §8.3.4). The Chebyshev method improves the order of convergence. Its convergence speed corresponds to the square root of the spectral condition number (cf. §8.3.5). In Section 8.4 the Chebyshev method is applied to the iterations discussed in Part I. In Section 8.5 we describe the ADI method which is not really of the form discussed above, but it might be seen as a generalisation of semi-iterations (replacing scalar parameters by matrix-valued ones).
Wolfgang Hackbusch
Chapter 9. Gradient Method
Abstract
The gradient method is an optimisation method of greedy type. For this purpose, the system of equations has to be rewritten as a minimisation problem (see Section 9.1). The gradient method \(\varUpsilon _{{\text {grad}}}[\varPhi ]\) derived in Section 9.2 determines the damping factors of the underlying iteration \(\,\varPhi \in \mathcal {L}\). It turns out that the convergence is not faster than the optimally damped version \(\varPhi _{\vartheta _{\mathrm {opt}}}\) of \(\varPhi \), but the method can be applied without knowing the spectral values determining \(\vartheta _{\mathrm {opt}}.\) In Section 9.3 we discuss the drawback of the gradient directions and introduce the conjugate directions in preparation for the conjugate gradient method in the next chapter. The final Section 9.4 mentions a variant of the gradient method: the minimal residual iteration which can be applied to any regular matrix A.
Wolfgang Hackbusch
Chapter 10. Conjugate Gradient Methods and Generalisations
Abstract
The conjugate gradient method is the best-known semi-iteration. Consuming only a small computational overhead, it is able to accelerate the underlying iteration. However, its use is restricted to positive definite matrices and positive definite iterations. There are several generalisations to the Hermitian and to the general case. In Section 10.1 we introduce the general concept of the required orthogonality conditions and the possible connection to minimisation principles. The standard conjugate gradient method is discussed in Section 10.2. The method of conjugate residuals introduced in Section 10.3 applies to Hermitian but possibly indefinite matrices. The method of orthogonal directions described in Section 10.4 also applies to general Hermitian matrices. General nonsymmetric problems are treated in Section 10.5. The generalised minimal residual method (GMRES; cf. \(\S \) 10.5.1), the full orthogonalisation method (cf. \(\S \) 10.5.2), and the biconjugate gradient method and its variants (cf. \(\S \) 10.5.3) are discussed.
Wolfgang Hackbusch

Special Iterations

Frontmatter
Chapter 11. Multigrid Iterations
Abstract
Multigrid methods belong to the class of fastest linear iterations, since their convergence rate is bounded independently of the step size h. Furthermore, their applicability does not require symmetry or positive definiteness. Books devoted to multigrid are Hackbusch [183], Wesseling [395], Trottenberg–Oosterlee–Schuller [367], Shaidurov [338], and Vassilevski [378]; see also [205, pp. 1–312]. The ‘smoothing step’ and the ‘coarse-grid correction’ together with the involved restrictions and prolongations are typical ingredients of the multigrid iteration. They are introduced in Section 11.1 for the Poisson model problem. The two-grid iteration explained in Section 11.2 is the first step towards the multigrid method. The iteration matrix is provided in §11.2.3. First numerical examples are presented in §11.2.4. Before a more general proof of convergence is presented, Section 11.3 investigates the one-dimensional model problem. The proof demonstrates the complementary roles of the smoothing part and the coarse-grid correction. Moreover, the dependence of the convergence rate on the number of smoothing steps is determined. The multigrid iteration is defined in Section 11.4. Its computational work is discussed and numerical examples are presented. The iteration matrix is described in §11.4.4. The nested iteration presented in Section 11.5 is a typical technique combined with the multigrid iteration. In principle, it can be combined with any iteration, provided that a hierarchy of discretisations is given. Besides a reduction of the computational work, the nested iteration technique allows us to adjust the iteration error to the discretisation error. A general convergence analysis of the W-cycle is presented in Section 11.6. Stronger statements are possible in the positive definite case which is studied in Section 11.7. Here, also the V-cycle convergence is proved. As long as lower order terms are responsible for the nonsymmetric structure, the symmetric convergence results can be transferred as shown in §11.7.6. This includes the case of the V-cycle. Possible combinations with semi-iterative methods are discussed in Section 11.8. Concluding comments are given in Section 11.9.
Wolfgang Hackbusch
Chapter 12. Domain Decomposition and Subspace Methods
Abstract
Domain decomposition is an umbrella term collecting various methods for solving discretised boundary value problems in a domain \(\Omega \) by means of a decomposition of \(\Omega \). Often this approach is chosen to support parallel computing. After general remarks in Section 12.1, the algorithm using overlapping subdomains is described in Section 12.2. In the case of nonoverlapping subdomains, one needs more involved methods (cf. Section 12.3). In particular the so-called FETI method described in \(\S \) 12.3.2 is very popular. The Schur complement method in Section 12.4 gives rise to many variants of iterations. The more abstract view of domain decomposition methods replaces the subdomain by a subspace. Section 12.5 formulates the setting of subspace iterations. Here we distinguish between the additive and multiplicative subspace iteration as explained in the corresponding Sections 12.6 and 12.7. Illustrations follow in Section 12.8. Interestingly, multigrid iterations can also be considered as subspace iterations as analysed in Section 12.9.
Wolfgang Hackbusch
Chapter 13. -LU Iteration
Abstract
The \(\mathcal {H}\)-LU iteration is a fast iteration for discretisations of boundary value problems. It even applies to fully populated matrices obtained by the boundary element method. The \(\mathcal {H}\)-LU iteration has an almost optimal order of convergence. Section 13.1 describes computing the general LU decomposition by using hierarchical matrices. In the case of sparse matrices, in particular, finite element matrices, the cluster tree can be modified (cf. Section 13.2) so that the corresponding LU decomposition partially preserves sparsity. The \(\mathcal {H}\)-LU decomposition is not exact, but the error can be rather small. Correspondingly, the \(\mathcal {H}\)-LU iteration described in Section 13.4 is very fast. The variant discussed in \(\S \) 13.4.2 is purely algebraic, i.e., the data needed for the iteration are only based on the underlying matrix. Concerning details about the technique of hierarchical matrices, we refer to Appendix D.
Wolfgang Hackbusch
Chapter 14. Tensor-based Methods
Abstract
There are situations in which the size of the system \(\,Ax=b\,\) is so large that it is impossible to store the vectors \(\,x,\,b\,\) in full format. The data size may take values like \(1000^{1000}.\) Instead one needs sparse representations for all quantities \(\,A,\,x,\,b.\) The numerical tensor calculus offers very efficient tools for this purpose. In Section 14.1 we introduce tensor spaces and show typical examples. The key for the efficient numerical treatment is a suitable sparse tensor representation. In Section 14.2 we briefly define the r-term format, the subspace format as well as the hierarchical format. The inverse matrix approximated in §14.2.2.3 will play an important role as preconditioner. In Section 14.3 two different types of huge linear systems are described together with the definition of the truncated iteration for their solution. Finally, in Section 14.4, the variational approach and the alternating least squares method are mentioned.
Wolfgang Hackbusch
Backmatter
Metadaten
Titel
Iterative Solution of Large Sparse Systems of Equations
verfasst von
Wolfgang Hackbusch
Copyright-Jahr
2016
Electronic ISBN
978-3-319-28483-5
Print ISBN
978-3-319-28481-1
DOI
https://doi.org/10.1007/978-3-319-28483-5

Premium Partner

    Bildnachweise