SuperDC Stable Superfast Divide-and-Conquer Eigenvalue Decomposition (in Matlab)

• Developers
  Xiaofeng Ou (ou17 -at- purdue.edu), Jianlin Xia, Purdue University. Feedback and suggestions are welcome.
  Provided as is. No warranty whatsoever. No liability whatsoever. (GNU General Public License v2.0)
• Applicability
  Rank-structured Hermitian matrices (represented/approximated by HSS forms). Examples:
  • Banded matrices
  • Toeplitz matrices (in Fourier space)
  • Some discretized integral equations
  • Schur complements in direct factorizations of some sparse matrices
  • Other dense or sparse matrices with small off-diagonal (numerical) ranks
• Features
  • No tridiagonal reduction needed
  • Nearly O(n) complexity for full eigenvalue decomposition
  • Nearly O(n) storage for all eigenvectors
  • Many stability features (stabilization like in tridiagonal divide-and-conquer, safeguards for clustered eigenvalues, stable FMM, etc.)
  • User controllable accuracy
• References
  
  • To cite the work (the package is used for)
    • X. Ou and J. Xia, SuperDC: Stable superfast divide-and-conquer eigenvalue decomposition, submitted (2021), arXiv:2108.04209.
    • X. Ou, J. Vogel, J. Xia, and Z. Xin, Efficient numerical computations via superfast eigenvalue decompositions, preprint, 2021.
  • Earlier related work
    • J. Vogel, J. Xia, S. Cauley, and V. Balakrishnan, Superfast divide-and-conquer method and perturbation analysis for structured eigenvalue solutions,
      SIAM J. Sci. Comput., 38 (2016), pp. A1358-A1382. (PDF--erratum. Journal article link)
    • D. Cai and J. Xia, A stable matrix version of the fast multipole method: stabilization strategies and examples, submitted. (PDF)
  • HSS related
    • J. Xia, S. Chandrasekaran, M. Gu, X. S. Li, Fast algorithms for hierarchically semiseparable matrices,
      Numer. Linear Algebra Appl., 17 (2010), pp. 953-976. (PDF. Journal article link)
    • J. Xia, Y. Xi, and M. Gu, A superfast structured solver for Toeplitz linear systems via randomized sampling,
      SIAM J. Matrix Anal. Appl., 33 (2012), pp. 837-858. (PDF. Journal article link)
    • J. Xia, S. Chandrasekaran, M. Gu, X. S. Li, Superfast multifrontal method for large structured linear systems of equations,
      SIAM J. Matrix Anal. Appl., 31 (2009), pp. 1382-1411. (PDF. Journal article link)
    • X. Liu, J. Xia, and M. V. de Hoop, Parallel randomized and matrix-free direct solvers for large structured dense linear systems,
      SIAM J. Sci. Comput., 38 (2016), pp. S508-S538. (PDF. Journal article link)
• Download (GNU General Public License v2.0)
  • Repository: SuperDC
  • Other packages needed: FMM1D, HSS
  • Place the following folders under one folder <superdc>:
    <superdc_1.0.0>, <fmm1d>, <hss>
  • Test routines under <superdc_1.0.0/tests>
  • Related tools: Structured Matrix Market