Minimizing the Arithmetic and Communication Complexity of Jacobi's Method for Eigenvalues and Singular Values: Part Two -- Parallel Algorithms
Abstract
This paper presents several parallel versions of Jacobi's method for the symmetric eigenvalue problem and the SVD. A continuation of [Demmel, Luo, Schneider, & Wang 2025], we develop parallel Jacobi algorithms whose arithmetic cost is optimal and whose bandwidth or latency can match the corresponding lower bounds of parallel matrix multiplication. Our focus is a standard distributed-memory setting with variable processor layouts, including both 2D and 2.5D processor grids. In the 2D case, we demonstrate that a standard implementation of parallel Jacobi achieves a perfect speedup in arithmetic cost -- i.e., complexity O(n3/P) when done with P processors -- while hitting the 2D matrix-multiplication lower bound for bandwidth and (nearly) the lower bound for latency. By employing a 2.5D processor grid and leveraging 2.5D matrix multiplication, equivalently by increasing the memory per processor, we demonstrate that parallel Jacobi can achieve even lower bandwidth/latency, though we also prove that these costs cannot simultaneously match the best-known bounds for parallel matrix multiplication in any Jacobi algorithm. Finally, we extend our results to one-sided Jacobi SVD.
Related
- Arithmetic classification of the Dirichlet eigenvalues for a one-dimensional nonlocal p-Laplacian problem
- On the Optimal Linear Minimization Oracle Complexity of Active-Hull Methods for Minimizing Convex Hölder Smooth Functions
- Descending Everest, Part II: Oracle Complexity of Minimizing a Sum of Convex (L0,L1)-Smooth Functions
- Decision-focused predictions via pessimistic bilevel optimization: complexity and algorithms
- Square-root logarithmic bounds for the arithmetic complexity of factorial multiples
BibTeX
@misc{demmel2026minimizing,
title = {{Minimizing the Arithmetic and Communication Complexity of Jacobi's Method for Eigenvalues and Singular Values: Part Two -- Parallel Algorithms}},
author = {James Demmel and Hengrui Luo and Ryan Schneider and Yifu Wang},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.28952},
eprint = {2608.28952},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.28952},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Minimizing the Arithmetic and Communication Complexity of Jacobi's Method for Eigenvalues and Singular Values: Part Two -- Parallel Algorithms
AU - James Demmel
AU - Hengrui Luo
AU - Ryan Schneider
AU - Yifu Wang
PY - 2026
DA - 2026/08/28
PB - arXiv
DO - 10.48550/arxiv.2608.28952
UR - https://arxiv.org/abs/2608.28952
AB - This paper presents several parallel versions of Jacobi's method for the symmetric eigenvalue problem and the SVD. A continuation of [Demmel, Luo, Schneider, & Wang 2025], we develop parallel Jacobi algorithms whose arithmetic cost is optimal and whose bandwidth or latency can match the corresponding lower bounds of parallel matrix multiplication. Our focus is a standard distributed-memory setting with variable processor layouts, including both 2D and 2.5D processor grids. In the 2D case, we demonstrate that a standard implementation of parallel Jacobi achieves a perfect speedup in arithmetic cost -- i.e., complexity O(n^3/P) when done with P processors -- while hitting the 2D matrix-multiplication lower bound for bandwidth and (nearly) the lower bound for latency. By employing a 2.5D processor grid and leveraging 2.5D matrix multiplication, equivalently by increasing the memory per processor, we demonstrate that parallel Jacobi can achieve even lower bandwidth/latency, though we also prove that these costs cannot simultaneously match the best-known bounds for parallel matrix multiplication in any Jacobi algorithm. Finally, we extend our results to one-sided Jacobi SVD.
ER -