Iterative algorithms checklist

[ocramz]

From https://github.com/JuliaMath/IterativeSolvers.jl/issues/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