ITERATIVE METHODS FOR SPARSE LINEAR SYSTEMS
BACKGROUND IN LINEAR ALGEBRA MATRICES SQUARE MATRICES AND EIGENVALUES TYPES OF MATRICES VECTOR INNER PRODUCTS AND NORMS MATRIX NORMS SUBSPACES, RANGE, AND KERNEL ORTHOGONAL VECTORS AND SUBSPACES CANONICAL FORMS OF MATRICES REDUCTION TO THE DIAGONAL FORM THE JORDAN CANONICAL FORM THE SCHUR CANONICAL FORM APPLICATION TO POWERS OF MATRICES NORMAL AND HERMITIAN MATRICES NORMAL MATRICES HERMITIAN MATRICES 1 10 NONNEGATIVE MATRICES, M-MATRICES 1 11 POSITIVE-DE?NITE MATRICES 1 12 PROJECTION OPERATORS 1 12 1 RANGE AND NULL SPACE OF A PROJECTOR 1 12 2 MATRIX REPRESENTATIONS 1 12 3 ORTHOGONAL AND OBLIQUE PROJECTORS 1 12 4 PROPERTIES OF ORTHOGONAL PROJECTORS 1 13 BASIC CONCEPTS IN LINEAR SYSTEMS 1 13 1 EXISTENCE OF A SOLUTION 1 13 2 PERTURBATION ANALYSIS EXERCISES AND NOTES DISCRETIZATION OF PDES PARTIAL DIFFERENTIAL EQUATIONS ELLIPTIC OPERATORS THE CONVECTION DIFFUSION EQUATION FINITE DIFFERENCE METHODS BASIC APPROXIMATIONS DIFFERENCE SCHEMES FOR THE LAPLACEAN OPERATOR FINITE DIFFERENCES FOR 1-D PROBLEMS UPWIND SCHEMES FINITE DIFFERENCES FOR 2-D PROBLEMS THE FINITE ELEMENT METHOD MESH GENERATION AND RE?NEMENT FINITE VOLUME METHOD SPARSE MATRICES INTRODUCTION GRAPH REPRESENTATIONS GRAPHS AND ADJACENCY GRAPHS GRAPHS OF PDE MATRICES PERMUTATIONS AND REORDERINGS BASIC CONCEPTS RELATIONS WITH THE ADJACENCY GRAPH COMMON REORDERINGS IRREDUCIBILITY STORAGE SCHEMES BASIC SPARSE MATRIX OPERATIONS SPARSE DIRECT SOLUTION METHODS TEST PROBLEMS BASIC ITERATIVE METHODS JACOBI, GAUSS-SEIDEL, AND SOR BLOCK RELAXATION SCHEMES ITERATION MATRICES AND PRECONDITIONING CONVERGENCE GENERAL CONVERGENCE RESULT REGULAR SPLITTINGS DIAGONALLY DOMINANT MATRICES SYMMETRIC POSITIVE DE?NITE MATRICES PROPERTY A AND CONSISTENT ORDERINGS ALTERNATING DIRECTION METHODS PROJECTION METHODS BASIC DE?NITIONS AND ALGORITHMS GENERAL PROJECTION METHODS MATRIX REPRESENTATION GENERAL THEORY TWO OPTIMALITY RESULTS INTERPRETATION IN TERMS OF PROJECTORS GENERAL ERROR BOUND ONE-DIMENSIONAL PROJECTION PROCESSES STEEPEST DESCENT MINIMAL RESIDUAL (MR) ITERATION RESIDUAL NORM STEEPEST DESCENT ADDITIVE AND MULTIPLICATIVE PROCESSES KRYLOV SUBSPACE METHODS – PART I KRYLOV SUBSPACES ARNOLDI’S METHOD THE BASIC ALGORITHM PRACTICAL IMPLEMENTATIONS ARNOLDI’S METHOD FOR LINEAR SYSTEMS (FOM) VARIATION 1: RESTARTED FOM VARIATION 2: IOM AND DIOM GMRES THE BASIC GMRES ALGORITHM THE HOUSEHOLDER VERSION PRACTICAL IMPLEMENTATION ISSUES BREAKDOWN OF GMRES RELATIONS BETWEEN FOM AND GMRES VARIATION 1: RESTARTING VARIATION 2: TRUNCATED GMRES VERSIONS THE SYMMETRIC LANCZOS ALGORITHM THE ALGORITHM RELATION WITH ORTHOGONAL POLYNOMIALS THE CONJUGATE GRADIENT ALGORITHM DERIVATION AND THEORY ALTERNATIVE FORMULATIONS EIGENVALUE ESTIMATES FROM THE CG COEF?CIENTS THE CONJUGATE RESIDUAL METHOD GCR, ORTHOMIN, AND ORTHODIR 6 10 THE FABER-MANTEUFFEL THEOREM 6 11 CONVERGENCE ANALYSIS 6 11 1 REAL CHEBYSHEV POLYNOMIALS 6 11 2 COMPLEX CHEBYSHEV POLYNOMIALS 6 11 3 CONVERGENCE OF THE CG ALGORITHM 6 11 4 CONVERGENCE OF GMRES 6 12 BLOCK KRYLOV METHODS KRYLOV SUBSPACE METHODS – PART II LANCZOS BIORTHOGONALIZATION THE LANCZOS ALGORITHM FOR LINEAR SYSTEMS THE BCG AND QMR ALGORITHMS THE BICONJUGATE GRADIENT ALGORITHM QUASI-MINIMAL RESIDUAL ALGORITHM TRANSPOSE-FREE VARIANTS CONJUGATE GRADIENT SQUARED BICGSTAB TRANSPOSE-FREE QMR (TFQMR) METHODS RELATED TO THE NORMAL EQUATIONS THE NORMAL EQUATIONS ROW PROJECTION METHODS GAUSS-SEIDEL ON THE NORMAL EQUATIONS CIMMINO’S METHOD CONJUGATE GRADIENT AND NORMAL EQUATIONS CGNR CGNE SADDLE-POINT PROBLEMS PRECONDITIONED ITERATIONS PRECONDITIONED CONJUGATE GRADIENT PRESERVING SYMMETRY EF?CIENT IMPLEMENTATIONS PRECONDITIONED GMRES LEFT-PRECONDITIONED GMRES RIGHT-PRECONDITIONED GMRES SPLIT PRECONDITIONING COMPARISON OF RIGHT AND LEFT PRECONDITIONING FLEXIBLE VARIANTS FLEXIBLE GMRES DQGMRES PRECONDITIONED CG FOR THE NORMAL EQUATIONS THE CGW ALGORITHM 10 PRECONDITIONING TECHNIQUES 10 1 INTRODUCTION 10 2 JACOBI, SOR, AND SSOR PRECONDITIONERS 10 3 ILU FACTORIZATION PRECONDITIONERS 10 3 1 INCOMPLETE LU FACTORIZATIONS 10 3 2 ZERO FILL-IN ILU (ILU(0)) 10 3 3 LEVEL OF FILL AND ILU( ) 10 3 4 MATRICES WITH REGULAR STRUCTURE 10 3 5 MODI?ED ILU (MILU) 10 4 THRESHOLD STRATEGIES AND ILUT 10 4 1 THE ILUT APPROACH 10 4 2 ANALYSIS 10 4 3 IMPLEMENTATION DETAILS 10 4 4 THE ILUTP APPROACH 10 4 5 THE ILUS APPROACH 10 5 APPROXIMATE INVERSE PRECONDITIONERS 10 5 1 APPROXIMATING THE INVERSE OF A SPARSE MATRIX 10 5 2 GLOBAL ITERATION 10 5 3 COLUMN-ORIENTED ALGORITHMS 10 5 4 THEORETICAL CONSIDERATIONS 10 5 5 CONVERGENCE OF SELF PRECONDITIONED MR 10 5 6 FACTORED APPROXIMATE INVERSES 10 5 7 IMPROVING A PRECONDITIONER 10 6 BLOCK PRECONDITIONERS 10 6 1 BLOCK-TRIDIAGONAL MATRICES 10 6 2 GENERAL MATRICES 10 7 PRECONDITIONERS FOR THE NORMAL EQUATIONS 10 7 1 JACOBI, SOR, AND VARIANTS 10 7 2 IC(0) FOR THE NORMAL EQUATIONS 10 7 3 INCOMPLETE GRAM-SCHMIDT AND ILQ 11 PARALLEL IMPLEMENTATIONS 11 1 INTRODUCTION 11 2 FORMS OF PARALLELISM 11 2 1 MULTIPLE FUNCTIONAL UNITS 11 2 2 PIPELINING 11 2 3 VECTOR PROCESSORS 11 2 4 MULTIPROCESSING AND DISTRIBUTED COMPUTING 11 3 TYPES OF PARALLEL ARCHITECTURES 11 3 1 SHARED MEMORY COMPUTERS 11 3 2 DISTRIBUTED MEMORY ARCHITECTURES 11 4 TYPES OF OPERATIONS 11 4 1 PRECONDITIONED CG 11 4 2 GMRES 11 4 3 VECTOR OPERATIONS 11 4 4 REVERSE COMMUNICATION 11 5 MATRIX-BY-VECTOR PRODUCTS 11 5 1 THE CASE OF DENSE MATRICES 11 5 2 THE CSR AND CSC FORMATS 11 5 3 MATVECS IN THE DIAGONAL FORMAT 11 5 4 THE ELLPACK-ITPACK FORMAT 11 5 5 THE JAGGED DIAGONAL FORMAT 11 5 6 THE CASE OF DISTRIBUTED SPARSE MATRICES 11 6 STANDARD PRECONDITIONING OPERATIONS 11 6 1 PARALLELISM IN FORWARD SWEEPS 11 6 2 LEVEL SCHEDULING: THE CASE OF 5-POINT MATRICES 11 6 3 LEVEL SCHEDULING FOR IRREGULAR GRAPHS 12 PARALLEL PRECONDITIONERS 12 1 INTRODUCTION 12 2 BLOCK-JACOBI PRECONDITIONERS 12 3 POLYNOMIAL PRECONDITIONERS 12 3 1 NEUMANN POLYNOMIALS 12 3 2 CHEBYSHEV POLYNOMIALS 12 3 3 LEAST-SQUARES POLYNOMIALS 12 3 4 THE NONSYMMETRIC CASE 12 4 MULTICOLORING 12 4 1 RED-BLACK ORDERING 12 4 2 SOLUTION OF RED-BLACK SYSTEMS 12 4 3 MULTICOLORING FOR GENERAL SPARSE MATRICES 12 5 MULTI-ELIMINATION ILU 12 5 1 MULTI-ELIMINATION 12 5 2 ILUM 12 6 DISTRIBUTED ILU AND SSOR 12 6 1 DISTRIBUTED SPARSE MATRICES 12 7 OTHER TECHNIQUES 12 7 1 APPROXIMATE INVERSES 12 7 2 ELEMENT-BY-ELEMENT TECHNIQUES 12 7 3 PARALLEL ROW PROJECTION PRECONDITIONERS 13 DOMAIN DECOMPOSITION METHODS 13 1 INTRODUCTION 13 1 1 NOTATION 13 1 2 TYPES OF PARTITIONINGS 13 1 3 TYPES OF TECHNIQUES 13 2 DIRECT SOLUTION AND THE SCHUR COMPLEMENT 13 2 1 BLOCK GAUSSIAN ELIMINATION 13 2 2 PROPERTIES OF THE SCHUR COMPLEMENT 13 2 3 SCHUR COMPLEMENT FOR VERTEX-BASED PARTITIONINGS 13 2 4 SCHUR COMPLEMENT FOR FINITE-ELEMENT PARTITIONINGS 13 3 SCHWARZ ALTERNATING PROCEDURES 13 3 1 MULTIPLICATIVE SCHWARZ PROCEDURE 13 3 2 MULTIPLICATIVE SCHWARZ PRECONDITIONING 13 3 3 ADDITIVE SCHWARZ PROCEDURE 13 3 4 CONVERGENCE 13 4 SCHUR COMPLEMENT APPROACHES 13 4 1 INDUCED PRECONDITIONERS 13 4 2 PROBING 13 4 3 PRECONDITIONING VERTEX-BASED SCHUR COMPLEMENTS 13 5 FULL MATRIX METHODS 13 6 GRAPH PARTITIONING 13 6 1 BASIC DE?NITIONS 13 6 2 GEOMETRIC APPROACH 13 6 3 SPECTRAL TECHNIQUES 13 6 4 GRAPH THEORY TECHNIQUES