Matrix-based multigrid : theory and applications

Title:

Personal Author:

Shapira, Yair, 1960-

Series:

Numerical methods and algorithms ; 2

Publication Information:

Boston : Kluwer Academic Publishers, 2003

ISBN:

9781402074851

Subject Term:

Differential equations, Partial -- Numerical solutions

Multigrid methods (Numerical analysis)

Matrices

Available:*

Library	Item Barcode	Call Number	Material Type	Item Category 1	Status
Searching... PSZ JB	30000010046224	QA377 S46 2003	Open Access Book	Book	Searching... Unknown

This is an introduction to and analysis of the multigrid approach for the numerical solution of large sparse linear systems arising from the discretization of elliptic partial differential equations. It gives special attention to the powerful matrix-based-multigrid approach, which is particularly useful for problems with variable coefficients and nonsymmetric and indefinite problems. grids but also to more realistic applications with complicated grids and domains and discontinuous coefficients. The dessication draws connections between multigrid and other iterative methods such as domain decomposition. The theoretical background provides insight about the nature of multigrid algorithms and how and why they work. The theory is written in simple algebraic terms, and therefore, requires preliminary knowledge only to basic linear algebra and calculus.

Author Notes

Yair Shapira: Computer Science department Technion -- Israel Institute of Technology

List of Figures	p. ix
List of Tables	p. xiii
Preface	p. xv
1. The Multilevel--Multiscale Approach	p. 1
1 The Multilevel--Multiscale Concept	p. 1
2 The Integer Number	p. 2
3 The Division Algorithm	p. 4
4 The Greatest-Common-Divider Algorithm	p. 5
5 Multilevel Refinement	p. 5
6 Examples from Computer Science	p. 6
7 Self Similarity	p. 7
8 The Wavelet Transform	p. 7
9 Mathematical Induction and Recursion	p. 7
10 The Product Algorithm	p. 9
11 Preliminary Notations and Definitions	p. 10
12 Application to Pivoting	p. 15
13 The Fourier Transform	p. 16
Part I The Problem and Solution Methods
2. PDES and Discretization Methods	p. 25
1 Standard Lemmas about Symmetric Matrices	p. 25
2 Elliptic Partial Differential Equations	p. 30
3 The Diffusion Equation	p. 31
4 The Finite-Difference Discretization Method	p. 31
5 Finite Differences for the Poisson Equation	p. 34
6 The Finite Volume Discretization Method	p. 36
7 The Finite Element Discretization Method	p. 38
8 Structured and Unstructured Grids	p. 41
3. Iterative Linear-System Solvers	p. 43
1 Iterative Sparse-Linear-System Solvers	p. 43
2 The Jacobi, Gauss-Seidel, and Kacmarz Relaxation Methods	p. 44
3 Reordering by Colors	p. 45
4 Cache-Oriented Reordering	p. 47
5 Symmetric Gauss-Seidel Relaxation	p. 50
6 The Preconditioned Conjugate Gradient (PCG) Method	p. 51
7 Incomplete LU Factorization (ILU)	p. 53
8 Parallelizable ILU Relaxation	p. 53
9 Parallelizable Gauss-Seidel Relaxation	p. 58
4. Multigrid Algorithms	p. 61
1 The Two-Grid Method	p. 61
2 The Multigrid Method	p. 63
3 Geometric Multigrid	p. 64
4 Matrix-Based Multigrid	p. 66
5 Algebraic Multigrid	p. 66
Part II Multigrid for Structured Grids
5. The Automug Method	p. 73
1 Properties of the AutoMUG Method	p. 73
2 Cyclic Reduction	p. 73
3 The 2-D Case	p. 75
4 The AutoMUG Method	p. 76
5 The AutoMUG(q) Method	p. 77
6. Applications in Image Processing	p. 79
1 The Denoising Problem	p. 80
2 The Denoising Algorithm for Grayscale Images	p. 80
3 The Denoising Algorithm for RGB Color Images	p. 82
4 Examples	p. 85
7. The Black-Box Multigrid Method	p. 91
1 Definition of BBMG	p. 91
2 Application to Problems with Discontinuous Coefficients	p. 93
8. The Indefinite Helmholtz Equation	p. 99
1 The Helmholtz Equation	p. 99
2 Adequate Discretization of the Indefinite Helmholtz Equation	p. 101
3 Multigrid for the Indefinite Helmholtz Equation	p. 103
4 Definition of BBMG2	p. 103
5 Computational Two-Level Analysis	p. 105
6 Multiple Coarse-Grid Corrections	p. 108
7 The Size of the Coarsest Grid	p. 110
8 Numerical Examples	p. 111
9. Matrix-Based Semicoarsening	p. 115
1 Flow of Information in Elliptic Problems	p. 116
2 Sequential Block-ILU Factorization	p. 119
3 The Domain Decomposition Solver	p. 121
4 Reordered Block-ILU Factorization	p. 123
5 Matrix Based Semicoarsening Multigrid Method	p. 125
6 A Deblurring Problem	p. 126
Part III Multigrid for Semi-Structured Grids
10. Multigrid for Locally Refined Meshes	p. 133
1 Locally Refined Meshes	p. 133
2 Multigrid and Hierarchical-Basis Linear-System Solvers	p. 136
3 The Two-Level Method	p. 137
4 Matrix-Induced Inner Products and Norms	p. 143
5 Properties of the Two-Level Method	p. 145
6 Isotropic Diffusion Problems	p. 148
7 The Multi-Level Method	p. 150
8 Upper Bound for the Condition Number	p. 152
9 The V(1,1), AFAC, and AFACx Cycles	p. 155
10 Scaling the Coefficient Matrix	p. 161
11 Black-Box Multigrid Version for Semi-Structured Grids	p. 163
12 Conclusions	p. 165
Part IV Multigrid for Unstructured Grids
11. Domain Decomposition	p. 171
1 Advantages of the Domain Decomposition Approach	p. 171
2 The Domain Decomposition Multigrid Method	p. 172
3 Upper Bound for the Condition Number	p. 174
4 High-Order Finite-Element and Spectral-Element Discretizations	p. 177
12. Algebraic Multilevel Method	p. 179
1 The Need for Algebraic Multilevel Methods	p. 179
2 The Algebraic Multilevel Method	p. 182
3 Properties of the Two-Level Method	p. 185
4 Properties of the Multilevel Method	p. 186
5 Upper Bound for the Condition Number	p. 187
6 Adequate Discretization of Highly-Anisotropic Equations	p. 189
7 Application to the Maxwell Equations	p. 192
8 The Convection-Diffusion Equation	p. 193
9 The Approximate Schur Complement Method	p. 199
10 Towards Semi-Algebraic Multilevel Methods	p. 199
13. Conclusions	p. 201
Appendices	p. 205
A C++ Framework for Unstructured Grids	p. 205
References	p. 215

Available:*

On Order

Summary

Summary

Author Notes

Table of Contents