AMS 526: Numerical Analysis I
(Numerical Linear Algebra for Computational and Data Sciences)
Fall 2016
Time: Monday & Wednesday 4:00--5:20pm
Location: Frey Hall 217

Lecture Schedule and Slides


Instructor: Prof. Xiangmin (Jim) Jiao
Email:  Phone: 631-632-4408
Office hours: Mon. 1:30-3:30pm & Wed. 2:30-3:30pm
Office: Math Tower P-137

TA: Prabhat Kumar
Email:
Office hours:  Tue. & Thur. 2:45 - 3:45pm
Office: Harriman 010



[ Course Description | Course Outline | Course Policy | Homework and Tests | References | University Policy ]

Course Description (back to top)


Direct and iterative methods for solving simultaneous linear equations. Matrix factorization, conditioning, stability, sparsity, and efficiency. Computation of eigenvalues and eigenvectors. Singular value decomposition.

Required Textbook

Prerequisite/Co-requisite

  • AMS 510 (linear algebra portion) or equivalent undergraduate-level linear algebra course. Familiarity of the following concepts is assumed: Vector spaces, Gaussian elimination, Gram-Schmidt orthogonalization, and eigenvalues/eigenvectors.
  • AMS 595/ (co-requisite for students without programming experience; offered as AMS 691 for Fall 2016).

Learning Objectives

The objective of this course is to introduce the key concepts and algorithms in numerical linear algebra, including direct and iterative methods for solving simultaneous linear equations, least squares problems, computation of eigenvalues and eigenvectors, and singular value decomposition. The key learning outcomes include the following:

  1. Master concepts and numerical methods for solving systems of linear equations
    • Gaussian elimination and its variants
    • Cholesky and LDL' factorizations
  2. Master concepts of orthogonality and numerical methods for linear least squares problems
    • Orthogonal matrices, projectors, and linear least squares
    • QR factorization using Gram-Schmidt orthogonalization, Householder reflectors, and Givens rotation
  3. Build fundamental understanding of conditioning and stability
    • Norms, condition numbers, and effect of rounding errors
    • Stable and backward stable algorithms
    • Backward error analysis of fundamental algorithms
  4. Master concepts and analyses based on eigenvalues and singular values and their numerical computations
    • Singular value decomposition and eigenvalue decomposition
    • Power method and similarity transformations
    • Reduction to Hessenberg and tridiagonal forms
  5. Build fundamental understanding of iterative methods for solving large sparse linear systems and computing eigenvalues
    • Conjugate gradient method, GMRES, and other Krylov subspace methods
    • Lanczos and Arnoldi iterations
    • Preconditioners for iterative methods
  6. Demonstrate programming skills for numerical methods using the abstractions of linear algebra

Course Outline (back to top)


Outline

  • Fundamentals (matrix notation and basic operations; vector spaces; algorithmic considerations; norms and condition numbers; decomposition of matrices)
  • Linear systems (triangular systems; Gaussian elimination; accuracy and stability; Cholesky factorization; sparse linear systems)
  • QR factorization and least squares (Gram-Schmidt orthogonalization; QR factorization with Householder reflection; updating QR factorization with Givens rotation; stability of QR factorization; least squares problems; rank-revealing QR factorization; SVD and low-rank approximations)
  • Eigenvalue problems (eigenvalues and invariant spaces; classical eigenvalue methods; QR algorithms; two-stage methods; Arnoldi and Lanczos iterations)
  • Iterative Methods for linear systems (basic iterative methods; conjugate gradient methods; minimal residual style methods; bi-Lanczos iterations; preconditioners)
  • Special topics (multigrid methods; compressed sensing; under-determined linear systems etc., if time permits)

Lecture Schedule and Slides

Course Policy (back to top)


Assignments

Homework assignments are due in class typically two weeks after they are assigned. You are allowed to discuss course materials and homework problems in small groups, but limited to discussion of general ideas only. You must write your solutions completely independently. Under no circumstances may you copy solutions from any source, including but not limited to other students solutions, official solutions distributed in past terms, and solutions from courses taught at other universities. Violation of these rules may result in disciplinary actions.

Exams

The exams (including two tests and the final exam) are closed-book, but you are allowed to bring a single-sided, one-page, letter-size cheat sheet, which you must prepare by yourself.

Attendance

All students are expected to attend all the lectures and exams.

Grading

  • Assignments: 30%

  • Two tests: 40%
  • Final exam: 30%

Homework and Sample Tests (back to top)

You are encouraged to typeset your homework solutions using LaTeX or using LyX (a very easy-to-use document processor, using LaTeX in the backend). (However, Microsoft Word alike are not recommended because of the equations.) Hand-written homework is due in class on the due date. Homework typeset using LaTeX or LyX is due at 11:59pm on the due date, through email submission of the PDF file to the TA.

All programming part of the homework are also due at 11:59pm on the due date, through email submission of the source code and the report to the TA.

Assignments

You are allowed to discuss course materials and homework problems in small groups, but limited to discussion of general ideas only. You must write your solutions completely independently. Under no circumstances may you copy solutions from any source, including but not limited to other students solutions, official solutions distributed in past terms, and solutions from courses taught at other universities. Violation of these rules may result in disciplinary actions.

Sample Tests

References (back to top)

References on Undergraduate-Level Linear Algebra

The following is an excellent text for reviewing fundamental concepts and some applications of linear algebra.

  • Gilbert Strang, Linear Algebra and Its Applications, 4th Edition, Brooks Cole, 2006.

Other References on Numerical Linear Algebra

The following books are graduate-level textbooks on numerical linear algebra, similar to the main textbook for this course.

  • James W. Demmel, Applied Numerical Linear Algebra, SIAM, 1997.

References on Iterative Methods and Multigrid Methods

The following books are for additional readings on iterative methods and multigrid methods, which are increasingly important but not covered in this course due to time constraint.

  • Anne Greenbaum, Iterative Methods for Solving Linear Systems, SIAM, 1997.
  • Yousef Saad, Iterative Methods for Sparse Linear Systems, SIAM, 2003.
  • William L. Briggs, Van Emden Henson, Steve F. McCormick, A Multigrid Tutorial, 2nd edition, SIAM, 2000.

References on Technical Writing

You can find some tips on using LyX etc. at here.

References on MATLAB Programming

References on C Programming

If you want to purchase a C book, a classical one is

  • B.W. Kernighan, D.M. Ritchie, C Programming Language (2nd edition). Prentice Hall, 1988.

There are some free online books linked at this "C Programming Language" page. Among these, the following book might be most appropriate.

  • M. Banahan, D. Brady and M. Doran, The C Book, second edition, Addison Wesley, 1991.

Another good starting point is the community-written C book is

Policies and Academic Integrity (back to top)


Americans with Disabilities Act

If you have a physical, psychological, medical or learning disability that may impact your course work, please contact Disability Support Services, ECC (Educational Communications Center) Building, room128, (631) 632-6748. They will determine with you what accommodations, if any, are necessary and appropriate. All information and documentation is confidential.

Academic Integrity

Each student must pursue his or her academic goals honestly and be personally accountable for all submitted work. Representing another person's work as your own is always wrong. Faculty are required to report any suspected instances of academic dishonesty to the Academic Judiciary. For more comprehensive information on academic integrity, including categories of academic dishonesty, please refer to the academic judiciary website at http://www.stonybrook.edu/uaa/academicjudiciary/

Critical Incident Management

Stony Brook University expects students to respect the rights, privileges, and property of other people. Faculty are required to report to the Office of Judicial Affairs any disruptive behavior that interrupts their ability to teach, compromises the safety of the learning environment, or inhibits students' ability to learn.