Golub G.H., Van Loan C.F. Matrix Computations

Prévia do material em texto

Matrix Computations (3rd Ed.)
	Copyright
	Contents
	Preface to the 3rd Ed.
	Software
	Selected References
	Ch1 Matrix Multiplication Problems
	1.1 Basic Algorithms & Notation
	1.1.1 Matrix Notation
	1.1.2 Matrix Operations
	1.1.3 Vector Notation
	1.1.4 Vector Operations
	1.1.5 Computation of Dot Products & Saxpys
	1.1.6 Matrix-Vector Multiplication & Gaxpy
	1.1.7 Partitioning Matrix into Rows & Columns
	1.1.8 Colon Notation
	1.1.9 Outer Product Update
	1.1.10 Matrix-Matrix Multiplication
	1.1.11 Scalar-Level Specifications
	1.1.12 Dot Product Formulation
	1.1.13 Saxpy Formulation
	1.1.14 Outer Product Formulation
	1.1.15 Notion of "Level"
	1.1.16 Note on Matrix Equations
	1.1.17 CompIex Matrices
	Problems
	1.2 Exploiting Structure
	1.2.1 Band Matrices & x-0 Notation
	1.2.2 Diagonal Matrix Manipulation
	1.2.3 Triangular Matrix Multiplication
	1.2.4 Flops
	1.2.5 Colon Notation: Again
	1.2.6 Band Storage
	1.2.7 Symmetry
	1.2.8 Store by Diagonal
	1.2.9 Note on Overwriting & Workspaces
	Problems
	1.3 Block Matrices & Algorithms
	1.3.1 Block Matrix Notation
	1.3.2 Block Matrix Manipulation
	1.3.3 Submatrix Designation
	1.3.4 Block Matrix Times Vector
	1.3.5 Block Matrix Multiplication
	1.3.6 Complex Matrix Multiplication
	1.3.7 Divide & Conquer Matrix Multiplication
	Problems
	1.4 Vectorization & Re-Use Issues
	1.4.1 Pipelining Arithmetic Operations
	1.4.2 Vector Operations
	1.4.3 Vector Length Issue
	1.4.4 Stride Issue
	1.4.5 Thinking about Data Motion
	1.4.6 Vector Touch Issue
	1.4.7 Blocking & Re-Use
	1.4.8 Block Matrix Data Structures
	Problems
	Ch2 Matrix Analysis
	2.1 Basic Ideas from Linear Algebra
	2.1.1 Independence, Subspace, Basis & Dimension
	2.1.2 Range, Null Space & Rank
	2.1.3 Matrix Inverse
	2.1.4 Determinant
	2.1.5 Differentiation
	Problems
	2.2 Vector Norms
	2.2.1 Definitions
	2.2.2 Some Vector Norm Properties
	2.2.3 Absolute & Relative Error
	2.2.4 Convergence
	Problems
	2.3 Matrix Norms
	2.3.1 Definitions
	2.3.2 Some Matrix Norm Properties
	2.3.3 Matrix 2-Norm
	2.3.4 Perturbations & Inverse
	Problems
	2.4 Finite Precision Matrix Computations
	2.4.1 Floating Point Numbers
	2.4.2 Model of Floating Point Arithmetic
	2.4.3 Cancellation
	2.4.4 Absolute Value Notation
	2.4.5 Rouadoff in Dot Products
	2.4.6 Alternative Ways to Quantify Roundoff Error
	2.4.7 Dot Product Accumulation
	2.4.8 Rowzdoff in other Basic Matrix Computations
	2.4.9 Forward & Backward Error Analyses
	2.4.10 Error in Strassen Multiplication
	Problems
	2.5 Orthogonality & SVD
	2.5.1 Orthogonality
	2.5.2 Norms & Orthogonal Transformations
	2.5.3 Singular Value Decomposition
	2.5.4 Thin SVD
	2.5.5 Rank Deficiency & SVD
	2.5.6 Unitary Matrices
	Problems
	2.6 Projections & CS Decomposition
	2.6.1 Orthogonal Projections
	2.6.2 SVD-Related Projections
	2.6.3 Distance between Suhpaces
	2.6.4 CS Decomposition
	Problems
	2.7 Sensitivity of Square Systems
	2.7.1 SVD Analysis
	2.7.2 Condition
	2.7.3 Determinants & Nearness to Singularity
	2.7.4 Rigorous Norm Bound
	2.7.5 Some Rigorous Componentwise Bounds
	Problems
	Ch3 General Linear Systems
	3.1 Triangular Systems
	3.1.1 Forward Substitution
	3.1.2 Back Substitution
	3.1.3 Column Oriented Versions
	3.1.4 Multiple Right Hand Sides
	3.1.5 Level-3 Fraction
	3.1.6 Non-Square Triangular System Solving
	3.1.7 Unit Triangular Systems
	3.1.8 Algebra of Triangular Matrices
	Problems
	3.2 LU Factorization
	3.2.1 Gauss Transformations
	3.2.2 Applying Gauss Transformations
	3.2.3 Roundoff Properties of Gauss Transforms
	3.2.4 Upper Triangularizing
	3.2.5 LU Factorization
	3.2.6 Some Practical Details
	3.2.7 Where is L?
	3.2.8 Solving Linear System
	3.2.9 Other Versions
	3.2.10 Block LU
	3.2.11 LU Factorization of Rectangular Matrix
	3.2.12 Note on Failure
	Problems
	3.3 Roundoff Analysis of Gaussian Elimination
	3.3.1 Errors in LU Factorization
	3.3.2 Triangular Solving with Inexact Triangles
	Problems
	3.4 Pivoting
	3.4.1 Permutation Matrices
	3.4.2 Partial Pivoting: Basic Idea
	3.4.3 Partial Pivoting Details
	3.4.4 Where is L?
	3.4.5 Gaxpy Version
	3.4.6 Error Analysis
	3.4.7 Block Gaussian Elimination
	3.4.8 Complete Pivoting
	3.4.9 Comments on Complete Pivoting
	3.4.10 Avoidance of Pivoting
	3.4.11 Some Applications
	Problems
	3.5 Improving & Estimating Accuracy
	3.5.1 Residual Size vs Accuracy
	3.5.2 Scaling
	3.5.3 Iterative Improvement
	3.5.4 Condition Estimation
	Problems
	Ch4 Special Linear Systems
	4.1 LDM & LDL Factorizations
	4.1.1 LDM Factorization
	4.1.2 Symmetry & LDL Factorization
	Problems
	4.2 Positive Definite Systems
	4.2.1 Positive Definiteness
	4.2.2 Unsymmetric Positive Definite Systems
	4.2.3 Symmetric Positive Definite Systems
	4.2.4 Gaxpy Cholesky
	4.2.5 Outer Product Cholesky
	4.2.6 Block Dot Product Cholesky
	4.2.7 Stability of Cholesky Process
	4.2.8 Semidefinite Case
	4.2.9 Symmetric Pivoting
	4.2.10 Polar Decomposition & Square Root
	Problems
	4.3 Banded Systems
	4.3.1 Band LU Factorization
	4.3.2 Band Triangular System Solving
	4.3.3 Band Gaussian Elimination with Pivoting
	4.3.4 Hessenberg LU
	4.3.5 Band Cblesky
	4.3.6 Tkidiagonal System Solving
	4.3.7 Vectorization Issues
	4.3.8 Band Matrix Data Structures
	Problems
	4.4 Symmetric Indefinite Systems
	4.4.1 Parlett-Reid Algorithms
	4.4.2 Method of Aasen
	4.4.3 Pivoting in Aasen's Method
	4.4.4 Diagonal Pivoting Methods
	4.4.5 Stability & Efficiency
	4.4.6 Note on Equilibrium Systems
	Problems
	4.5 Block Systems
	4.5.1 Block Tridiagonal LU Factorization
	4.5.2 BIock Diagonal Dominance
	4.5.3 Block vs Band Solving
	4.5.4 Block Cyclic Reduction
	4.5.5 Kronecker Product Systems
	Problems
	4.6 Vandermonde Systems & FFT
	4.6.1 Polynomial Interpolation: V'a = f
	4.6.2 System Vz = b
	4.6.3 Stability
	4.6.4 Fast Fourier Transform
	Problems
	4.7 Toeplitz & Related Systems
	4.7.1 Three Problems
	4.7.2 Solving Yule-Walker Equations
	4.7.3 General Right Hand Side Problem
	4.7.4 Computing the Inverse
	4.7.5 Stability Issues
	4.7.6 Unsymmetric Case
	4.7.7 Circulant Systems
	Problems
	Ch5 Orthogonalization & Least Squares
	5.1 Householder & Givens Matrices
	5.1.1 2-by-2 Preview
	5.1.2 Householder Reflections
	5.1.3 Computing Householder Vector
	5.1.4 Applying Householder Matrices
	5.1.5 Roundoff Properties
	5.1.6 Factored Form Representation
	5.1.7 Block Representation
	5.1.8 Givens Rotations
	5.1.9 Applying Givens Rotations
	5.1.10 Roundoff Properties
	5.1.11 Representing Products of Givens Rotations
	5.1.12 Error Propagation
	5.1.13 Fast Givens Transformations
	Problems
	5.2 QR Factorization
	5.2.1 Householder QR
	5.2.2 Block Householder QR Factorization
	5.2.3 Givens QR Methods
	5.2.4 Hessenberg QR via Givens
	5.2.5 Fast Givens QR
	5.2.6 Properties of QR Factorization
	5.2.7 Classical Gram-Schmidt
	5.2.8 Modified Gram-Schmidt
	5.2.9 Work & Accuracy
	5.2.10 Note on Complex QR
	Problems
	5.3 Full Rank LS Problem
	5.3.1 Implications of Full Rank
	5.3.2 Method of Normal Equations
	5.3.3 LS Solution via QR Factorization
	5.3.4 Breakdown in Near-Rank Deficient Case
	5.3.5 Note on MGS Approach
	5.3.6 Fast Givens LS Solver
	5.3.7 Sensitivity of LS Problem
	5.3.8 Normal Equations vs QR
	Problems
	5.4 Other Orthogonal Factorizations
	5.4.1 Rank Deficiency: QR with Column Pivoting
	5.4.2 Complete Orthogonal Decompositions
	5.4.3 Bidiagonalization
	5.4.4 R-Bidiagonalization
	5.4.5 SVD & its Computation
	Problems
	5.5 Rank Deficient LS Problem
	5.5.1 Minimum Norm Solution
	5.5.2 Complete Orthogonai Factorization & XLS
	5.5.3 SVD & LS Problem
	5.5.4 Pseudo-Inverse
	5.5.5 Some Sensitivity Issues
	5.5.6 QR with Column Pivoting & Basic Solutions
	5.5.7 Numerical Rank Determination with AII = QR
	5.5.8 Numerical Rank & SVD
	5.5.9 Some Comparisons
	Problems
	5.6 Weighting & Iterative Improvement
	5.6.1 CoIumnWeighting
	5.6.2 Row Weighting
	5.6.3 GeneraIized Least Squares
	5.6.4 Iterative Improvement
	Problems
	5.7 Square & Underdetermined Systems
	5.7.1 Using QR & SVD to Solve Square Systems
	5.7.2 Underdetermined Systems
	5.7.3 Perturbed Underdetermined Systems
	Problems
	Ch6 Parallel Matrix Computations
	6.1 Basic Concepts
	6.1.1 Distributed Memory System
	6.1.2 Communication
	6.1.3 Some Distributed Data Structures
	6.1.4 Gaxpy on Ring
	6.1.5 Cost of Communication
	6.1.6 Efficiency & Speed-Up
	6.1.7 Challenge of Load Balancing
	6.1.8 Tradeoffs
	6.1.9 Shared Memory Systems
	6.1.10 Shared Memory Gaxpy
	6.1.11 Memory Traffic Overhead
	6.1.12 Barrier Synchronization
	6.1.13 Dynamic Scheduling
	Problems
	6.2 Matrix Multiplication
	6.2.1 Block Gaxpy Procedure
	6.2.2 Torus
	Problems
	6.3 Factorizations
	6.3.1 Ring Cholesky
	6.3.2 Shared Memory Cholesky
	Problems
	Ch7 Unsymmetric Eigenvalue Problem
	7.1 Properties & Decompositions
	7.1.1 Eigenvalues & Invariant Subspaces
	7.1.2 Decoupling
	7.1.3 Basic Unitary Decompositions
	7.1.4 Nonunitary Reductions
	7.1.5 Some Comments on Nonunitary Similarity
	7.1.6 Singular Values & Eigenvalues
	Problems
	7.2 Perturbation Theory
	7.2.1 Eigenvalue Sensitivity
	7.2.2 Condition of Simple Eigenvalue
	7.2.3 Sensitivity of Repeated Eigenvalues
	7.2.4 Invariant Subspace Sensitivity
	7.2.5 Eigenvector Sensitivity
	Problems
	7.3 Power Iterations
	7.3.1 Power Method
	7.3.2 Orthogonal Iteration
	7.3.3 QR Iteration
	7.3.4 LR Iterations
	Appendix
	Problems
	7.4 Hessenberg & Real Schur Forms
	7.4.1 Real Schur Decomposition
	7.4.2 Hessenberg QR Step
	7.4.3 Hessenberg Reduction
	7.4.4 Level-3 Aspects
	7.4.5 Important Hessenberg Matrix Properties
	7.4.6 Companion Matrix Form
	7.4.7 Hessenberg Reduction via Gauss Transforms
	Problems
	7.5 Practical QR Algorithm
	7.5.1 Deflation
	7.5.2 Shifted QR Iteration
	7.5.3 Single Shift Strategy
	7.5.4 Double Shift Strategy
	7.5.5 Double Implicit Shift Strategy
	7.5.6 Overall Process
	7.5.7 Balancing
	Problems
	7.6 Invariant Subspace Computations
	7.6.1 Selected Eigenvectors via Inverse Iteration
	7.6.2 Ordering Eigenvalues in Real Schur Form
	7.6.3 Block Diagonalization
	7.6.4 Eigenvector Bases
	7.6.5 Ascertaining Jordan Block Structures
	Problems
	7.7 QZ Method for Ax = lambdaBx
	7.7.1 Background
	7.7.2 Generalized Schur Decomposition
	7.7.3 Sensitivity Issues
	7.7.4 Hessenberg-Triangular Form
	7.7.5 Deflation
	7.7.6 QZ Step
	7.7.7 Overall QZ Process
	7.7.8 Generalized Invariant Subspace Computations
	Problems
	Ch8 Symmetric Eigenvalue Problem
	8.1 Properties & Decompositions
	8.1.1 Eigenvalues & Eigenvectors
	8.1.2 Eigenvalue Sensitivity
	8.1.3 Invariant Subspaces
	8.1.4 Approximate Invariant Subspaces
	8.1.5 Law of Inertia
	Problems
	8.2 Power Iterations
	8.2.1 Power Method
	8.2.2 Inverse Iteration
	8.2.3 Rayleigh Quotient Iteration
	8.2.4 Orthogonal Iteration
	8.2.5 QR Iteration
	Problems
	8.3 Symmetric QR Algorithm
	8.3.1 Reduction to Tridiagonal Form
	8.3.2 Properties of Tridiagonal Decomposition
	8.3.3 QR Iteration & Tridiagonal Matrices
	8.3.4 Explicit Single Shift QR Iteration
	8.3.5 Implicit Shift Version
	8.3.6 Orthogonal Iteration with Ritz Acceleration
	Problems
	8.4 Jacobi Methods
	8.4.1 Jacobi Idea
	8.4.2 2-by-2 Symmetric Schur Decomposition
	8.4.3 Classical Jacobi Algorithm
	8.4.4 Cyclic-by-Row Algorithm
	8.4.5 Error Analysis
	8.4.6 Parallel Jacobi
	8.4.7 Ring Procedure
	8.4.8 Block Jacobi Procedures
	Problems
	8.5 Tridiagonal Methods
	8.5.1 Eigenvalues by Bisection
	8.5.2 Sturm Sequence Methods
	8.5.3 Eigensystems of Diagonal Plus Rank-1 Matrices
	8.5.4 Divide & Conquer Method
	8.5.5 Parallel Implementation
	Problems
	8.6 Computing SVD
	8.6.1 Perturbation Theory & Properties
	8.6.2 SVD Algorithm
	8.6.3 Jacobi SVD Procedures
	Problems
	8.7 Some Generalized Eigenvalue Problems
	8.7.1 Mathematical Background
	8.7.2 Methods for Symmetric-Definite Problem
	8.7.3 Generalized Singular Value Problem
	Problems
	Ch9 Lanczos Methods
	9.1 Derivation & Convergence Properties
	9.1.1 Krylov Subspaces
	9.1.2 Tridiagonalization
	9.1.3 Termination & Error Bounds
	9.1.4 Kaniel-Paige Convergence Theory
	9.1.5 Power Method vs Lanczos Method
	9.1.6 Convergence of Interior Eigenvalues
	Problems
	9.2 Practical Lanczos Procedures
	9.2.1 Exact Arithmetic Implementation
	9.2.2 Roundoff Properties
	9.2.3 Lanczos with Complete Reorthogonalization
	9.2.4 Selective Orthogonalization
	9.2.5 Ghost Eigenvalue Problem
	9.2.6 Block Lanczos
	9.2.7 s-Step Lanczos
	Problems
	9.3 Applications to Ax = b & Least Squares
	9.3.1 Symmetric Positive Definite Systems
	9.3.2 Symmetric Indefinite Systems
	9.3.3 Bidiagonalization & SVD
	9.3.4 Least Squares
	Problems
	9.4 Arnoldi & Unsymmetric Lanczos
	9.4.1 Basic Arnoldi Iteration
	9.4.2 Arnoldi with Restarting
	9.4.3 Unsymmetric Lanczos Tridiagonalization
	9.4.4 Look-Ahead Idea
	Problems
	Ch10 Iterative Methods for Linear Systems
	10.1 Standard Iterations
	10.1.1 Jacobi & Gauss-Seidel Iterations
	10.1.2 Splittings & Convergence
	10.1.3 Practical Implementation of Gauss-Seidel
	10.1.4 Successive Over-Relaxation
	10.1.5 Chebyshev Semi-Iterative Method
	10.1.6 Symmetric SOR
	Problems
	10.2 Conjugate Gradient Method
	10.2.1 Steepest Descent
	10.2.2 General Search Directions
	10.2.3 A-Conjugate Search Directions
	10.2.4 Choosing Best Search Direction
	10.2.5 Lanczos Connection
	10.2.6 Some Practical Details
	10.2.7 Convergence Properties
	Problems
	10.3 Preconditioned Conjugate Gradients
	10.3.1 Derivation
	10.3.2 Incomplete Cholesky Preconditioners
	10.3.3 Incomplete Block Preconditioners
	10.3.4 Domain Decomposition Ideas
	10.3.5 Polynomial Preconditioners
	10.3.6 Another Perspective
	Problems
	10.4 Other Krylov Subspace Methods
	10.4.1 Normal Equation Approaches
	10.4.2 Note on Objective Functions
	10.4.3 Conjugate Residual Method
	10.4.4 GMRES
	10.4.5 Preconditioning
	10.4.6 Biconjugate Gradient Method
	10.4.7 QMR
	10.4.8 Summary
	Problems
	Ch11 Functions of Matrices
	11.1 Eigenvalue Met hods
	11.1.1 Definition
	11.1.2 Jordan Characterization
	11.1.3 Schur Decomposition Approach
	11.1.4 Block Schur Approach
	Problems
	11.2 Approximation Methods
	11.2.1 Jordan Analysis
	11.2.2 Schur Analysis
	11.2.3 Taylor Approximants
	11.2.4 Evaluating Matrix Polynomials
	11.2.5 Computing Powers of Matrix
	11.2.6 Integrating Matrix Functions
	Problems
	11.3 Matrix Exponential
	11.3.1 Pade Approximation Method
	11.3.2 Perturbation Theory
	11.3.3 Some Stability Issues
	11.3.4 Eigenvalues & Pseudo-Eigenvalues
	Problems
	Ch12 Special Topics
	12.1 Constrained Least Squares
	12.1.1 Problem LSQI
	12.1.2 LS Minimization over Sphere
	12.1.3 Ridge Regression
	12.1.4 Equality Constrained Least Squares
	12.1.5 Method of Weighting
	Problems
	12.2 Subset Selection using SVD
	12.2.1 QR with Column Pivoting
	12.2.2 Using SVD
	12.2.3 More on Column Independence vs Residual
	Problems
	12.3 Total Least Squares
	12.3.1 Mathematical Background
	12.3.2 Computations for k = 1 Case
	12.3.3 Geometric Interpretation
	Problems
	12.4 Computing Subspaces with SVD
	12.4.1 Rotation of Subspaces
	12.4.2 Intersection of Null Spaces
	12.4.3 Angles between Subspaces
	12.4.4 Intersection of Subspaces
	Problems
	12.5 Updating Matrix Factorizations
	12.5.1 Rank-One Changes
	12.5.2 Appending or Deleting Column
	12.5.3 Appending or Deleting Row
	12.5.4 Hyperbolic Transformation Methods
	12.5.5 Updating ULV Decomposition
	Problems
	12.6 Modified/Structured Eigenproblems
	12.6.1 Constrained Eigenvalue Problem
	12.6.2 Two Inverse Eigenvalue Problems
	12.6.3 Toeplitz Eigenproblem
	12.6.4 Orthogonal Matrix Eigenproblem
	Problems
	Bibliography
	Index