Applied Numerical Linear Algebra ——J.D Demmel

APPLIED NUMERICAL LINEAR ALGEBRA James W. Demmel University of California Berkeley, California Society for Industrial and Applied Mathematics Philadelphia Contents Preface ix 1 Introduction 1 1.1 Basic Notation 1 1.2 Standard Problems of Numerical Linear Algebra 1 1.3 General Techniques 2 1.3.1 Matrix Factorizations 3 1.3.2 Perturbation Theory and Condition Numbers 4 1.3.3 Effects of Roundoff Error on Algorithms 5 1.3.4 Analyzing the Speed of Algorithms 5 1.3.5 Engineering Numerical Software 6 1.4 Example: Polynomial Evaluation 7 1.5 Floating Point Arithmetic 9 1.5.1 Further Details 12 1.6 Polynomial Evaluation Revisited 15 1.7 Vector and Matrix Norms 19 1.8 References and Other Topics for Chapter 1 23 1.9 Questions for Chapter 1 24 2 Linear Equation Solving 31 2.1 Introduction 31 2.2 Perturbation Theory 32 2.2.1 Relative Perturbation Theory 35 2.3 Gaussian Elimination 38 2.4 Error Analysis 44 2.4.1 The Need for Pivoting 45 2.4.2 Formal Error Analysis of Gaussian Elimination 46 2.4.3 Estimating Condition Numbers 50 2.4.4 Practical Error Bounds 54 2.5 Improving the Accuracy of a Solution 60 2.5.1 Single Precision Iterative Refinement 62 2.5.2 Equilibration 62 2.6 Blocking Algorithms for Higher Performance 63 2.6.1 Basic Linear Algebra Subroutines (BLAS) 66 2.6.2 How to Optimize Matrix Multiplication 67 2.6.3 Reorganizing Gaussian Elimination to Use Level 3 BLAS 72 2.6.4 More About Parallelism and Other Performance Issues . 75 vi Contents 2.7 2.8 2.9 Special Linear Systems 2.7.1 Real Symmetric Positive Definite Matrices 2.7.2 Symmetric Indefinite Matrices 2.7.3 Band Matrices 2.7.4 General Sparse Matrices 2.7.5 Dense Matrices Depending on Fewer Than O(n2) Pa- rameters References and Other Topics for Chapter 2 Questions for Chapter 2 76 76 79 79 83 90 93 93 3 Linear Least Squares Problems 101 3.1 Introduction 101 3.2 Matrix Factorizations That Solve the Linear Least Squares Prob- lem 105 3.2.1 Normal Equations 106 3.2.2 QR Decomposition 107 3.2.3 Singular Value Decompos