Linear Algebra: Foundations to Frontiers: A Collection of Notes on Numerical Linear Algebra

Description

Preface Notes on Setting Up Opening Remarks Launch Outline What You Will Learn Setting Up to Learn How to Navigate These Materials Setting Up Your Computer MATLAB Why MATLAB Installing MATLAB MATLAB Basics Wrapup Additional Homework Summary I Basics Notes on Simple Vector and Matrix Operations Opening Remarks Launch Outline What You Will Learn Notation (Hermitian) Transposition Conjugating a complex scalar Conjugate of a vector Conjugate of a matrix Transpose of a vector Hermitian transpose of a vector Transpose of a matrix Hermitian transpose (adjoint) of a matrix Exercises Vector-vector Operations Scaling a vector (scal) Scaled vector addition (axpy) Dot (inner) product (dot) Matrix-vector Operations Matrix-vector multiplication (product) Rank-1 update Matrix-matrix multiplication (product) Element-by-element computation Via matrix-vector multiplications Via row-vector times matrix multiplications Via rank-1 updates Enrichments The Basic Linear Algebra Subprograms (BLAS) Wrapup Additional exercises Summary Notes on Vector and Matrix Norms Opening Remarks Launch Outline What You Will Learn Absolute Value Vector Norms Vector 2-norm (Euclidean length) Vector 1-norm Vector -norm (infinity norm) Vector p-norm Matrix Norms Frobenius norm Induced matrix norms Special cases used in practice Discussion Submultiplicative norms An Application to Conditioning of Linear Systems Equivalence of Norms Enrichments Practical computation of the vector 2-norm Wrapup Additional exercises Summary II Orthogonality Notes on Orthogonality and the Singular Value Decomposition Video Opening Remarks Launch: Orthogonal projection and its application Outline What you will learn Orthogonality and Unitary Matrices Toward the SVD The Theorem Geometric Interpretation Consequences of the SVD Theorem Projection onto the Column Space Low-rank Approximation of a Matrix An Application SVD and the Condition Number of a Matrix An Algorithm for Computing the SVD? Wrapup Additional exercises Summary Notes on Gram-Schmidt QR Factorization Opening Remarks Launch Outline What you will learn Classical Gram-Schmidt (CGS) Process Modified Gram-Schmidt (MGS) Process In Practice, MGS is More Accurate Cost Cost of CGS Cost of MGS Wrapup Additional exercises Summary Notes on the FLAME APIs Video Outline Motivation Install FLAME@lab An Example: Gram-Schmidt Orthogonalization The Spark Webpage Implementing CGS with FLAME@lab Editing the code skeleton Testing Implementing the Other Algorithms Notes on Householder QR Factorization Opening Remarks Launch Outline What you will learn Householder Transformations (Reflectors) The general case As implemented for the Householder QR factorization (real case) The complex case (optional) A routine for computing the Householder vector Householder QR Factorization Forming Q Applying QH Blocked Householder QR Factorization The UT transform: Accumulating Householder transformations The WY transform A blocked algorithm Variations on a theme Enrichments Wrapup Additional exercises Summary Notes on Rank Revealing Householder QR Factorization Opening Remarks Launch Outline What you will learn Modifying MGS to Compute QR Factorization with Column Pivoting Unblocked Householder QR Factorization with Column Pivoting Basic algorithm Alternative unblocked Householder QR factorization with column pivoting Blocked HQRP Computing Q Enrichments QR factorization with randomization for column pivoting Wrapup Additional exercises Summary Notes on Solving Linear Least-Squares Problems Launch Outline What you will learn The Linear Least-Squares Problem Method of Normal Equations Solving the LLS Problem Via the QR Factorization Simple derivation of the solution Alternative derivation of the solution Via Householder QR Factorization Via the Singular Value Decomposition Simple derivation of the solution Alternative derivation of the solution What If A Does Not Have Linearly Independent Columns? Exercise: Using the the L Q factorization to solve underdetermined systems Wrapup Additional exercises Summary Notes on the Condition of a Problem Opening Remarks Launch Video Outline What you will learn Notation The Prototypical Example: Solving a Linear System Condition Number of a Rectangular Matrix Why Using the Method of Normal Equations Could be Bad Why Multiplication with Unitary Matrices is a Good Thing Balancing a Matrix Wrapup Additional exercises Wrapup Additional exercises Summary Notes on the Stability of an Algorithm Launch Outline What you will learn Motivation Floating Point Numbers Notation Floating Point Computation Model of floating point computation Stability of a numerical algorithm Absolute value of vectors and matrices Stability of the Dot Product Operation An algorithm for computing Dot A simple start Preparation Target result A proof in traditional format A weapon of math induction for the war on (backward) error (optional) Results Stability of a Matrix-Vector Multiplication Algorithm An algorithm for computing Gemv Analysis Stability of a Matrix-Matrix Multiplication Algorithm An algorithm for computing Gemm Analysis An application Wrapup Additional exercises Summary Notes on Performance Notes on Gaussian Elimination and LU Factorization Opening Remarks Launch Outline What you will learn Definition and Existence LU Factorization First derivation Gauss transforms Cost of LU factorization LU Factorization with Partial Pivoting Permutation matrices The algorithm Proof of Theorem 12.3 LU with Complete Pivoting Solving A x = y Via the LU Factorization with Pivoting Solving Triangular Systems of Equations L z = y U x = z Other LU Factorization Algorithms Variant 1: Bordered algorithm Variant 2: Left-looking algorithm Variant 3: Up-looking variant Variant 4: Crout variant Variant 5: Classical LU factorization All algorithms Formal derivation of algorithms Numerical Stability Results Is LU with Partial Pivoting Stable? Blocked Algorithms Blocked classical LU factorization (Variant 5) Blocked classical LU factorization with pivoting (Variant 5) Variations on a Triple-Nested Loop Inverting a Matrix Basic observations Via the LU factorization with pivoting Gauss-Jordan inversion (Almost) never, ever invert a matrix Efficient Condition Number Estimation The problem Insights A simple approach Discussion Wrapup Additional exercises Summary Notes on Cholesky Factorization Opening Remarks Launch Outline What you will learn Definition and Existence Application An Algorithm Proof of the Cholesky Factorization Theorem Blocked Algorithm Alternative Representation Cost Solving the Linear Least-Squares Problem via the Cholesky Factorization Other Cholesky Factorization Algorithms Implementing the Cholesky Factorization with the (Traditional) BLAS What are the BLAS? A simple implementation in Fortran Implemention with calls to level-1 BLAS Matrix-vector operations (level-2 BLAS) Matrix-matrix operations (level-3 BLAS) Impact on performance Alternatives to the BLAS The FLAME/C API BLIS Wrapup Additional exercises Summary Notes on Eigenvalues and Eigenvectors Video Outline Definition The Schur and Spectral Factorizations Relation Between the SVD and the Spectral Decomposition Notes on the Power Method and Related Methods Video Outline The Power Method First attempt Second attempt Convergence Practical Power Method The Rayleigh quotient What if "026A30C 0"026A30C "026A30C 1 "026A30C ? The Inverse Power Method Rayleigh-quotient Iteration Notes on the QR Algorithm and other Dense Eigensolvers Video Outline Preliminaries Subspace Iteration The QR Algorithm A basic (unshifted) QR algorithm A basic shifted QR algorithm Reduction to Tridiagonal Form Householder transformations (reflectors) Algorithm The QR algorithm with a Tridiagonal Matrix Givens' rotations QR Factorization of a Tridiagonal Matrix The Implicitly Shifted QR Algorithm Upper Hessenberg and tridiagonal matrices The Implicit Q Theorem The Francis QR Step A complete algorithm Further Reading More on reduction to tridiagonal form Optimizing the tridiagonal QR algorithm Other Algorithms Jacobi's method for the symmetric eigenvalue problem Cuppen's Algorithm The Method of Multiple Relatively Robust Representations (MRRR) The Nonsymmetric QR Algorithm A variant of the Schur decomposition Reduction to upperHessenberg form The implicitly double-shifted QR algorithm Notes on the Method of Relatively Robust Representations (MRRR) Outline MRRR, from 35,000 Feet Cholesky Factorization, Again The L D LT Factorization The U D UT Factorization The U D UT Factorization The Twisted Factorization Computing an Eigenvector from the Twisted Factorization Notes on Computing the SVD of a Matrix Outline Background Reduction to Bidiagonal Form The QR Algorithm with a Bidiagonal Matrix Putting it all together Answers 1. Notes on Simple Vector and Matrix Operations 2. Notes on Vector and Matrix Norms 3. Notes on Orthogonality and the SVD 4. Notes on Gram-Schmidt QR Factorization 6. Notes on Householder QR Factorization 8. Notes on Solving Linear Least-squares Problems (Answers) 8. Notes on the Condition of a Problem 9. Notes on the Stability of an Algorithm 10. Notes on Performance 11. Notes on Gaussian Elimination and LU Factorization 12. Notes on Cholesky Factorization 13. Notes on Eigenvalues and Eigenvectors 14. Notes on the Power Method and Related Methods 16. Notes on the Symmetric QR Algorithm 17. Notes on the Method of Relatively Robust Representations 18. Notes on Computing the SVD How to Download LAFF Routines (FLAME@lab)