没有包装的快速矩阵反转

假设我有一个正方形matrixM。假设我想invert矩阵M。没有包装的快速矩阵反转

我正在尝试使用gmpy2中的分数mpq作为我的矩阵M的成员。如果你不熟悉这些分数，它们在功能上与Python的内置软件包fractions相似。唯一的问题是，没有任何软件包会颠倒我的矩阵，除非我将它们从分数形式中提取出来。我需要分数形式的数字和答案。所以我将不得不编写自己的函数来反转M。

有一些我可以编程的已知算法，例如gaussian elimination。然而，性能是一个问题，所以我的问题如下：

是否有一个计算快速算法，我可以用来计算矩阵的逆M？

来源

2017-06-02 Paul Terwilliger

要做到这一点，任何合理的快速算法都将作为扩展在C中实现。另一种方法是将它们全部乘以它们的GCD或它们的分母的乘积以将它们整合为整数，并使用具有C扩展的包并且花费更多时间来优化。这是'O（n）'，所以除非反转算法比'O（n）'好，否则不会影响时间复杂度。 – Artyer

你看过sympy吗？它适用于gmpy2和矩阵：http://docs.sympy.org/dev/modules/matrices/matrices.html#linear-algebra – denfromufa

是的，但sympy的反转比手动编码高斯消除要慢。我可以分享我的代码用于高斯消除与基准。 –

还有什么你知道这些矩阵？例如，对于symmetric positive definite矩阵，Cholesky分解允许您比您提到的标准高斯 - 乔丹方法更快地进行反演。

对于一般的矩阵求逆，Strassen algorithm会给你一个比Gauss-Jordan更快的结果，但比Cholesky慢。

看起来好像你想得到确切的结果，但如果你对近似反演很好，那么有算法可以比前面提到的算法快得多。

但是，您可能需要问自己，您是否需要整个矩阵反转以适合您的特定应用。根据你在做什么，使用另一个矩阵属性可能会更快。根据我的经验，计算矩阵求逆是一个不必要的步骤。

我希望有帮助！

来源

2017-06-08 12:24:15

没有包装的快速矩阵反转

回答

相关问题