《IMA Journal of Numerical Analysis》：Minimizing the arithmetic and communication complexity of Jacobi’s method for eigenvalues and singular values: part one—serial algorithms
编辑推荐：
本研究分析了雅可比方法（Jacobi's method）的若干变体，用于求解对称特征值问题。研究目标在于尽可能降低算法的渐近成本，衡量指标包括执行的算术运算次数以及相关的（串行或并行）通信量，即数据在慢速与快速存储器之间或在网络处理器之间的移动量。本工作聚焦于
本研究分析了雅可比方法（Jacobi's method）的若干变体，用于求解对称特征值问题。研究目标在于尽可能降低算法的渐近成本，衡量指标包括执行的算术运算次数以及相关的（串行或并行）通信量，即数据在慢速与快速存储器之间或在网络处理器之间的移动量。本工作聚焦于串行环境下的前半部分；本文包含了针对多种串行雅可比算法的严格复杂度界限，这些算法既基于经典的O(n3)矩阵乘法，也基于快速的类斯特拉森（Strassen-like）O(n^(ω?))替代方案。在经典情形下，研究表明分块实现的雅可比方法能够达到O(n3)矩阵乘法的通信下界（因此有望在O(n3)特征值求解器中实现通信最优）。在快速算法情形下，研究表明递归版本的分块雅可比可以更进一步，在两项度量上均达到本质上最优的复杂度。研究人员还推导了（单边）雅可比奇异值分解（SVD）算法的相应复杂度界限。本工作的后续部分将把复杂度分析扩展到并行情形。
论文解读文章
研究背景与问题
对称特征值问题和奇异值分解（SVD）是数值线性代数中的核心计算，广泛应用于科学工程与数据分析领域。雅可比方法（Jacobi's method）作为最古老的求解算法之一，因其高相对精度（尤其在处理具有小特征值或小奇异值的矩阵时）而经久不衰。然而，现有雅可比算法面临一个两难困境：要么能达到算术或通信复杂度的理论下界但缺乏收敛性保证，要么具备收敛性保证却以次优复杂度为代价。随着问题规模增长，如何同时优化算术运算次数（浮点操作数，flops）和数据移动量（通信量）成为关键挑战。此外，矩阵乘法作为计算下界基准，其复杂度（经典O(n3)或快速O(n^(ω?))，其中ω?介于2到3之间）为评估雅可比方法提供了基线。本研究旨在填补这一空白，探索雅可比方法在串行环境下逼近甚至达到这些理论极限的可能性。
研究内容与结论
研究人员系统分析了多种串行雅可比算法变体的复杂度，包括经典标量版、分块版和递归版，并将其推广至单边雅可比SVD算法。主要结论如下：
- •
经典标量雅可比方法（Algorithm 1）的单次扫描（sweep）需Θ(n3)次算术运算，在假设√M ≤ n < M（M为快速存储器容量）时，通信复杂度下界为Ω(n?/M)，且可通过特定消去顺序达到该下界。
- •
分块雅可比方法引入块大小参数b（0 < b < n/2），将算术复杂度降至Θ(n2b + n3b^(ω?-3))，通信复杂度为O(n3/b)。当b = Θ(√M)时，该方法达到O(n3)矩阵乘法的通信下界，预期为O(n3)特征值求解器中的通信最优。
- •
递归（cache-oblivious）分块雅可比方法进一步实现了接近最优的复杂度：算术复杂度为O(n^(3(1-f)+ω?f))，通信复杂度为O(n^(3(1-f)+ω?f)/M^(ω?/2-1))，其中f（0<f<1）为对数块大小。当f趋近于1时，可获得近乎O(n^(ω?))的最优算术复杂度，尽管这需要极大的n。
- •
上述复杂度界限同样适用于单边雅可比SVD算法。
这些结果表明，通过引入树状递归结构，雅可比方法能够在保证收敛性的同时，首次同时达到算术与通信复杂度的理论下界，从而实现了收敛性与最优复杂度的统一。
关键技术方法
研究人员采用了以下几种关键技术方法：（1）经典标量雅可比方法（Algorithm 1），通过逐次正交相似变换消去非对角元，采用列循环次序（column-cyclic ordering）保证收敛，并通过几何论证证明通信下界；（2）分块雅可比方法（Section 3），将矩阵划分为大小为b的块，在块内执行雅可比旋转以减少通信，利用经典或快速矩阵乘法进行块更新，通过调整块大小b = Θ(√M)达到通信最优；（3）递归（cache-oblivious）分块雅可比方法（Section 4），引入树状递归结构，自动适应缓存层次，通过控制递归深度（对数块大小f）在算术与通信复杂度之间权衡，最终实现接近最优的复杂度。此外，研究人员还提出了随机消去顺序的收敛性命题（Proposition 1），证明了均匀随机选择非对角元几乎必然收敛。
研究结果
Section 2: 经典雅可比方法（Classical Jacobi）
通过分析Algorithm 1的单次扫描，证明了算术复杂度为Θ(n3)，并推导了通信下界Ω(n?/M)（定理2）。该下界在仅允许改变消去顺序的前提下是最优的，且可通过特定顺序达到。同时给出了随机消去顺序的收敛性保证（命题1）。
Section 3: 分块雅可比方法（Blocked Jacobi）
提出了分块实现，将矩阵划分为大小为b的块。算术复杂度降为Θ(n2b + n3b^(ω?-3))，通信复杂度为O(n3/b)。当b = Θ(√M)时，通信复杂度达到O(n3/√M)，即O(n3)矩阵乘法的通信下界（定理4）。
Section 4: 递归雅可比方法（Recursive Jacobi）
设计了cache-oblivious的递归分块算法。算术复杂度为O(n^(3(1-f)+ω?f))，通信复杂度为O(n^(3(1-f)+ω?f)/M^(ω?/2-1))，其中f为对数块大小（0<f<1）。通过使f趋近于1，可实现近乎O(n^(ω?))的算术复杂度，尽管这需要极大的n。
Section 5: 单边雅可比SVD算法（One-Sided Jacobi SVD）
将上述复杂度分析扩展至单边雅可比SVD算法，表明所有复杂度界限均可直接迁移至该设定。
Section 6: 数值实验（Numerical Examples）
通过少量数值示例验证了收敛性假设（即O(1)次扫描后收敛），为理论分析提供实验支撑。
总结与讨论
讨论部分：本文系统建立了多种串行雅可比算法的严格复杂度界限，将其置于数值线性代数两个并行努力方向的交汇点：一是以矩阵乘法算术复杂度稳定实现各类基本线性代数计算，二是最小化通信成本。研究指出，将标准雅可比的高相对精度优势扩展到本文提出的算法版本是一个有待未来解决的开放问题。此外，并行版本的复杂度分析将在后续工作中呈现。
研究结论翻译：对于经典情形，研究表明分块实现的雅可比方法能够达到O(n3)矩阵乘法的通信下界（因此有望在O(n3)特征值求解器中实现通信最优）。在快速算法情形下，研究表明递归版本的分块雅可比可以更进一步，在算术运算和串行通信两项度量上均达到本质上最优的复杂度。研究人员还推导了（单边）雅可比奇异值分解算法的相应复杂度界限。
