TIES581 Numerical linear algebra

News

Contents

• Direct solution of Ax=b
• Iterative solvers (Krylov) and preconditioning
• Numerical solution of Ax=λx
• SVD and its applications

Literature

• Prof. Youcef Saad's numerical linear albegra books:
  • linear systems book
    Material to be read:
    • Chapter 1: Basic linear algebra concepts (if not already familiar): QR factorization, Givens and Householder transformations, similarity, Schur decomposition, etc.
    • Chapter 3: Sparse storage schemes, graph representation of a sparse matrix, permutations, basic ideas behind sparse direct methods
    • Chapter 5: General projection methods
    • Chapter 6: Krylov subspace methods (Arnoldi, CG, GMRES)
    • Chapter 9: Preconditioning - the basic ideas
    • Chapter 10: Some preconditioners (basic iterative methods as preconditioners, incomplete factorization based preconditioners)
  • eigenvalue book
    Material to be read:
    • Chapter 4: Power methods, deflation, general projection methods
    • Chapter 5: Simple subspace iteration
    • Chapter 6: Arnoldi and Lanczos methods (basic ideas)
• Some dense linear algebra (eigenvalues, SVD) (see book Golub \& van Loan, "Matrix computations" for more details)

Hands on examples and exercises (in Matlab / Octave) ()

• Basic matrix computations: matrix_vector.m, diag_mul.m
• Permutations and sparse matrix computations: perm_demo.m, test_sparse.m, sparse_perm.m (save this matrix file to your working directory: sparse1.mat) sparse_perm2.m, sparse_perm3.m
• Exercise #1: Find info about the symbolic Cholesky factorization (i.e. determining the nonzero pattern of triangular factors before the actual factorization). In Matlab you can do it using symbfact ;)
• exercises + notes #2
• Test simple Krylov method: test_krylov.m, fom.m, matrix5p.m
• Conjugate gradient with improved stopping criterion cgeig_test.m, cgeig.m
• *updated* Test Matlab's preconditioned conjugate gradient method: precon_demo.m
• (updated luinc -> ilu) Test Matlab's preconditioned GMRES method: precon_demo2.m Exercises: 1) Try to find the best compromise in the Krylov subspace size (restart parameter). 2) Does the bicgstab method perform better ?
• Nonlinear systems can be solved using Krylov based methods too: nonlin_gmres_demo.m
• Some eigenvalue exercises
• Simple image compression using SVD: svd_image.m, lena512.bmp

Some other optional reading material

• Algorithms for sparse linear systems ** NEW ** (open access book)
• Numerical linear algebra methods for data mining
• The University of Florida Sparse Matrix Collection
• Wikipedia article on matrices (for a quick ref :-)
• Some history of eigenvalue solvers...
• History of QR decomposition...

Related YouTube videos

• 1976 Singular value decomposition film
• Direct methods for sparse matrices
• Solving Large Sparse Linear Systems: The Exascale Challenge