AMS 526: Numerical Analysis I (Numerical Linear Algebra)
Fall 2011

Time: Monday & Friday 12:50 pm - 2:10 pm
Location: Physics P125

Instructor: Prof. Xiangmin (Jim) Jiao
Email: Phone: 631-632-4408
Office hours: Mon. & Fri., 2:20pm-3:40pm
Office: Math Tower 1-115

TA: Vladimir Dyedov
Office hours: Tue. & Thur. 3pm-4pm
Office: Math Tower S-250

[ Announcements | Course Description | Course Outline | Course Policy | Homework and Tests | Class Schedule  | References | Links ]

Announcements (back to top)

  • Class for 8/29 was cancelled due to Hurricane Irene.

Course Description (back to top)

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

Prerequisite/Co-requisite: AMS 510, AMS 595 (co-requisite for students without programming experience in C).

Required Textbook

  • Numerical Linear Algebra, by Lloyd N. Trefethen and David Bau, III, SIAM, 1997, ISBN 0-89871-361-7.

Reference Book (not required)

  • Matrix Computations, 3rd edition, by Gene H. Golub and Charles F. Van Loan, John Hopkins University Press, 1996, ISBN 0-8018-5414-8.

Course Outline (back to top)


  • Matrix fundamentals, orthogonality, norms, and SVD (2.5 weeks).

  • QR factorization, projectors, Gram-Schmidt algorithm, Householder triangulation, least squares problems (2 weeks).

  • Conditioning and stability (2.5 weeks).

  • Solution of linear system of equations, Gaussian elimination, pivoting, Cholesky factorization (2 weeks).

  • Eigenvalue problems, Hessenberg tridiagonalization, Rayleigh quotient, inverse power method, QR algorithm, Computing SVD (3 weeks).

  • Overview of iterative methods; Arnoldi/Lanczos iteration (1.5 week).

  • Linear algebra software (1 week).

Course Policy (back to top)


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.


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.


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


  • Assignments: 30%

  • Two tests: 40%

  • Final exam: 30%

Homework and Sample Tests (back to top)

For the computing assignments, you are encouraged to use the Linux machines in the Mathlab SINC Site at Math Tower S-235. You can remotely log onto the Linux computer using ssh. Before you can login, you may need to go to Math Tower S-235 to activate your account. You may use your own computer if it runs a UNIX system (such as Linux or Mac OS X), has a C compiler (such as gcc) and debugger (such as gdb and ddd), and has octave, gnuplot, and gv (for plotting).


Sample Tests

Class Schedule (back to top)


  • Important: All schedules are tentative and are subject to change.








Mon 8/29

Class cancelled due to Hurricane Irene

Fri 9/2

Course overview; matrix-vector multiplication

Lecture 1



Mon 9/5

No class (Labor Day observed)

HW1 out

Fri 9/9

Orthogonal vectors and matrices; Vector norm

Lecture 2



Mon 9/12

Matrix norms; Singular value decomposition

Lecture 3


Fri 9/6

More on singular value decomposition

Lecture 4



Mon 9/19

Projectors, QR factorization

Lecture 5


HW1 due; HW2 out

Fri 9/23

Gram-Schmidt orthogonalization; Householder triangularization

Lecture 6



Mon 9/26

More on Householder triangularization; Least squares problems

Lecture 7


Wed 9/28

Floating-point arithmetic; condition numbers

Lecture 8


Correction Day


Mon 10/3

Accuracy and stability; Review for test 1

Lecture 9


HW2 due

Fri 10/7

Test 1 (covers Part I and Part II of text book)

HW3 out


Mon 10/10

Stability of Householder QR and back substitution

Lecture 10


Fri 10/14

Conditioning of least squares problems

Lecture 11



Mon 10/17

Gaussian elimination and LU factorization

Lecture 12


Fri 10/21

Stability of LU; Cholesky factorization

Lecture 13


HW3 due; HW4 out


Mon 10/24

Linear algebra software; eigenvalue problems

Lecture 14



Fri 10/28

Reduction to Hessenberg form

Lecture 15



Mon 10/31

Rayleigh quotient iteration

Lecture 16


Fri 11/4

QR algorithm without shifts; Review for test 2

Lecture 17


HW4 due


Mon 11/7

Test 2 (covers material up to 10/31)

HW5 out

Fri 11/11

QR algorithm and simultaneous iteration

Lecture 18


Mon 11/14

QR algorithm with shifts

Lecture 19


Fri 11/18

Other eigenvalue algorithms

Lecture 20



Mon 11/21

Overview of iterative methods

Lecture 21


HW5 due; HW6 out

Fri 11/25

No class (Thanksgiving break)


Mon 11/28

Conjugate gradient method

Lecture 22


Fri 12/2

GMRES and other Krylov subspace methods

Lecture 23



Mon 12/5

Preconditioning; multigrid methods

Lecture 24


Fri 12/9



HW6 due


Thur 12/15

Final exam (2:15-4:45pm, Physics P125)

References (back to top)


References on C Programming

For students who are not familiar with C, you are encouraged to read some books on C programming. 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

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.

References on Iterative Methods

  • 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, SIAM, 2000.

Links (back to top)


  • Netlib contains a collection mathematical software. Some particularly useful software for numerical linear algebra include BLAS, LAPACK, ScaLAPACK, etc.

  • Jonathan R. Shewchuk, An Introduction to the Conjugate Gradient Method Without the Agonizing Pain, 1994. PDF (58 pages)