MathWiki - User contributions [en]

Math 511: Numerical Methods for PDEs

2010-10-19T19:33:55Z

Sc96: /* Desired Learning Outcomes */

== Catalog Information ==

=== Title ===
Numerical Methods for Partial Differential Equations.

=== Credit Hours ===
3

=== Prerequisite ===
[[Math 303]] or [[Math 347|347]]; [[Math 410|410]]; or equivalents.

=== Description ===
Finite difference and finite volume methods for partial differential equations. Stability, consistency, and convergence theory.

== Desired Learning Outcomes ==

This course is designed to prepare students to solve mathematical
models represented by initial or boundary value problems involving
partial differential equations that cannot be solved directly
using standard mathematical techniques but are amenable to a
computational approach. Numerical solution of partial differential equations has important applications in many application areas. Students are introduced to the
discretization methodologies, with particular emphasis on the
finite difference method, that allows the construction of
accurate and stable numerical schemes. In depth discussion of
theoretical aspects such as stability analysis and convergence
will be used to enhance the students' understanding of the
numerical methods. Students will also be required to perform some
programming and computation so as to gain experience in
implementing the schemes and to be able to observe the numerical
performance of the various numerical methods.

The course addresses the University goal of developing the skills
of sound thinking, effective communication and quantitative
reasoning. The course also allow students, especially
undergraduate students, to develop some depth and consequently
competence in an important area of applied mathematics.

This course requires knowledge of higher level courses in
mathematics and serves as an introductory graduate
level course to prepare the students to apply the methods learned
in their research projects.

=== Prerequisites ===

Understanding of basic theory and properties of solutions of partial differential equations;

Basic programming skill in matlab;

=== Minimal learning outcomes ===

<div style="-moz-column-count:2; column-count:2;">

</div>
Students are expected to acquire the following knowledge and skills:

Derive finite difference schemes using Taylor series.

Derive finite volume schemes using flux balance.

Understand how finite volume scheme and finite difference scheme are related.

Determine the consistency of a difference scheme.

Explain the proper function spaces and discrete norms for
grid functions for use in analysis of stability.

Establish the stability of a difference scheme using
(1) Heuristic approach
(2) Energy method
(3) von Neumann method
(4) Matrix method.

Recall the CFL condition its relation with stability.

Explain the convergence of the finite difference
approximations and its relation with consistency and stability via
Lax theorem;

Determine the order of accuracy of a finite difference
scheme.

Implement finite difference schemes on computers and perform
numerical studies of the stability and convergence properties of
the schemes.

Explain the role and the control of numerical diffusion and
dispersion in computation ; to determine how numerical phase speed
and group velocity may deviate from the theoretical phase speed
and group velocity and the numerical techniques to handle such
issues.

Recall numerical methods that efficiently handle a
multidimensional problem.

Recall alternating direction methods that reduce higher
dimensional problems into a sequence of one dimensional problems.

Recall the maximum principles for numerical schemes for
Laplace equations.

Recall iterative techniques for solving the linear systems
resulting from finite difference or finite element discretization.

=== Textbooks ===

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

John Strikwerda, Finite Difference Schemes and Partial Differential Equations, 2nd Ed., SIAM, 2007;
ISBN: 089871639X, 978-0898716399

Randall Leveque, Finite Difference Methods for Ordinary and Partial Differential Equations: Steady-State and Time-Dependent Problems, SIAM 2007;
ISBN: 0898716292, 978-0898716290

K. W. Morton and D. F. Mayers, Numerical Solution of Partial Differential Equations: An Introduction, 2nd Ed., Cambridge University Press, 2005;
ISBN: 0521607930, 978-0521607933

Arieh Iserles, A First Course in the Numerical Analysis of Differential Equations, 2nd Ed, Cambridge University Press, 2008;
ISBN: 0521734908, 978-0521734905

Claes Johnson, Numerical Solution of Partial Differential Equations by the Finite Element Method, Dover, 2009;
ISBN: 048646900X, 978-0486469003

J.W. Thomas, Numerical Partial Differential Equations: Finite Difference Methods, 2nd Ed., Springer, 2010;
ISBN-10: 1441931058, 978-1441931054

=== Additional topics ===
Finite element method; Method of lines; Parallel computing

=== Courses for which this course is prerequisite ===

[[Category:Courses|511]]
Math 303 or 347; 410; or equivalents.

Math 510: Numerical Methods for Linear Algebra

2010-10-19T19:33:21Z

Sc96: /* Desired Learning Outcomes */

Math 511: Numerical Methods for PDEs

2010-10-19T19:28:41Z

Sc96: /* Desired Learning Outcomes */

== Catalog Information ==

=== Title ===
Numerical Methods for Partial Differential Equations.

=== Credit Hours ===
3

=== Prerequisite ===
[[Math 303]] or [[Math 347|347]]; [[Math 410|410]]; or equivalents.

=== Description ===
Finite difference and finite volume methods for partial differential equations. Stability, consistency, and convergence theory.

== Desired Learning Outcomes ==

This course is designed to prepare students to solve mathematical
models represented by initial or boundary value problems involving
partial differential equations that cannot be solved directly
using standard mathematical techniques but are amenable to a
computational approach. Numerical solution of partial differential equations has important applications in many application areas. Students are introduced to the
discretization methodologies, with particular emphasis on the
finite difference method, that allows the construction of
accurate and stable numerical schemes. In depth discussion of
theoretical aspects such as stability analysis and convergence
will be used to enhance the students' understanding of the
numerical methods. Students will also be required to perform some
programming and computation so as to gain experience in
implementing the schemes and to be able to observe the numerical
performance of the various numerical methods.

The course addresses the University goal of developing the skills
of sound thinking, effective communication and quantitative
reasoning. The course also allow students, especially
undergraduate students, to develop some depth and consequently
competence in an important area of applied mathematics.

This course requires knowledge of higher level courses in
mathematics and serves as a introductory graduate
level course to prepare the students to apply the methods learned
in their research projects.

=== Prerequisites ===

Understanding of basic theory and properties of solutions of partial differential equations;

Basic programming skill in matlab;

=== Minimal learning outcomes ===

<div style="-moz-column-count:2; column-count:2;">

</div>
Students are expected to acquire the following knowledge and skills:

Derive finite difference schemes using Taylor series.

Derive finite volume schemes using flux balance.

Understand how finite volume scheme and finite difference scheme are related.

Determine the consistency of a difference scheme.

Explain the proper function spaces and discrete norms for
grid functions for use in analysis of stability.

Establish the stability of a difference scheme using
(1) Heuristic approach
(2) Energy method
(3) von Neumann method
(4) Matrix method.

Recall the CFL condition its relation with stability.

Explain the convergence of the finite difference
approximations and its relation with consistency and stability via
Lax theorem;

Determine the order of accuracy of a finite difference
scheme.

Implement finite difference schemes on computers and perform
numerical studies of the stability and convergence properties of
the schemes.

Explain the role and the control of numerical diffusion and
dispersion in computation ; to determine how numerical phase speed
and group velocity may deviate from the theoretical phase speed
and group velocity and the numerical techniques to handle such
issues.

Recall numerical methods that efficiently handle a
multidimensional problem.

Recall alternating direction methods that reduce higher
dimensional problems into a sequence of one dimensional problems.

Recall the maximum principles for numerical schemes for
Laplace equations.

Recall iterative techniques for solving the linear systems
resulting from finite difference or finite element discretization.

=== Textbooks ===

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

John Strikwerda, Finite Difference Schemes and Partial Differential Equations, 2nd Ed., SIAM, 2007;
ISBN: 089871639X, 978-0898716399

Randall Leveque, Finite Difference Methods for Ordinary and Partial Differential Equations: Steady-State and Time-Dependent Problems, SIAM 2007;
ISBN: 0898716292, 978-0898716290

K. W. Morton and D. F. Mayers, Numerical Solution of Partial Differential Equations: An Introduction, 2nd Ed., Cambridge University Press, 2005;
ISBN: 0521607930, 978-0521607933

Arieh Iserles, A First Course in the Numerical Analysis of Differential Equations, 2nd Ed, Cambridge University Press, 2008;
ISBN: 0521734908, 978-0521734905

Claes Johnson, Numerical Solution of Partial Differential Equations by the Finite Element Method, Dover, 2009;
ISBN: 048646900X, 978-0486469003

J.W. Thomas, Numerical Partial Differential Equations: Finite Difference Methods, 2nd Ed., Springer, 2010;
ISBN-10: 1441931058, 978-1441931054

=== Additional topics ===
Finite element method; Method of lines; Parallel computing

=== Courses for which this course is prerequisite ===

[[Category:Courses|511]]
Math 303 or 347; 410; or equivalents.

Math 511: Numerical Methods for PDEs

2010-10-19T19:28:31Z

Sc96: /* Desired Learning Outcomes */

== Catalog Information ==

=== Title ===
Numerical Methods for Partial Differential Equations.

=== Credit Hours ===
3

=== Prerequisite ===
[[Math 303]] or [[Math 347|347]]; [[Math 410|410]]; or equivalents.

=== Description ===
Finite difference and finite volume methods for partial differential equations. Stability, consistency, and convergence theory.

== Desired Learning Outcomes ==

This course is designed to prepare students to solve mathematical
models represented by initial or boundary value problems involving
partial differential equations that cannot be solved directly
using standard mathematical techniques but are amenable to a
computational approach. Numerical solution of partial differential equations has important applications in many application areas. Students are introduced to the
discretization methodologies, with particular emphasis on the
finite difference method, that allows the construction of
accurate and stable numerical schemes. In depth discussion of
theoretical aspects such as stability analysis and convergence
will be used to enhance the students' understanding of the
numerical methods. Students will also be required to perform some
programming and computation so as to gain experience in
implementing the schemes and to be able to observe the numerical
performance of the various numerical methods.

The course addresses the University goal of developing the skills
of sound thinking, effective communication and quantitative
reasoning. The course also allow students, especially
undergraduate students, to develop some depth and consequently
competence in an important area of applied mathematics.

This course requires knowledge of higher level courses in
mathematics and serves as a introductory graduate
level course to prepare the students to apply the methods learned
in their research projects.

=== Prerequisites ===

Understanding of basic theory and properties of solutions of partial differential equations;

Basic programming skill in matlab;

=== Minimal learning outcomes ===

<div style="-moz-column-count:2; column-count:2;">

</div>
Students are expected to acquire the following knowledge and skills:

Derive finite difference schemes using Taylor series.

Derive finite volume schemes using flux balance.

Understand how finite volume scheme and finite difference scheme are related.

Determine the consistency of a difference scheme.

Explain the proper function spaces and discrete norms for
grid functions for use in analysis of stability.

Establish the stability of a difference scheme using
(1) Heuristic approach
(2) Energy method
(3) von Neumann method
(4) Matrix method.

Recall the CFL condition its relation with stability.

Explain the convergence of the finite difference
approximations and its relation with consistency and stability via
Lax theorem;

Determine the order of accuracy of a finite difference
scheme.

Implement finite difference schemes on computers and perform
numerical studies of the stability and convergence properties of
the schemes.

Explain the role and the control of numerical diffusion and
dispersion in computation ; to determine how numerical phase speed
and group velocity may deviate from the theoretical phase speed
and group velocity and the numerical techniques to handle such
issues.

Recall numerical methods that efficiently handle a
multidimensional problem.

Recall alternating direction methods that reduce higher
dimensional problems into a sequence of one dimensional problems.

Recall the maximum principles for numerical schemes for
Laplace equations.

Recall iterative techniques for solving the linear systems
resulting from finite difference or finite element discretization.

=== Textbooks ===

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

John Strikwerda, Finite Difference Schemes and Partial Differential Equations, 2nd Ed., SIAM, 2007;
ISBN: 089871639X, 978-0898716399

Randall Leveque, Finite Difference Methods for Ordinary and Partial Differential Equations: Steady-State and Time-Dependent Problems, SIAM 2007;
ISBN: 0898716292, 978-0898716290

K. W. Morton and D. F. Mayers, Numerical Solution of Partial Differential Equations: An Introduction, 2nd Ed., Cambridge University Press, 2005;
ISBN: 0521607930, 978-0521607933

Arieh Iserles, A First Course in the Numerical Analysis of Differential Equations, 2nd Ed, Cambridge University Press, 2008;
ISBN: 0521734908, 978-0521734905

Claes Johnson, Numerical Solution of Partial Differential Equations by the Finite Element Method, Dover, 2009;
ISBN: 048646900X, 978-0486469003

J.W. Thomas, Numerical Partial Differential Equations: Finite Difference Methods, 2nd Ed., Springer, 2010;
ISBN-10: 1441931058, 978-1441931054

=== Additional topics ===
Finite element method; Method of lines; Parallel computing

=== Courses for which this course is prerequisite ===

[[Category:Courses|511]]
Math 303 or 347; 410; or equivalents.

Math 511: Numerical Methods for PDEs

2010-10-19T19:27:17Z

Sc96: /* Desired Learning Outcomes */

== Catalog Information ==

=== Title ===
Numerical Methods for Partial Differential Equations.

=== Credit Hours ===
3

=== Prerequisite ===
[[Math 303]] or [[Math 347|347]]; [[Math 410|410]]; or equivalents.

=== Description ===
Finite difference and finite volume methods for partial differential equations. Stability, consistency, and convergence theory.

== Desired Learning Outcomes ==

This course is designed to prepare students to solve mathematical
models represented by initial or boundary value problems involving
partial differential equations that cannot be solved directly
using standard mathematical techniques but are amenable to a
computational approach. Numerical solution of partial differential equations has important applications in many application areas. Students are introduced to the
discretization methodologies, with particular emphasis on the
finite difference method, that allows the construction of
accurate and stable numerical schemes. In depth discussion of
theoretical aspects such as stability analysis and convergence
will be used to enhance the students' understanding of the
numerical methods. Students will also be required to perform some
programming and computation so as to gain experience in
implementing the schemes and to be able to observe the numerical
performance of the various numerical methods.

=== Prerequisites ===

Understanding of basic theory and properties of solutions of partial differential equations;

Basic programming skill in matlab;

=== Minimal learning outcomes ===

<div style="-moz-column-count:2; column-count:2;">

</div>
Students are expected to acquire the following knowledge and skills:

Derive finite difference schemes using Taylor series.

Derive finite volume schemes using flux balance.

Understand how finite volume scheme and finite difference scheme are related.

Determine the consistency of a difference scheme.

Explain the proper function spaces and discrete norms for
grid functions for use in analysis of stability.

Establish the stability of a difference scheme using
(1) Heuristic approach
(2) Energy method
(3) von Neumann method
(4) Matrix method.

Recall the CFL condition its relation with stability.

Explain the convergence of the finite difference
approximations and its relation with consistency and stability via
Lax theorem;

Determine the order of accuracy of a finite difference
scheme.

Implement finite difference schemes on computers and perform
numerical studies of the stability and convergence properties of
the schemes.

Explain the role and the control of numerical diffusion and
dispersion in computation ; to determine how numerical phase speed
and group velocity may deviate from the theoretical phase speed
and group velocity and the numerical techniques to handle such
issues.

Recall numerical methods that efficiently handle a
multidimensional problem.

Recall alternating direction methods that reduce higher
dimensional problems into a sequence of one dimensional problems.

Recall the maximum principles for numerical schemes for
Laplace equations.

Recall iterative techniques for solving the linear systems
resulting from finite difference or finite element discretization.

=== Textbooks ===

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

John Strikwerda, Finite Difference Schemes and Partial Differential Equations, 2nd Ed., SIAM, 2007;
ISBN: 089871639X, 978-0898716399

Randall Leveque, Finite Difference Methods for Ordinary and Partial Differential Equations: Steady-State and Time-Dependent Problems, SIAM 2007;
ISBN: 0898716292, 978-0898716290

K. W. Morton and D. F. Mayers, Numerical Solution of Partial Differential Equations: An Introduction, 2nd Ed., Cambridge University Press, 2005;
ISBN: 0521607930, 978-0521607933

Arieh Iserles, A First Course in the Numerical Analysis of Differential Equations, 2nd Ed, Cambridge University Press, 2008;
ISBN: 0521734908, 978-0521734905

Claes Johnson, Numerical Solution of Partial Differential Equations by the Finite Element Method, Dover, 2009;
ISBN: 048646900X, 978-0486469003

J.W. Thomas, Numerical Partial Differential Equations: Finite Difference Methods, 2nd Ed., Springer, 2010;
ISBN-10: 1441931058, 978-1441931054

=== Additional topics ===
Finite element method; Method of lines; Parallel computing

=== Courses for which this course is prerequisite ===

[[Category:Courses|511]]
Math 303 or 347; 410; or equivalents.

Math 511: Numerical Methods for PDEs

2010-10-19T19:27:05Z

Sc96: /* Desired Learning Outcomes */

== Catalog Information ==

=== Title ===
Numerical Methods for Partial Differential Equations.

=== Credit Hours ===
3

=== Prerequisite ===
[[Math 303]] or [[Math 347|347]]; [[Math 410|410]]; or equivalents.

=== Description ===
Finite difference and finite volume methods for partial differential equations. Stability, consistency, and convergence theory.

== Desired Learning Outcomes ==

This course is designed to prepare students to solve mathematical
models represented by initial or boundary value problems involving
partial differential equations that cannot be solved directly
using standard mathematical techniques but are amenable to a
computational approach. Numerical solution of partial differential equations has important applications in many application areas. Students are introduced to the
discretization methodologies, with particular emphasis on the
finite difference method, that allows the construction of
accurate and stable numerical schemes. In depth discussion of
theoretical aspects such as stability analysis and convergence
will be used to enhance the students' understanding of the
numerical methods. Students will also be required to perform some
programming and computation so as to gain experience in
implementing the schemes and to be able to observe the numerical
performance of the various numerical methods.

=== Prerequisites ===

Understanding of basic theory and properties of solutions of partial differential equations;

Basic programming skill in matlab;

=== Minimal learning outcomes ===

<div style="-moz-column-count:2; column-count:2;">

</div>
Students are expected to acquire the following knowledge and skills:

Derive finite difference schemes using Taylor series.

Derive finite volume schemes using flux balance.

Understand how finite volume scheme and finite difference scheme are related.

Determine the consistency of a difference scheme.

Explain the proper function spaces and discrete norms for
grid functions for use in analysis of stability.

Establish the stability of a difference scheme using
(1) Heuristic approach
(2) Energy method
(3) von Neumann method
(4) Matrix method.

Recall the CFL condition its relation with stability.

Explain the convergence of the finite difference
approximations and its relation with consistency and stability via
Lax theorem;

Determine the order of accuracy of a finite difference
scheme.

Implement finite difference schemes on computers and perform
numerical studies of the stability and convergence properties of
the schemes.

Explain the role and the control of numerical diffusion and
dispersion in computation ; to determine how numerical phase speed
and group velocity may deviate from the theoretical phase speed
and group velocity and the numerical techniques to handle such
issues.

Recall numerical methods that efficiently handle a
multidimensional problem.

Recall alternating direction methods that reduce higher
dimensional problems into a sequence of one dimensional problems.

Recall the maximum principles for numerical schemes for
Laplace equations.

Recall iterative techniques for solving the linear systems
resulting from finite difference or finite element discretization.

=== Textbooks ===

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

John Strikwerda, Finite Difference Schemes and Partial Differential Equations, 2nd Ed., SIAM, 2007;
ISBN: 089871639X, 978-0898716399

Randall Leveque, Finite Difference Methods for Ordinary and Partial Differential Equations: Steady-State and Time-Dependent Problems, SIAM 2007;
ISBN: 0898716292, 978-0898716290

K. W. Morton and D. F. Mayers, Numerical Solution of Partial Differential Equations: An Introduction, 2nd Ed., Cambridge University Press, 2005;
ISBN: 0521607930, 978-0521607933

Arieh Iserles, A First Course in the Numerical Analysis of Differential Equations, 2nd Ed, Cambridge University Press, 2008;
ISBN: 0521734908, 978-0521734905

Claes Johnson, Numerical Solution of Partial Differential Equations by the Finite Element Method, Dover, 2009;
ISBN: 048646900X, 978-0486469003

J.W. Thomas, Numerical Partial Differential Equations: Finite Difference Methods, 2nd Ed., Springer, 2010;
ISBN-10: 1441931058, 978-1441931054

=== Additional topics ===
Finite element method; Method of lines; Parallel computing

=== Courses for which this course is prerequisite ===

[[Category:Courses|511]]
Math 303 or 347; 410; or equivalents.

Math 510: Numerical Methods for Linear Algebra

2010-10-19T19:19:53Z

Sc96: /* Minimal learning outcomes */

Math 510: Numerical Methods for Linear Algebra

2010-10-19T19:18:18Z

Sc96: /* Minimal learning outcomes */

Math 510: Numerical Methods for Linear Algebra

2010-10-19T18:59:51Z

Sc96: /* Additional topics */

== Catalog Information ==

=== Title ===
Numerical Methods for Linear Algebra.

=== Credit Hours ===
3

=== Prerequisite ===
[[Math 343]], [[Math 410|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 ===
Mastery of materials in an undergraduate course in linear algebra. Knowledge of matlab.

=== Minimal learning outcomes ===

<div style="-moz-column-count:2; column-count:2;">
</div>
(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

(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 greater than or equal to 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

(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

=== 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 ===
Multigrid method;
Domain decomposition method;
Freely available linear algebra software;
Fast multipole method for linear systems; Parallel processing

=== Courses for which this course is prerequisite ===

[[Category:Courses|510]]
Math 343, 410; or equivalents.

Math 511: Numerical Methods for PDEs

2010-10-19T18:59:08Z

Sc96: /* Prerequisites */

Math 511: Numerical Methods for PDEs

2010-10-19T18:57:50Z

Sc96: /* Additional topics */

Math 511: Numerical Methods for PDEs

2010-10-19T18:57:20Z

Sc96: /* Minimal learning outcomes */

Math 511: Numerical Methods for PDEs

2010-10-19T18:54:45Z

Sc96: /* Textbooks */

Math 511: Numerical Methods for PDEs

2010-10-19T18:46:15Z

Sc96: /* Minimal learning outcomes */

Math 511: Numerical Methods for PDEs

2010-10-19T18:43:08Z

Sc96: /* Textbooks */

Math 511: Numerical Methods for PDEs

2010-10-19T18:37:50Z

Sc96: /* Additional topics */

Math 511: Numerical Methods for PDEs

2010-10-19T18:36:21Z

Sc96: /* Courses for which this course is prerequisite */

Math 511: Numerical Methods for PDEs

2010-10-19T18:35:57Z

Sc96: /* Minimal learning outcomes */

Math 511: Numerical Methods for PDEs

2010-10-19T18:35:37Z

Sc96: /* Minimal learning outcomes */

Math 511: Numerical Methods for PDEs

2010-10-19T18:35:09Z

Sc96: /* Minimal learning outcomes */

Math 511: Numerical Methods for PDEs

2010-10-19T18:34:00Z

Sc96: /* Minimal learning outcomes */

Math 510: Numerical Methods for Linear Algebra

2010-10-19T18:31:02Z

Sc96: /* Minimal learning outcomes */

== Catalog Information ==

=== Title ===
Numerical Methods for Linear Algebra.

=== Credit Hours ===
3

=== Prerequisite ===
[[Math 343]], [[Math 410|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 ===
Mastery of materials in an undergraduate course in linear algebra. Knowledge of matlab.

=== Minimal learning outcomes ===

<div style="-moz-column-count:2; column-count:2;">
</div>
(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

(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 greater than or equal to 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

(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

=== 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 ===
Multigrid method;
Domain decomposition method;
Freely available linear algebra software;
Fast multipole method for linear systems

=== Courses for which this course is prerequisite ===

[[Category:Courses|510]]
Math 343, 410; or equivalents.

Math 510: Numerical Methods for Linear Algebra

2010-10-19T18:30:43Z

Sc96: /* Additional topics */

== Catalog Information ==

=== Title ===
Numerical Methods for Linear Algebra.

=== Credit Hours ===
3

=== Prerequisite ===
[[Math 343]], [[Math 410|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 ===
Mastery of materials in an undergraduate course in linear algebra. Knowledge of matlab.

=== Minimal learning outcomes ===

<div style="-moz-column-count:2; column-count:2;">
</div>
(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

(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 greater than or equal to 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

(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 ===
Multigrid method;
Domain decomposition method;
Freely available linear algebra software;
Fast multipole method for linear systems

=== Courses for which this course is prerequisite ===

[[Category:Courses|510]]
Math 343, 410; or equivalents.

Math 510: Numerical Methods for Linear Algebra

2010-10-19T18:30:28Z

Sc96: /* Additional topics */

== Catalog Information ==

=== Title ===
Numerical Methods for Linear Algebra.

=== Credit Hours ===
3

=== Prerequisite ===
[[Math 343]], [[Math 410|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 ===
Mastery of materials in an undergraduate course in linear algebra. Knowledge of matlab.

=== Minimal learning outcomes ===

<div style="-moz-column-count:2; column-count:2;">
</div>
(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

(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 greater than or equal to 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

(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 ===
Multigrid method
Domain decomposition method
Freely available linear algebra software
Fast multipole method for linear systems

=== Courses for which this course is prerequisite ===

[[Category:Courses|510]]
Math 343, 410; or equivalents.

Math 510: Numerical Methods for Linear Algebra

2010-10-19T18:27:43Z

Sc96: /* Minimal learning outcomes */

== Catalog Information ==

=== Title ===
Numerical Methods for Linear Algebra.

=== Credit Hours ===
3

=== Prerequisite ===
[[Math 343]], [[Math 410|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 ===
Mastery of materials in an undergraduate course in linear algebra. Knowledge of matlab.

=== Minimal learning outcomes ===

<div style="-moz-column-count:2; column-count:2;">
</div>
(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

(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 greater than or equal to 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

(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 ===

[[Category:Courses|510]]
Math 343, 410; or equivalents.

Math 510: Numerical Methods for Linear Algebra

2010-10-19T18:26:37Z

Sc96: /* Courses for which this course is prerequisite */

== Catalog Information ==

=== Title ===
Numerical Methods for Linear Algebra.

=== Credit Hours ===
3

=== Prerequisite ===
[[Math 343]], [[Math 410|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 ===
Mastery of materials in an undergraduate course in linear algebra. Knowledge of matlab.

=== Minimal learning outcomes ===

<div style="-moz-column-count:2; column-count:2;">
</div>
(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

(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

(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 ===

[[Category:Courses|510]]
Math 343, 410; or equivalents.

Math 510: Numerical Methods for Linear Algebra

2010-10-19T18:26:02Z

Sc96: /* Prerequisites */

== Catalog Information ==

=== Title ===
Numerical Methods for Linear Algebra.

=== Credit Hours ===
3

=== Prerequisite ===
[[Math 343]], [[Math 410|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 ===
Mastery of materials in an undergraduate course in linear algebra. Knowledge of matlab.

=== Minimal learning outcomes ===

<div style="-moz-column-count:2; column-count:2;">
</div>
(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

(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

(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 ===

[[Category:Courses|510]]

Math 510: Numerical Methods for Linear Algebra

2010-10-19T18:23:02Z

Sc96: /* Minimal learning outcomes */

== Catalog Information ==

=== Title ===
Numerical Methods for Linear Algebra.

=== Credit Hours ===
3

=== Prerequisite ===
[[Math 343]], [[Math 410|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 ===

<div style="-moz-column-count:2; column-count:2;">
</div>
(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

(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

(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 ===

[[Category:Courses|510]]

Math 510: Numerical Methods for Linear Algebra

2010-10-19T18:22:19Z

Sc96: /* Minimal learning outcomes */

== Catalog Information ==

=== Title ===
Numerical Methods for Linear Algebra.

=== Credit Hours ===
3

=== Prerequisite ===
[[Math 343]], [[Math 410|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 ===

#<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

(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

(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>

=== 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 ===

[[Category:Courses|510]]

Math 510: Numerical Methods for Linear Algebra

2010-10-19T18:21:27Z

Sc96: /* Minimal learning outcomes */

== Catalog Information ==

=== Title ===
Numerical Methods for Linear Algebra.

=== Credit Hours ===
3

=== Prerequisite ===
[[Math 343]], [[Math 410|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 ===

#<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

(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

(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>

=== 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 ===

[[Category:Courses|510]]

Math 510: Numerical Methods for Linear Algebra

2010-10-19T18:20:39Z

Sc96: /* Minimal learning outcomes */

== Catalog Information ==

=== Title ===
Numerical Methods for Linear Algebra.

=== Credit Hours ===
3

=== Prerequisite ===
[[Math 343]], [[Math 410|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 ===

#<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

(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

(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>

=== 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 ===

[[Category:Courses|510]]

Math 510: Numerical Methods for Linear Algebra

2010-10-19T18:03:36Z

Sc96: /* Minimal learning outcomes */

== Catalog Information ==

=== Title ===
Numerical Methods for Linear Algebra.

=== Credit Hours ===
3

=== Prerequisite ===
[[Math 343]], [[Math 410|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 ===

<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

(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

(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>

=== 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 ===

[[Category:Courses|510]]

Math 510: Numerical Methods for Linear Algebra

2010-10-19T18:02:36Z

Sc96: /* Minimal learning outcomes */

== Catalog Information ==

=== Title ===
Numerical Methods for Linear Algebra.

=== Credit Hours ===
3

=== Prerequisite ===
[[Math 343]], [[Math 410|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 ===

<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

(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>

=== 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 ===

[[Category:Courses|510]]

Math 510: Numerical Methods for Linear Algebra

2010-10-19T18:00:38Z

Sc96: /* Minimal learning outcomes */

== Catalog Information ==

=== Title ===
Numerical Methods for Linear Algebra.

=== Credit Hours ===
3

=== Prerequisite ===
[[Math 343]], [[Math 410|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 ===

<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>

=== 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 ===

[[Category:Courses|510]]

Math 510: Numerical Methods for Linear Algebra

2010-10-19T17:50:17Z

Sc96: /* Textbooks */