Near-Linear Runtime for a Classical Matrix Preconditioning Algorithm

doi:10.1145/3779224

2026-02-01

PRE

DOI：10.1145/3779224

原文求助

摘要

En 中文

1960年，Osborne提出了一种具有出色数值性能的矩阵平衡迭代算法。如今，它已成为Python、Julia、MATLAB、EISPACK、LAPACK等主流软件包中计算方阵（非对称）特征值及其他线性代数子程序前的默认预处理步骤。尽管该算法应用广泛，但其运行时间的理论保证一直难以获得：首个多项式时间保证仅在近十年才被提出，而近期接近线性的运行时间仅限于具有重要差异的Osborne算法变体，这些变体虽然分析更简单，但实际运行较慢。本文通过证明实践中默认的矩阵平衡预处理Osborne原始算法实际上具有接近线性的运行时间，弥补了理论与实际之间的长期差距。该运行时间保证（1）在输入规模上最多只有一个对数因子是最优的，（2）是首个不主导下游任务（如特征值计算）运行时间的Osborne算法运行时间，（3）优于所有其他Osborne算法变体的理论运行时间。

Keyword:

Osborne's algorithm

matrix balancing

near-linear runtime

convex optimization

coordinate descent

cyclic algorithms