Difference between revisions of "Math 510: Numerical Methods for Linear Algebra"

From MathWiki
Jump to: navigation, search
(→‎Textbooks)
(→‎Minimal learning outcomes)
Line 21: Line 21:
  
 
<div style="-moz-column-count:2; column-count:2;">
 
<div style="-moz-column-count:2; column-count:2;">
 +
(Must know)
 +
Know properties of unitary matrices
 +
Know general definition of norms and specific definition of vector $p$-norms for 1<=p< infinity
 +
Know general definition of induced matrix norms and specific definitions of 1-,2- and infinity-norms
 +
Know  norm of product of matrices  $\leq $  product of norms of each matrix
 +
Know invariance of 2-norm and Frobenius norm of a matrix under multiplication by a unitary matrix
 +
Know definition of singular values and left and right singular vectors
 +
State the  existence and uniqueness of SVD
 +
Be able to find 2-norm and Frobenius norm given singular values of a matrix 
 +
Be able to represent a matrix  as a sum of rank-one matrices 
 +
Know truncated rank-one sum gives the best lower rank approximation to a matrix 
 +
Know definitions of projectors,  complementary projectors and orthogonal projectors
 +
be able to state and apply  classical Gram-Schmidt and modified Gram-Schmidt algorithms
 +
Know definition and properties of a Householder reflector
 +
Know how to construct Householder reflectors to triangularize a matrix
 +
Know the Householder QR factorization for triangularizing a matrix
 +
Know how least squares problems arise from a polynomial fitting problem
 +
Know how to solve least square problems using  normal equations/pseudoinverse , QR factorization and SVD
 +
 +
Be able to define the condition of a problem and related condition number
 +
Know how to calculate the condition number of a matrix (using norms and using singular values)
 +
Understand the concepts of well-conditioned and ill-conditioned problems
 +
  Know how to derive the conditioning bound of matrix-vector multiplication/ linear system solve
 +
Be able to state the precise definition of stability and backward stability
 +
Know the difference between stability and conditioning
 +
Know the four condition numbers of a least squares problem 
 +
Know how to construct element matrices to represent row operations
 +
Understand LU  and PLU factorizations
 +
Know how permutation matrices are used to represent row and column swap
 +
Understand how pivots are selected in partial pivoting
 +
Know how PLU is represented by permutation matrices and elementary matrices 
 +
  Know similarity transformation preserves eigenvalues
 +
Know nondefective matrices have an eigenvalue decomposition (i.e. diagonalizable)
 +
Understand why and how matrices can be reduced to Hessberg form (or for real symmetric matrices, to tridiagonal form) using Householder reflectors while preserving eigenvalues
 +
Be able to state and prove the convergence of power method
 +
  Know what Rayleigh quotient is nd its relation to eigenvalues
 +
Be able to describe inverse iteration and Rayleigh quotient iteration
 +
Know the convergence rates for eigenvalue/vector of  Rayleigh quotient iteration
 +
Understand Rayleigh quotient as stationary points of $r(x)$
 +
Know what normal matrices are
 +
Be able to state the QR algorithm (without and with shifts) and now why shifts are needed
 +
Know how to find Rayleigh quotient shifts and Wilkinson shifts
 +
Know how to find Rayleigh quotient shifts
 +
Be able to state the simultaneous iteration algorithm
 +
Understand simultaneous iteration and QR alogirthm are mathematically equivalent 
 +
Be able to describe Arnoldi algorithm
 +
Know reduced QR factors of Krylov matrix obtained from Arnoldi iterations 
 +
  Know characteristic polynomial of $H_{n}$ in Arnoldi iteration satisfies a minimization problem 
 +
Be able to state the GMRES algorithm
 +
Be able to describe the leas squares problem that needs to be solved in a GMRES iteration
 +
Be able to state three term recurrence of Lanczos iteration for real symmetric matrices
 +
State the CG algorithm for a real SPD matrix
 +
Be able to derive the step length parameter in line search and construction of new search directions in CG
 +
Be about the describe the v-cycle multigrid algorithm and the full multigrid algorithm
 +
Understand  relaxation, nested multiplication and coarse grid correction
 +
Understand how information is transferred between uniform grids using prolongation and restriction for 1D problems
 +
 +
(Important to know)
 +
Know  inner product and outer product
 +
Know Cauchy-Schwarz and Holder inequalities
 +
Know difference between reduced and full SVD
 +
Know relation between singular vectors and eigenvectors for Hermitian $A$
 +
Know relation between determinant of a square matrix and its singular values
 +
Know relationship between mathematical/ numerical rank  and singular values 
 +
Know relation among range, null space  and singular vectors 
 +
Know characterization of orthogonal projector 
 +
Know  reduced and full QR factorizations
 +
Know existence of QR factorization 
 +
Be able to express classical Gram-Schmidt and modified Gram-Schmidt algorithms in terms of projectors
 +
Write Gram-Schmidt as a QR factorization
 +
Know classical Gram-Schmidt algorithm is unstable (loss of orthogonality) but  modified Gram-Schmidt algorithm is stable
 +
Know solution of least square problem has its residual orthogonal to the range of  matrix 
 +
Know pseudo-inverse and its relation to least squares problem
 +
 +
 +
Be able to state the fundamental axiom of floating point arithmetic
 +
Understand the big Oh notation
 +
Know that QR factorization via Householder factorization is backward stable
 +
Be able to derive the conditioning bounds for a least squares problem when the vector $b$ is perturbed. 
 +
Know solution using SVD and QR factorization  (both via Householder or Gram-Schmidt)
 +
is backward stable
 +
Know solution to normal equations  is unstable
 +
Know how PLU factorization is implemented
 +
Understand Cholesky decomposition via  LDL transposed
 +
Know definition of algebraic multiplicity and geometric multiplicity
 +
Know determinant and trace are related to eigenvalues
 +
Be able to state and prove that every square matrix has a Schur factorization
 +
Know normality is equivalent to unitary diagonalizability and in particular for hermitian matrices
 +
Be able to describe the two stages of eigenvalue algorithms
 +
Be able to describe power iteration via Rayleigh quotient for symmetric matrices
 +
Know the convergence rates for eigenvalue/vector of  power iteration via Rayleigh quotient
 +
Know what Ritz values and Ritz vectors are
 +
Know the polynomial approximation problem associated with Arnoldi method
 +
Know invariance properties of Arnoldi method
 +
Know Ritz values from Arnoldi iteration are related to ``extreme'' eigenvalues
 +
Know the polynomial approximation problem associated with GMRES
 +
Know invariance and convergence properties of GMRES (monotone decrease in error, faster convergence from eigenvalue clustering)
 +
Be able to state the steepest descent algorithm
 +
Be able to state the residual norm related to the minimizing polynomial 
 +
Understand residuals in CG are orthogonal and search directions are $A$-conjugate 
 +
Know monotonic convergence of CG 
 +
Be able to state the finite termination property of CG 
 +
Know the polynomial approximation problem associated with CG
 +
Be able to state the  PCG algorithm
 +
\end{enumerate}
 +
 +
 +
(Useful to know)
 +
Know matrix inverse times vector as a change of basis operation
 +
Know orthogonal vectors are linearly independent
 +
Know definition of weighted vector norms and corresponding induced matrix norms
 +
Know different definitions of Frobenius norm
 +
Know positive singular values are distinct and singular vectors are unique up to complex signs
 +
Know relation between null space of a projector and the range space of its complementary projector
 +
Understand what machine epsilon is
 +
Know uniqueness of QR factorization
 +
Understand why one of the two Householder reflectors is a better choice
 +
Be able to solve $Ax=b$ for  square $A$ with a known QR factorization
 +
 +
Know how to calculate the relative condition number of a general problem
 +
Know how to determine stability and backward stability for simple problems
 +
Know that QR factorization via Householder factorization is backward stable
 +
Understand the difference between stability and accuracy
 +
Know number of operation for LU factorization is  O (n^3)
 +
Know number of operation for pivoting is  O (n^2)
 +
Know how pivots are chosen in complete pivoting
 +
  Know how Cholesky decomposition is implemented
 +
Know algebraic multiplicity is $\geq$ geometric multiplicity
 +
Know  defective eigenvalues and matrices
 +
State operation count for reduction to upper Hessenberg form
 +
Know the convergence rates for eigenvalue/vector of  inverse iteration
 +
Understand the meaning of cubic convergence
 +
Be able to describe simultaneous iteration
 +
Know convergence of QR 
 +
 +
Understand loss of orthogonality in Lanczos may cause computational problem
 +
 +
Know bound for error of CG 
 +
Be able to state the error bound of CG 
 +
Know how preconditioning works (both Hermitian and non-Hermitian cases)
 +
Construct (block) diagonal, incomplete LU and incomplete Cholesky preconditioners
 +
\end{enumerate}
 +
 +
 +
(Nice to know)
 +
Know proof of existence and uniqueness of SVD
 +
Know oblique projector
 +
Know the proof of  characterization of orthogonal projector
 +
Know the operation count of Gram-Schmidt iterations
 +
Know the operation count of Householder QR factorization
 +
 +
Know a projector separate tensor product of complex plane into two spaces
 +
Know that solution of $Ax=b$  via QR is of order condition number time machine epsilon
 +
Know that back substitution is backward stable
 +
Be able to derive the conditioning bounds for a least squares problem when the matrix $A$ is perturbed.
 +
Stability of Gaussian Elimination
 +
Know what a growth factor is
 +
Know linear solve via Cholesky decomposition is stable
 +
Stability of reduction to Hessenberg form
 +
Know QR algorithm is backward stable
 +
Know Strassen's formula
 +
Know Arnoldi lemniscates
 +
Know physical interpretation of Lanczos iteration and electric charge distribution
 +
CGN and BCG and other Krylov space methods  [important topics but you will not be tested on these]
 +
  
 
</div>
 
</div>
 +
 
=== Textbooks ===
 
=== Textbooks ===
  

Revision as of 12:00, 19 October 2010

Catalog Information

Title

Numerical Methods for Linear Algebra.

Credit Hours

3

Prerequisite

Math 343, 410; or equivalents.

Description

Numerical matrix algebra, orthogonalization and least squares methods, unsymmetric and symmetric eigenvalue problems, iterative methods, advanced solvers for partial differential equations.

Desired Learning Outcomes

Prerequisites

Minimal learning outcomes

(Must know) 

Know properties of unitary matrices
Know general definition of norms and specific definition of vector $p$-norms for 1<=p< infinity
Know general definition of induced matrix norms and specific definitions of 1-,2- and infinity-norms 
Know  norm of product of matrices  $\leq $  product of norms of each matrix
Know invariance of 2-norm and Frobenius norm of a matrix under multiplication by a unitary matrix
Know definition of singular values and left and right singular vectors 
State the  existence and uniqueness of SVD 
Be able to find 2-norm and Frobenius norm given singular values of a matrix  
Be able to represent a matrix  as a sum of rank-one matrices  
Know truncated rank-one sum gives the best lower rank approximation to a matrix  
Know definitions of projectors,  complementary projectors and orthogonal projectors
be able to state and apply  classical Gram-Schmidt and modified Gram-Schmidt algorithms
Know definition and properties of a Householder reflector
Know how to construct Householder reflectors to triangularize a matrix
Know the Householder QR factorization for triangularizing a matrix
Know how least squares problems arise from a polynomial fitting problem
Know how to solve least square problems using  normal equations/pseudoinverse , QR factorization and SVD

Be able to define the condition of a problem and related condition number
Know how to calculate the condition number of a matrix (using norms and using singular values)
Understand the concepts of well-conditioned and ill-conditioned problems
 Know how to derive the conditioning bound of matrix-vector multiplication/ linear system solve
Be able to state the precise definition of stability and backward stability
Know the difference between stability and conditioning
Know the four condition numbers of a least squares problem  
Know how to construct element matrices to represent row operations
Understand LU  and PLU factorizations
Know how permutation matrices are used to represent row and column swap
Understand how pivots are selected in partial pivoting 
Know how PLU is represented by permutation matrices and elementary matrices  
 Know similarity transformation preserves eigenvalues
Know nondefective matrices have an eigenvalue decomposition (i.e. diagonalizable)
Understand why and how matrices can be reduced to Hessberg form (or for real symmetric matrices, to tridiagonal form) using Householder reflectors while preserving eigenvalues
Be able to state and prove the convergence of power method
 Know what Rayleigh quotient is nd its relation to eigenvalues
Be able to describe inverse iteration and Rayleigh quotient iteration
Know the convergence rates for eigenvalue/vector of  Rayleigh quotient iteration
Understand Rayleigh quotient as stationary points of $r(x)$
Know what normal matrices are
Be able to state the QR algorithm (without and with shifts) and now why shifts are needed
Know how to find Rayleigh quotient shifts and Wilkinson shifts
Know how to find Rayleigh quotient shifts 
Be able to state the simultaneous iteration algorithm
Understand simultaneous iteration and QR alogirthm are mathematically equivalent  
Be able to describe Arnoldi algorithm
Know reduced QR factors of Krylov matrix obtained from Arnoldi iterations  
 Know characteristic polynomial of $H_{n}$ in Arnoldi iteration satisfies a minimization problem  
Be able to state the GMRES algorithm
Be able to describe the leas squares problem that needs to be solved in a GMRES iteration
Be able to state three term recurrence of Lanczos iteration for real symmetric matrices
State the CG algorithm for a real SPD matrix
Be able to derive the step length parameter in line search and construction of new search directions in CG
Be about the describe the v-cycle multigrid algorithm and the full multigrid algorithm
Understand  relaxation, nested multiplication and coarse grid correction
Understand how information is transferred between uniform grids using prolongation and restriction for 1D problems

(Important to know) 

Know  inner product and outer product
Know Cauchy-Schwarz and Holder inequalities
Know difference between reduced and full SVD
Know relation between singular vectors and eigenvectors for Hermitian $A$
Know relation between determinant of a square matrix and its singular values 
Know relationship between mathematical/ numerical rank  and singular values  
Know relation among range, null space  and singular vectors  
Know characterization of orthogonal projector  
Know  reduced and full QR factorizations
Know existence of QR factorization  
Be able to express classical Gram-Schmidt and modified Gram-Schmidt algorithms in terms of projectors
Write Gram-Schmidt as a QR factorization
Know classical Gram-Schmidt algorithm is unstable (loss of orthogonality) but  modified Gram-Schmidt algorithm is stable
Know solution of least square problem has its residual orthogonal to the range of  matrix  
Know pseudo-inverse and its relation to least squares problem



Be able to state the fundamental axiom of floating point arithmetic
Understand the big Oh notation
Know that QR factorization via Householder factorization is backward stable
Be able to derive the conditioning bounds for a least squares problem when the vector $b$ is perturbed.  
Know solution using SVD and QR factorization   (both via Householder or Gram-Schmidt)

is backward stable 

Know solution to normal equations  is unstable
Know how PLU factorization is implemented 
Understand Cholesky decomposition via  LDL transposed
Know definition of algebraic multiplicity and geometric multiplicity 
Know determinant and trace are related to eigenvalues
Be able to state and prove that every square matrix has a Schur factorization
Know normality is equivalent to unitary diagonalizability and in particular for hermitian matrices
Be able to describe the two stages of eigenvalue algorithms
Be able to describe power iteration via Rayleigh quotient for symmetric matrices
Know the convergence rates for eigenvalue/vector of  power iteration via Rayleigh quotient
Know what Ritz values and Ritz vectors are
Know the polynomial approximation problem associated with Arnoldi method
Know invariance properties of Arnoldi method
Know Ritz values from Arnoldi iteration are related to ``extreme eigenvalues 
Know the polynomial approximation problem associated with GMRES
Know invariance and convergence properties of GMRES (monotone decrease in error, faster convergence from eigenvalue clustering) 
Be able to state the steepest descent algorithm
Be able to state the residual norm related to the minimizing polynomial  
Understand residuals in CG are orthogonal and search directions are $A$-conjugate  
Know monotonic convergence of CG   
Be able to state the finite termination property of CG  
Know the polynomial approximation problem associated with CG
Be able to state the  PCG algorithm

\end{enumerate}


(Useful to know) 

Know matrix inverse times vector as a change of basis operation
Know orthogonal vectors are linearly independent
Know definition of weighted vector norms and corresponding induced matrix norms
Know different definitions of Frobenius norm
Know positive singular values are distinct and singular vectors are unique up to complex signs 
Know relation between null space of a projector and the range space of its complementary projector 
Understand what machine epsilon is
Know uniqueness of QR factorization
Understand why one of the two Householder reflectors is a better choice
Be able to solve $Ax=b$ for   square $A$ with a known QR factorization 

Know how to calculate the relative condition number of a general problem
Know how to determine stability and backward stability for simple problems
Know that QR factorization via Householder factorization is backward stable
Understand the difference between stability and accuracy
Know number of operation for LU factorization is   O (n^3) 
Know number of operation for pivoting is  O (n^2) 
Know how pivots are chosen in complete pivoting
 Know how Cholesky decomposition is implemented 
Know algebraic multiplicity is $\geq$ geometric multiplicity
Know  defective eigenvalues and matrices 
State operation count for reduction to upper Hessenberg form
Know the convergence rates for eigenvalue/vector of  inverse iteration 
Understand the meaning of cubic convergence
Be able to describe simultaneous iteration
Know convergence of QR  

Understand loss of orthogonality in Lanczos may cause computational problem

Know bound for error of CG  
Be able to state the error bound of CG  
Know how preconditioning works (both Hermitian and non-Hermitian cases)
Construct (block) diagonal, incomplete LU and incomplete Cholesky preconditioners

\end{enumerate}


(Nice to know) 

Know proof of existence and uniqueness of SVD 
Know oblique projector
Know the proof of  characterization of orthogonal projector 
Know the operation count of Gram-Schmidt iterations
Know the operation count of Householder QR factorization

Know a projector separate tensor product of complex plane into two spaces
Know that solution of $Ax=b$  via QR is of order condition number time machine epsilon 
Know that back substitution is backward stable 
Be able to derive the conditioning bounds for a least squares problem when the matrix $A$ is perturbed. 
Stability of Gaussian Elimination
Know what a growth factor is 
Know linear solve via Cholesky decomposition is stable
Stability of reduction to Hessenberg form
Know QR algorithm is backward stable
Know Strassen's formula
Know Arnoldi lemniscates
Know physical interpretation of Lanczos iteration and electric charge distribution
CGN and BCG and other Krylov space methods   [important topics but you will not be tested on these]


Textbooks

Possible textbooks for this course include (but are not limited to):

Lloyd N. Trefethen and David Bau III, Numerical Linear Algebra, SIAM; 1997; ISBN: 0898713617, 978-0898713619

James W. Demmel, Applied Numerical Linear Algebra, SIAM; 1997; ISBN: 0898713897, 978-0898713893

Gene H. Golub and Charles F. Van Loan, Matrix Computations, 3rd Ed., Johns Hopkins University Press, 1996; ISBN: 0801854148, 978-0801854149

William L. Briggs, Van Emden Henson and Steve F. McCormick, A Multigrid Tutorial, 2nd Ed., SIAM, 2000; ISBN: 0898714621, 978-0898714623

Barry Smith, Petter Bjorstad, William Gropp, Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations, Cambridge University Press, 2004; ISBN: 0521602866, 978-0521602860

Additional topics

Courses for which this course is prerequisite

Retrieved from "https://math.byu.edu/wiki/index.php?title=Math_510:_Numerical_Methods_for_Linear_Algebra&oldid=1458"