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