高斯消元变换与征服算法的替代方案

Question

在“转化和征服”中，高斯消元算法的时间复杂度为O(n^3)。是否有任何技术可以使该算法具有更高效的复杂度？

- ana

---

你想要求逆矩阵还是解决方程组？对于解决方程组，不要使用高斯消元法(GE)。对于求逆矩阵，当n很大时有一些算法是划算的。可以查看@Roland的答案。通常情况下使用高斯消元法(GE)，而且永远不要自己编写。 - Alexandre C.

@AlexandreC. 为了解决系统问题，还可以使用哪些算法？ - Shweta Aggrawal

Answer 1

有一些矩阵求逆的算法具有更好的渐进复杂度，例如，复杂度为O(n^2.807)的Strassen算法和复杂度为O(n^2.376)的Coppersmith–Winograd算法。

（请注意，矩阵乘法和矩阵求逆的复杂度是相同的）

- Roland

Answer 2

这取决于你要衡量哪种复杂性：

乘法次数：通过改变技术，你不能仅仅恶化高斯消元的复杂度。

时间步数：是的，行操作的并行实现将时间复杂度降至O(n)。

- Peter G.