One of the first things a student of partial differential equations learns is that it is impossible to solve elliptic equations by spatial marching. This new book describes how to do exactly that, providing a powerful tool for solving problems in fluid dynamics, heat transfer, electrostatics, and other fields characterized by discretized partial differential equations.
Elliptic Marching Methods and Domain Decomposition demonstrates how to handle numerical instabilities (i.e., limitations on the size of the problem) that appear when one tries to solve these discretized equations with marching methods. The book also shows how marching methods can be superior to multigrid and pre-conditioned conjugate gradient (PCG) methods, particularly when used in the context of multiprocessor parallel computers. Techniques for using domain decomposition together with marching methods are detailed, clearly illustrating the benefits of these techniques for applications in engineering, applied mathematics, and the physical sciences.
Introduction: The Impact of Direct Methods. Direct Marching Methods. History of Marching Methods. The Marching Method in 1D. The Reference 2D Problem. Operation Counts as an Index of Merit. Operation Counts for the Reference 2D Problem. Error Propagation Characteristics for the Reference 2D Problem. Gradient, Mixed, and Periodic Boundary Conditions. Irregular Mesh and Variable Coefficient Poisson Equations. Irregular Geometries. Other Second-Order Elliptic Equations: Advection-Diffusion Equations. Upwind Differences. Turbulence Terms. Fibonacci Scale. Helmholtz Terms. Cross Derivatives. Gradient Boundary Conditions and Cross Derivatives. Interior Flux Boundaries.
High-Order Equations
Introduction
High-Order Accuracy Operators
Higher-Order Accurate Solutions by Deferred Corrections
Higher-Order Elliptic Equations
Operation Counts for Higher-Order Systems
Finite Element Equations
Extending the Mesh Size: Domain Decomposition
Introduction
Mesh Doubling by Two-Directional Marching
Multiple Marching
Patching
Influence Extending
Other Direct Methods for Extending the Mesh Size
Lower Accuracy Stencils Plus Iteration
Iterative Coupling for Subregions
Higher Precision Arithmetic: Applications on Workstations and Virtual Parallel Networks
Banded Approximations to Influence Matrices
Introduction
Banded Approximation to C
Operation Count and Storage for Banded CB
Intrinsic Storage: Data Compression for Massively Parallel Computers
Banded Approximation to C
(*****Need a "hat" or caret over the "C" in the above title)
Marching Methods in 3D
Introduction
Simple 3D Marching
Error Propagation Characteristics for the 3D EVP
Operation Count and Storage Penalty for the 3D EVP Method
Banded Approximations in 3D
Operation Count for Banded Approximation in 3D
Additional Terms in the 3D Marching Method
3D EVP-FFT Method
Error Propagation Characteristics for 3D EVP-FFT Method
Operation Count and Storage Penalty for the 3D EVP-FFT Method
Accuracy and Additional Terms in the 3D EVP-FFT Method
N-Plane Relaxation within Multigrid and Domain Decomposition Methods
Performance of the 2D GEM Code
Introduction
Uses and Users
Overview of the GEM Codes
Problem Description in the Basic GEM Code
Tests of the Basic GEM Code
The Stabilizing Codes GEMPAT2 and GEMPAT4
Timing Tests of the Stabilized Codes
Representative Accuracy Testing
Conclusions
Vectorization and Parallelization
Introduction
Vectorizing the Tridiagonal Algorithm and the 9-Point March
Vectorizing the 5-Point March
Timing and Accuracy for the Vectorized Marches
Efficiencies
Multiprocessor Architectures
Semidirect Methods for Nonlinear Equations of Fluid Dynamics
Introduction: Time-Dependent Calculations vs. Semidirect Methods
Burgers Equation by Time Accurate Methods
Basic Idea of Semidirect Methods
Burgers Equation by Picard Semidirect Iteration
Further Discussion of the Picard Semidirect Iteration
Genesis of Semidirect Methods
NOS Method
LAD Method
Performance of NOS and LAD on the Driven Cavity Problem
Relative Importance of Lagging Boundary Conditions
Performance of LAD and NOS on a Flow-Through Problem
Optimum Relaxation Factor and Convergence for Large Problems
Choice Between LAD and NOS
Split NOS Method
A Better Boundary Condition on Wall Vorticity
Dorodnicyn-Meller Method
Viscous Flows in Alternate Variables
BID Method
FOD and Coupled System Solvers
Other Applications and Non-Time-Like Methods
Remarks on Solution Uniqueness
Remarks on Semidirect Methods within Domain Decomposition
Comparison to Multigrid Methods
Introduction
Definition of the Methods
Treatment of Nonlinearities
Speed and Accuracy
Grid Sensitivity and Word Length Sensitivity
Directionality
Storage Penalty
Dimensionality
Work Estimates
Boundary Conditions
General Coefficient Problems
Grid Transformations
Irregular Logical-Space Geometry
Higher Order Systems
Higher Order Accuracy Equations
Finite Element Equations
Use in Time Dependent Problems
Cell Reynolds Number Difficulties
Virtual Problems
MLAT and Other Grid Adaptation
Vectorization, Parallelization, and Convergence Testing
Simplicity, Modularity, and Robustness
Summary
Appendix A - Marching Schemes and Error Propagation for Various Discrete Laplacians
Appendix B - Tridiagonal Algorithm for Periodic Boundary Conditions
Appendix C - Gauss Elimination as a Direct Solver
Subject Index
Each Chapter and Appendix also Contains a List of References
Biography
Patrick J. Roache
"Together with an important historical perspective, this book uses the domain decomposition connection to develop and explore the nature of marching methods. Interesting analytical and anecdotal comparisons are made with direct methods and multigrid techniques, told by a scientist who has obviously has much experience with real practical problems."
-Mathematical Reviews, 99a