线性方程的快速近似解？

Question

我需要求解 N 个线性方程组作为数值优化器的中间步骤。AFAIK 相当简单的算法精确地做到这一点是 O(N^3) （尽管我在一些数学论文中看到了一个非常复杂的算法，可以用 O(N^2.8) 和一个巨大的常数来完成）。在某些情况下，N 很大，即几千。

有没有什么好方法可以在小于 O(N^3) 的时间内获得线性方程组的近似解？

编辑：

如果有帮助的话，这里有一些更多的细节。

1. 我的矩阵是对称的，并且不稀疏。

2. 这是 Newton-Raphson 的二阶导数矩阵。我正在尝试在 2000 维空间中优化某些内容。

Answer 1

是的，如果你从它们的系数得到的矩阵是稀疏的。例如，如果您有一个三对角矩阵，则可以使用“Rightlay”方法（保加利亚语，不确定确切的翻译），该矩阵的运算时间为 O(N)。还有其他算法仍然是 O(N^3)，但如果矩阵符合它们所需的某些不变量（稀疏、对角占优、三角形等），则可以获得令人难以置信的结果。

如果您坚持使用基于不变量的特定方法，那么进一步加快速度的唯一方法就是使用多线程。

尝试这个搜索。