**Numerical Linear Algebra**

**Fall 2017**- Prerequisites: mathematical analysis, advanced linear algebra, matlab
- If any other mathematical topic is as fundamental to the mathematical sciences as calculus and differential equations, it is numerical linear algebra. -- Trefethen & Bau, 1997.

## Contents

## Instructor & Tutor

- Kui Du, School of Mathematical Sciences, Xiamen University Email: kuidu@xmu.edu.cn Tel: 0592-2580672
- Xiao Qi, School of Mathematical Sciences, Xiamen University Email: 530194696@qq.com

## Textbooks (bookcover)

- Numerical Linear Algebra, Lloyd N. Trefethen and David Bau, III, SIAM, 1997
- (supplement) Applied Numerical Linear Algebra, James Demmel, SIAM, 1997
- (supplement) Numerical Linear Algebra and Applications, Biswa Nath Datta, 2nd Edition, SIAM, 2010
- (supplement) Matrix Computations, Gene H. Golub and Charles F. Van Loan, 4th Edition, Johns Hopkins University Press, 2013
- (supplement) Numerical Linear Algebra with Applications Using MATLAB, William Ford, Academic Press, 2015
- (supplement) MATLAB Primer, Timothy A. Davis, 2011

## Lecture contents

- Part 1: Inner product, Orthogonality, Vector/Matrix norm, Singular value decomposition (SVD)
- Part 2: QR factorization, Projector, Classical/Modified Gram-Schmidt, Householder reflector, Givens rotation, Least squares
- Part 3: Conditioning, Floating point arithmetic, Stability
- Part 4: LU factorization, Gaussian elimination, Pivoting, Cholesky factorization, Jocabi, Gauss-Seidel and SOR methods
- Part 5: Eigenvalue problem, Power/Inverse iteration, Rayleight quotient iteration, Hessenberg/Tridiagonal reduction, QR algorithm, other algorithms
- Part 6: Other topics depending on time: Krylov subspace methods, Preconditioning, FFT and Structured matrices, Pseudospectra, ...
- Matlab m-files for lectures

## Grading policy (tentative)

- Assignment 30% + Programming 30% + Final exam 40%
- Bonus 5% (overall performance: classroom and discussion participation, learning attitude, reading project, ...)
- Assignment + Programming + Bonus <= 60%

## Homework (tentative)

- Discussion is permissible. However, transcribed solutions and copied programs are both unacceptable!
- Write solutions of assignments in
**english and latex**are highly encouraged. - Write programming reports by
**matlab**(you can use matlab's 'publish'). Submit your programming reports to: xmunla@163.com. Only one pdf-file should be submitted with filename studentnumberPx.pdf for Programming x. For example, if your student number is 19020150000000, then your submission for Programming 1 is 19020150000000P1.pdf. Submissions in other file formats are unacceptable! - Late submissions for assignments and programming reports get only
**half**the score. Unaccepted submissions get**0**score.**No exceptions!**

- Assignment 1. (latex file) Deadline:
- Assignment 2.
- Assignment 3.
- Assignment 4.
- Assignment 5.
- Programming 1.
- Programming 2.
- Programming 3.
- Programming 4.
- Programming 5.

## Reading project (tentative)

- David S. Watkins, The QR algorithm revisited, SIREV, 2008
- Mark Embree, The Arnoldi eigenvalue iteration with exact shifts can fail, SIMAX, 2009
- Jared L. Aurentz and Lloyd N. Trefethen, Block operators and spectral discretizations, SIREV, 2017
- Kui Du, Jurjen Duintjer Tebbens, and Gerard Meurant, Any admissible harmonic Ritz value set is possible for GMRES, ETNA, 2017

## Others

- Chebfun-numerical computing with functions by Trefethen's team
- Matrix computations/Numerical linear algebra by Jianyu Pan
- An introduction to the conjugate gradient method without the agonizing pain by Jonathan Shewchuk
- Randomized algorithms in numerical linear algebra by Ravindran Kannan and Santosh Vempala, Acta Numerica, 2017
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions by N. Halko, P. G. Martinsson, and J. A. Tropp, SIREV, 2011
- Numerical linear algebra in data mining by Lars Elden, Acta Numerica, 2006