这不太可能。Demmel 和合著者有一篇名为“Fast Linear Algebra is Stable”的论文表明，用于特征分解（达到有限精度）的数值稳定算法的成本至少与矩阵乘法一样多，即$O(n^{\omega})$， 在哪里$2 \leq \omega \leq 2.376$（或者）。将 LDL 或 Cholesky 分解转换为特征分解的方法通常使用极分解（计算此值的牛顿方法为$O(n^{\omega})$) 或其他计算类似信息的方法（例如，SVD，$O(n^{3})$）。

我认为稀疏在这里也没有太大帮助。迭代方法（Krylov 子空间方法，如 Lanczos 或 Arnoldi）将是$O(n^{3})$（那是，$O(n^{2})$每个特征值）。我不知道任何用于极分解的稀疏直接方法。存在稀疏 SVD，这将比密集算法节省一些费用，但我不知道是否存在表明它将是的结果$O(n^{2})$.

优化算法将使用稀疏 Cholesky、LDL 或 LU。稀疏 Cholesky 的复杂度为$O(nnz(L))$， 在哪里$nnz$是非零函数的数量，对于稀疏 LU，它是$\Omega(nnz(L) + nnz(U))$和$O(n^{\omega})$. 但是，这些算法将对每个线性求解执行一次因式分解，每次迭代至少一次。

关于这个主题的算法复杂性，我能想到的所有东西都用完了。二次复杂度算法在密集情况下不太可能，在稀疏情况下也可能不太可能。