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: xiangmin.jiao@stonybrook.edu Phone: 631-632-4408
Office hours: Mon. & Fri., 2:20pm-3:40pm
Office: Math Tower 1-115

TA: Vladimir Dyedov
Email: vladimir@ams.sunysb.edu
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)


Outline

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


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)


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 compute.mathlab.sunysb.edu 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).

Assignments

Sample Tests

Class Schedule (back to top)

 

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


Week

Date

Topic

Slides

Reading

Notes

1

Mon 8/29

Class cancelled due to Hurricane Irene





Fri 9/2

Course overview; matrix-vector multiplication

Lecture 1

§I.1


2

Mon 9/5

No class (Labor Day observed)



HW1 out


Fri 9/9

Orthogonal vectors and matrices; Vector norm

Lecture 2

§I.2-3


3

Mon 9/12

Matrix norms; Singular value decomposition

Lecture 3

§I.3-4



Fri 9/6

More on singular value decomposition

Lecture 4

§I.4-5


4

Mon 9/19

Projectors, QR factorization

Lecture 5

§II.6-7

HW1 due; HW2 out


Fri 9/23

Gram-Schmidt orthogonalization; Householder triangularization

Lecture 6

§II.8


5

Mon 9/26

More on Householder triangularization; Least squares problems

Lecture 7

§II.10-11



Wed 9/28

Floating-point arithmetic; condition numbers

Lecture 8

§III.12-13

Correction Day

6

Mon 10/3

Accuracy and stability; Review for test 1

Lecture 9

§III.14-15

HW2 due


Fri 10/7

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



HW3 out

7

Mon 10/10

Stability of Householder QR and back substitution

Lecture 10

§III.16-17



Fri 10/14

Conditioning of least squares problems

Lecture 11

§III.18-19


8

Mon 10/17

Gaussian elimination and LU factorization

Lecture 12

§IV.20-21



Fri 10/21

Stability of LU; Cholesky factorization

Lecture 13

§IV.22-23

HW3 due; HW4 out

9

Mon 10/24

Linear algebra software; eigenvalue problems

Lecture 14

§V.24-25

example.c


Fri 10/28

Reduction to Hessenberg form

Lecture 15

§V.26


10

Mon 10/31

Rayleigh quotient iteration

Lecture 16

§V.27



Fri 11/4

QR algorithm without shifts; Review for test 2

Lecture 17

§V.28

HW4 due

11

Mon 11/7

Test 2 (covers material up to 10/31)



HW5 out


Fri 11/11

QR algorithm and simultaneous iteration

Lecture 18



12

Mon 11/14

QR algorithm with shifts

Lecture 19

§V.29



Fri 11/18

Other eigenvalue algorithms

Lecture 20

§V.30-31


13

Mon 11/21

Overview of iterative methods

Lecture 21

§VI.32,33,36

HW5 due; HW6 out


Fri 11/25

No class (Thanksgiving break)




14

Mon 11/28

Conjugate gradient method

Lecture 22

§VI.38



Fri 12/2

GMRES and other Krylov subspace methods

Lecture 23

§VI.35,39


15

Mon 12/5

Preconditioning; multigrid methods

Lecture 24

§VI.40



Fri 12/9

Review

review


HW6 due

16

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)