algorithm - 线性方程的快速近似解？

Question

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

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

编辑：

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

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

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

Answer 1

有迭代方法，如 Jacobi、Gauss-Seidel、cg、GMRES 等。

Answer 2

对于对称矩阵，共轭梯度法实现起来很简单，并且会击败大多数其他迭代方法（例如 Gauss-Seidel、SOR）。主循环由矩阵向量乘法和一些其他向量操作组成。

一旦你得到它的工作，你可以使用预处理来进一步提高收敛性。

Answer 3

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

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

试试这个搜索。