我很难找到以下问题的直接答案：
如果您计算 nxn 正定对称矩阵 A 的 Cholesky 分解，即因子 A=LL^T 且 L 为下三角矩阵，则复杂度为 O(n^3)。对于稀疏矩阵，显然有更快的算法，但要快多少呢？
对于这样一个具有 m<n^2 个非零条目的矩阵，我们可以实现什么复杂度？
编辑：我的矩阵也大约是主对角线（只有对角线和下方和上方的一些相邻对角线是非零的）。
PS 我最终对 Julia 或 Python 中的实现感兴趣。Python 有 sksparse.cholmod 模块（https://scikit-sparse.readthedocs.io/en/latest/cholmod.html），但我不清楚他们使用的是什么算法以及它的复杂性是什么。不确定 Julia，如果有人能告诉我。
这只能在 P=NP 的情况下准确地回答任意矩阵......所以一般来说不可能回答。时间复杂度取决于使用的填充减少排序，它试图获得 NP 难题的近似解。
但是，对于来自规则方形 2D 或 3D 网格的矩阵的特殊情况，有一个答案。在这种情况下，嵌套剖析给出了渐近最优的排序。对于 2D s-by-s 网格，矩阵的维度为 n = s^2，我认为大约有 5n 个条目。在这种情况下，L 有 31*(n log2(n)/8)+O(n) 个非零，工作量是 829*(n^(3/2))/84+O(n log n)。对于 n = s^3 的 3D s-by-s-by-s 网格，L 中有 O(n^(4/3)) 个非零值，并且需要 O(n^2) 个操作来计算 L。
Python Library Numpy (Numerical Python) 也有一个用于 cholesky 的模块 - np.linalg.cholesky，我已经提供了文档的链接，尽管我不确定这是否能回答这个问题，可能需要一些实验。
不完整的 Cholesky 分解值得研究，它有多种变体，但通常要么只计算输入中非零的三角因子中的条目，要么使用分解的低秩近似。从您的问题中不清楚您为什么对渐近复杂性感兴趣，但是使用高斯过程标签我可以猜到您正在分解协方差核矩阵并在推理过程中反复求解线性系统。在这类应用程序中，不完全分解最常用作预处理器——虽然它不精确，但它非常有效，易于增量更新，并且可以大大加快求解器的速度。
但是，在应用程序中，您的问题的答案很可能与最适合您的目的的方法无关。不完全分解有 $O(n log(n)^k)$ 时间算法，由于与具有最低指数的矩阵乘法算法相同的原因，这些算法没有实际用途。知道您的应用程序究竟需要什么将告知您的选择，但您已经拥有了最好的工具来找到 - 花几分钟时间编写一些代码来生成合成数据或对不同大小的真实数据进行采样并在与您对应用程序感兴趣的方式相同。如果您要进行一次分解并求解多个系统，则进行分解的时间可能会因求解而相形见绌。如果您要进行许多分解，尤其是每次从头开始，运行时间的常数和线性因素会产生更大的影响。另外，稀疏模式和内核本身可以对相同算法的性能产生巨大影响。构造具有完全密集的协方差矩阵、三对角精度矩阵和 Cholesky 分解的核并不困难，该分解只是矩阵的下三角部分，正好可以按对角矩阵进行缩放（1d 中的指数核同时具有所有 3 个） . 首先配置文件，最后优化。s 构造具有完全密集的协方差矩阵、三对角精度矩阵和 Cholesky 分解的核并不困难，该分解正好是矩阵的下三角部分，正好可以按对角矩阵进行缩放（1d 中的指数核同时具有所有 3 个） . 首先配置文件，最后优化。s 构造具有完全密集的协方差矩阵、三对角精度矩阵和 Cholesky 分解的核并不困难，该分解正好是矩阵的下三角部分，正好可以按对角矩阵进行缩放（1d 中的指数核同时具有所有 3 个） . 首先配置文件，最后优化。