dev-aditya/arpack-refs

reference implementation of sparse eigen solvers

arpack-py

This is an attempt to write an eigensolver for sparse matrices without depending on ARPACK. Ultimately, the hope is to be a viable replacement for scipy.sparse.eigen.arpack, and remove the fortran dependency.

Why ?

ARPACK-NG is a fortran library for sparse eigen solvers. It has the following issues:

• the fortran code is not thread-safe. In particular, it is not re-entrant
• it does not incorporate some of the more recent improvements discovered for large problems, e.g. A Krylov-Schur Algorithm for Large Eigenproblems, G. W. Stewart, SIAM J. M ATRIX A NAL. A PPL ., Vol. 23, No. 3, pp. 601–614

Existing alternative implementations

• matlab:
  • KrylovSchur. Warning: no license.
  • Various implementations of Lanczos, including selective orthogonalization. Warning: no license.
• julia
  • Complete toolking in pure julia
    • includes linsolve, expm in addition to eigen value solvers
  • Faithful reimplementation of ARPACK in pure julia
  • The Arnold method with Krulov-Schur restart, natively in pure Julia
    • According to https://discourse.julialang.org/t/ann-arnoldimethod-jl-v0-4/110604, it is more stable than ARPACK.
    • implementation ~ 2k julia (not including tests)
    • license compatible with SciPy (MIT-like)

References

• Explanations of ARPACK implementation: https://dgleich.micro.blog/2021/04/21/a-small-project.html (arpack faithful reimplementation in julia)
• Mathematical references:
  • Lecture Notes on Solving Large Scale Eigenvalue Problems by Prof. Dr. Peter Arbenz from the Computer Science Department at ETH. See in particular the latest version of the notes
  • Templates for the Solution of Algebraic Eigenvalue Problems: a Practical Guide. Overview on numerical methods for eigen values, including dense and sparse
  • A shifted block Lanczos algorithm for solving sparse symmetric generalized eigenproblems.
  • Applied Numerical Linear Algebra
  • Implicit application of polynomial filters in a k-step Arnoldi method
    • An Implicitly Restarted Lanczos Method for Large Symmetric Eigenvalue Problems: a specialization of the implicit ARNOLDI to the hermitian operator case.