Practical Fourier Analysis for Multigrid Methods

by Wienands; Roman

• ISBN13: 9781584884927
• ISBN10: 1584884924
• Edition: CD
• Format: Hardcover
• Copyright: 2004-10-28
• Publisher: Chapman & Hall/

Summary

Before applying multigrid methods to a project, mathematicians, scientists, and engineers need to answer questions related to the quality of convergence, whether a development will pay out, whether multigrid will work for a particular application, and what the numerical properties are. Practical Fourier Analysis for Multigrid Methods uses a detailed and systematic description of local Fourier k-grid (k=1,2,3) analysis for general systems of partial differential equations to provide a framework that answers these questions.This volume contains software that confirms written statements about convergence and efficiency of algorithms and is easily adapted to new applications. Providing theoretical background and the linkage between theory and practice, the text and software quickly combine learning by reading and learning by doing. The book enables understanding of basic principles of multigrid and local Fourier analysis, and also describes the theory important to those who need to delve deeper into the details of the subject.The first chapter delivers an explanation of concepts, including Fourier components and multigrid principles. Chapter 2 highlights the basic elements of local Fourier analysis and the limits to this approach. Chapter 3 examines multigrid methods and components, supported by a user-friendly GUI. Chapter 4 provides case studies for two- and three-dimensional problems. Chapters 5 and 6 detail the mathematics embedded within the software system. Chapter 7 presents recent developments and further applications of local Fourier analysis for multigrid methods.

Author Biography

Wolfgang Joppich holds a professorship at the University of Applied Sciences Bonn-Rhein-Sieg, at Sankt Augustin, Germany.

Table of Contents

Symbol Description	xv
I Practical Application of LFA and xlfa	1	(96)
1 INTRODUCTION	3	(26)
1.1 SOME NOTATION	4	(8)
1.1.1 Boundary value problems	4	(1)
1.1.2 Discrete boundary value problems	5	(1)
1.1.3 Stencil notation	6	(3)
1.1.4 Systems of partial differential equations	9	(2)
1.1.5 Operator versus matrix notation	11	(1)
1.2 BASIC ITERATIVE SCHEMES	12	(1)
1.3 A FIRST DISCUSSION OF FOURIER COMPONENTS	13	(6)
1.3.1 Empirical calculation of convergence factors	13	(1)
1.3.2 Convergence analysis for the Jacobi method	14	(2)
1.3.3 Smoothing properties of Jacobi relaxation	16	(3)
1.4 FROM RESIDUAL CORRECTION TO COARSE-GRID CORRECTION	19	(1)
1.5 MULTIGRID PRINCIPLE AND COMPONENTS	20	(2)
1.6 A FIRST LOOK AT THE GRAPHICAL USER INTERFACE	22	(7)
2 MAIN FEATURES OF LOCAL FOURIER ANALYSIS FOR MULTIGRID	29	(6)
2.1 THE POWER OF LOCAL FOURIER ANALYSIS	29	(1)
2.2 BASIC IDEAS	30	(2)
2.2.1 Main goal	30	(1)
2.2.2 Necessary simplifications for the discrete problem	31	(1)
2.2.3 Crucial observation	31	(1)
2.2.4 Arising questions	31	(1)
2.3 APPLICABILITY OF THE ANALYSIS	32	(3)
2.3.1 Type of partial differential equation	33	(1)
2.3.2 Type of grid	33	(1)
2.3.3 Type of discretization	34	(1)
3 MULTIGRID AND ITS COMPONENTS IN LFA	35	(22)
3.1 MULTIGRID CYCLING	35	(5)
3.1.1 Coarse-grid correction operator	35	(1)
3.1.2 Aliasing of Fourier components	36	(1)
3.1.3 Correction scheme	37	(3)
3.2 FULL MULTIGRID	40	(2)
3.3 xlfa FUNCTIONALITY- AN OVERVIEW	42	(2)
3.3.1 Menu bar	42	(1)
3.3.2 Button bar	43	(1)
3.3.3 Parameter display	43	(1)
3.3.4 Problem display	44	(1)
3.4 IMPLEMENTED COARSE-GRID CORRECTION COMPONENTS	44	(7)
3.4.1 Discretization and grid structure	45	(1)
3.4.2 Coarsening strategies	46	(1)
3.4.3 Coarse-grid operator	46	(2)
3.4.4 Multigrid cycling	48	(1)
3.4.5 Restriction	49	(1)
3.4.6 Prolongation	50	(1)
3.5 IMPLEMENTED RELAXATIONS	51	(6)
3.5.1 Relaxation type and ordering of grid points	51	(3)
3.5.2 Relaxation methods for systems	54	(1)
3.5.3 Multistage (MS) relaxations	55	(2)
4 USING THE FOURIER ANALYSIS SOFTWARE	57	(40)
4.1 CASE STUDIES FOR 2D SCALAR PROBLEMS	59	(18)
4.1.1 Anisotropic diffusion equation: second-order discretization	59	(6)
4.1.2 Anisotropic diffusion equation: fourth-order discretization	65	(2)
4.1.3 Anisotropic diffusion equation: Mehrstellen discretization	67	(2)
4.1.4 Helmholtz equation	69	(1)
4.1.5 Biharmonic equation	69	(1)
4.1.6 Rotated anisotropic diffusion equation	70	(3)
4.1.7 Convection diffusion equation: first-order upwind discretization	73	(3)
4.1.8 Convection diffusion equation: higher-order upwind discretization	76	(1)
4.2 CASE STUDIES FOR 3D SCALAR PROBLEMS	77	(7)
4.2.1 Ansiotropic diffusion equation: second-order discretization	77	(5)
4.2.2 Anisotropic diffusion equation: fourth-order discretization	82	(1)
4.2.3 Anisotropic diffusion equation: Mehrstellen discretization	82	(1)
4.2.4 Helmholtz equation	83	(1)
4.2.5 Biharmonic equation	83	(1)
4.2.6 Convection diffusion equation: first-order upwind discretization	83	(1)
4.3 CASE STUDIES FOR 2D SYSTEMS OF EQUATIONS	84	(10)
4.3.1 Biharmonic system	84	(2)
4.3.2 Stokes equations	86	(1)
4.3.3 First-order discretization of the Oseen equations	86	(5)
4.3.4 Higher-order discretization of the Oseen equations	91	(2)
4.3.5 Elasticity system	93	(1)
4.3.6 A linear shell problem	93	(1)
4.4 CREATING NEW APPLICATIONS	94	(3)
II The Theory behind LFA	97	(106)
5 FOURIER ONE-GRID OR SMOOTHING ANALYSIS	99	(48)
5.1 ELEMENTS OF LOCAL FOURIER ANALYSIS	100	(3)
5.1.1 Basic definitions	100	(2)
5.1.2 Generalization to systems of PDEs	102	(1)
5.2 HIGH AND LOW FOURIER FREQUENCIES	103	(2)
5.2.1 Standard and semicoarsening	103	(1)
5.2.2 Red-black coarsening and quadrupling	104	(1)
5.3 SIMPLE RELAXATION METHODS	105	(8)
5.3.1 Jacobi relaxation	107	(1)
5.3.2 Lexicographic Gauss-Seidel relaxation	108	(2)
5.3.3 A first definition of the smoothing factor	110	(3)
5.4 PATTERN RELAXATIONS	113	(16)
5.4.1 Red-black Jacobi (RB-JAC) relaxations	114	(1)
5.4.2 Spaces of 2h-harmonics	115	(3)
5.4.3 Auxiliary definitions and relations	118	(2)
5.4.4 Fourier representation for RB-JAC point relaxation	120	(3)
5.4.5 General definition of the smoothing factor	123	(4)
5.4.6 Red-black Gauss-Seidel (RB-GS) relaxations	127	(1)
5.4.7 Multicolor relaxations	128	(1)
5.5 SMOOTHING ANALYSIS FOR SYSTEMS	129	(5)
5.5.1 Collective versus decoupled smoothing	129	(3)
5.5.2 Distributive relaxation	132	(2)
5.6 MULTISTAGE (MS) RELAXATIONS	134	(4)
5.7 FURTHER RELAXATION METHODS	138	(1)
5.8 THE MEASURE OF h-ELLIPTICITY	139	(8)
5.8.1 Example 1: anisotropic diffusion equation	141	(2)
5.8.2 Example 2: convection diffusion equation	143	(2)
5.8.3 Example 3: Oseen equations	145	(2)
6 FOURIER TWO- AND THREE-GRID ANALYSIS	147	(36)
6.1 BASIC ASSUMPTIONS	148	(1)
6.2 TWO-GRID ANALYSIS FOR 2D SCALAR PROBLEMS	149	(20)
6.2.1 Spaces of 2h-harmonics	149	(2)
6.2.2 Fourier representation of fine-grid discretization	151	(1)
6.2.3 Fourier representation of restriction	151	(1)
6.2.4 Fourier representation of prolongation	152	(6)
6.2.5 Fourier representation of coarse-grid discretization	158	(2)
6.2.6 Invariance property of the two-grid operator	160	(1)
6.2.7 Definition of the two-grid convergence factor	161	(2)
6.2.8 Semicoarsening	163	(6)
6.3 TWO-GRID ANALYSIS FOR 3D SCALAR PROBLEMS	169	(4)
6.3.1 Standard coarsening	169	(2)
6.3.2 Semicoarsening	171	(2)
6.4 TWO-GRID ANALYSIS FOR SYSTEMS	173	(3)
6.5 THREE-GRID ANALYSIS	176	(7)
6.5.1 Spaces of 4h-harmonics	177	(2)
6.5.2 Invariance property of the three-grid operator	179	(1)
6.5.3 Definition of three-grid convergence factor	180	(1)
6.5.4 Generalizations	181	(2)
7 FURTHER APPLICATIONS OF LOCAL FOURIER ANALYSIS	183	(20)
7.1 ORDERS OF TRANSFER OPERATORS	184	(3)
7.1.1 Polynomial order	184	(1)
7.1.2 High- and low-frequency order	185	(2)
7.2 SIMPLIFIED FOURIER k-GRID ANALYSIS	187	(2)
7.3 CELL-CENTERED MULTIGRID	189	(8)
7.3.1 Transfer operators	191	(1)
7.3.2 Fourier two- and three-grid analysis	192	(2)
7.3.3 Orders of transfer operators	194	(1)
7.3.4 Numerical experiments	195	(2)
7.4 FOURIER ANALYSIS FOR MULTIGRID PRECONDITIONED BY GMRES	197	(6)
7.4.1 Analysis based on the GMRES(m)-polynomial	199	(1)
7.4.2 Analysis based on the spectrum of the residual transformation matrix	200	(3)
A FOURIER REPRESENTATION OF RELAXATION	203	(4)
A.1 Two-dimensional case	204	(1)
A.2 Three-dimensional case	204	(3)
REFERENCES	207	(6)
INDEX	213