EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Minimizing the arithmetic and communication complexity of Jacobi’s method for eigenvalues and singular values: part one—serial algorithms

James Demmel, Hengrui Luo, Ryan Schneider, Yifu Wang

IMA Journal of Numerical Analysis · 05.11.2026

DOI: 10.1093/imanum/drag104 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IMA Journal of Numerical Analysis, online erschienen am 05.11.2026. Verfasst von James Demmel und 3 weiteren Autor:innen. Die Arbeit nennt 64 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We analyse several versions of Jacobi’s method for the symmetric eigenvalue problem. Our goal is to reduce the asymptotic cost of the algorithm as much as possible, as measured by the number of arithmetic operations performed and associated (serial or parallel) communication, i.e., the amount of data moved between slow and fast memory or between processors in a network. The first half of this effort, which considers the serial setting, is presented here; this paper contains rigorous complexity bounds for a variety of serial Jacobi algorithms, built on both classic $O(n^{3})$ matrix multiplication and fast, Strassen-like $O(n^{\omega _{0}})$ alternatives. In the classical case we show that a blocked implementation of Jacobi’s method attains the communication lower bound for $O(n^{3})$ matrix multiplication (and is therefore expected to be communication optimal among $O(n^{3})$ eigensolvers). In the fast setting we demonstrate that a recursive version of blocked Jacobi can go further, reaching essentially optimal complexity in both measures. We also derive analogous complexity bounds for (one-sided) Jacobi singular value decomposition algorithms. A forthcoming sequel to this paper will extend our complexity analysis to the parallel case.

Förderung

  • National Science Foundation

Zitieren

APA

Demmel, J., Luo, H., Schneider, R., & Wang, Y. (2026). Minimizing the arithmetic and communication complexity of Jacobi’s method for eigenvalues and singular values: part one—serial algorithms. IMA Journal of Numerical Analysis. https://doi.org/10.1093/imanum/drag104

Vancouver

Demmel J, Luo H, Schneider R, Wang Y. Minimizing the arithmetic and communication complexity of Jacobi’s method for eigenvalues and singular values: part one—serial algorithms. IMA Journal of Numerical Analysis. 2026. doi:10.1093/imanum/drag104

BibTeX
@article{Demmel2026,
  author = {Demmel, James and Luo, Hengrui and Schneider, Ryan and Wang, Yifu},
  title = {Minimizing the arithmetic and communication complexity of Jacobi’s method for eigenvalues and singular values: part one—serial algorithms},
  journal = {IMA Journal of Numerical Analysis},
  year = {2026},
  doi = {10.1093/imanum/drag104}
}
Kostenlos starten →