Iterative algorithms checklist

[ocramz]

From JuliaLinearAlgebra/IterativeSolvers.jl#1

A comprehensive listing of methods in the references.
Please remove any methods are impractical/obsolete and add methods worth implementing to the list.

Linear systems

• Stationary methods
  • Jacobi (LT)
  • Gauss-Seidel (LT)
  • Successive overrelaxation, SOR (LT)
  • Symmetric SOR (LT)
• Nonstationary methods
  • GMRES (LT, Saa)
  • MINRES (LT)
  • Conjugate Gradients, CG (LT)
  • LSQR
  • LSMR
  • BiCGStab(l) (Sle, Sle2)
  • Chebyshev iteration (LT)
  • Quasi-Minimal Residual, QMR (LT)

(Generalized) eigenproblems

• Without subspace
  • (Shift-and-inverted) power iteration (ET)
  • Rayleigh Quotient Iteration [1]
• Krylov subspace methods
  • Implicitly restarted Lanczos (ET, IRLBA)
  • Implicitly restarted Arnoldi (ET)
• Other subspace methods
  • Jacobi-Davidson method (ET)
  • Locally-optimal (block-)preconditioned conjugate gradient (LO(B)PCG)
  • Accelerated Rayleigh Quotient Iteration [1]
  • (Shift-and-inverted) subspace iteration (ET)

Singular value decomposition

• Golub-Kahan-Lanczos (ET)

References

LT: Templates for the Solution of Linear Systems: http://www.netlib.org/linalg/html_templates/report.html
ET: Templates for the Solution of Algebraic Eigenvalue Problems : http://web.eecs.utk.edu/%7Edongarra/etemplates/book.html
IRLBA : augmented implicitly restarted Lanczos bidiagonalization algorithm (IRLBA) : https://bwlewis.github.io/irlba/
Saa: GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems (pdf) : http://www.stat.uchicago.edu/%7Elekheng/courses/324/saad-schultz.pdf
Sle: BiCGstab(l) and other hybrid Bi-CG methods (pdf) : http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.139.7946&rep=rep1&type=pdf
Sle2: BICGSTAB(L) for linear equations involving unsymmetric matrices with complex spectrum http://www.emis.ams.org/journals/ETNA/vol.1.1993/pp11-32.dir/pp11-32.pdf
TB: Numerical linear algebra : http://www.worldcat.org/title/numerical-linear-algebra/oclc/36084666
HV: Iterative Krylov methods for large linear systems : http://www.worldcat.org/title/iterative-krylov-methods-for-large-linear-systems/oclc/837021440
LOBPCG : Accelerating the LOBPCG method on GPUs using a blocked Sparse Matrix Vector Product

• Anzt, Tomov, Dongarra - http://icl.cs.utk.edu/news_pub/submissions/ut-eecs-14-731.pdf

[1] Low-priority methods: they are quite expensive per iteration.

[ocramz]

Alternating Anderson-Richardson method: An efficient alternative to preconditioned Krylov methods for large, sparse linear systems https://arxiv.org/abs/1606.08740