Numerical Linear Algebra

Jupyter notebooks on concepts from numerical/computational linear algebra. Inspired by Professor Rachel Thomas' class on computational linear algebra.

Topics

Introduction

• p-norms
• Lp-spaces
• Gauss-Legendre quadrature

Matrix decomposition

• SVD
  • Truncated SVD
  • Randomized SVD
• Non-negative matrix factorization (NMF)
  • Sparse NMF
• Principal component analysis (PCA) -[x] Robust PCA
• QR factorization
  • QR algorithm with Wilkinson shifts
• Golub-Kahan bidiagonalization with Householder reflectors

Eigenvalue algorithms

• Power iteration
• Power method with shifts and deflation
• Inverse iteration
• Rayleigh quotient iteration
• Arnoldi iteration
• Lanczos algorithm
• Cuppen's divide-and-conquer eigenvalue algorithm

Clustering

• T-distributed stochastic neighbor embedding (t-SNE)
• k-means clustering
• c-means clustering
• Spectral clustering

Preconditioners

• Jacobi
• Gauss-Seidel
• Cholesky factorization
  • Incomplete Cholesky with zero-fill (IC(0))
  • Incomplete Cholesky with threshold dropping (ICT)
• LDL factorization
• Successive over-relaxation (SOR)
• Symmetric successive over-relaxation (SSOR)
• Incomplete LU factorization (ILU)
• Sparse approximate inverse (SPAI)
• MR algorithm

Iterative methods

• Conjugate gradient (CG) method -[x] Preconditioned CG method
• Generalized minimal residual method (GMRES)
• Krylov subspaces
• Monte Carlo methods

Other

• Sparseness measure

Possible future topics

• Randomized linear algebra

Creating Conda environment

conda env create -f environment.yml
conda activate linalg

Resources

fast.ai Computational Linear Algebra course

Numerical Linear Algebra by Lloyd N. Trefethen and David Bau III

Matrix Computations by Gene H. Golub and Charles F. Van Loan

Iterative Methods for Sparse Linear Systems by Yousef Saad