检查一个方阵是否为满秩的最有效方法是什么？

Question

检查一个方阵是否为满秩的最有效方法是什么？

arraysalgorithmmatrixrank

4

我目前正在处理一个问题，需要定期检查大量（1000+）的8x8方阵，以确定它们是否为满秩。

实际上，我并不关心矩阵的秩，只关心它是否达到最大秩。什么是最有效的算法来找出答案?

--编辑-- 有关这些矩阵的更多信息：很遗憾，它们是任意的；既不对称也不稀疏。而且，其中一些系数是双曲函数的评估，因此通常是非常大的数字。已经处理了该问题的符号版本，尽可能简化行和列（并尝试用tanh代替尽可能多的sinh和cosh）。

- Isaia Ismaele

1

欢迎来到SO！这些矩阵是任意的、稀疏的、对称的还是其他什么？ - Sven-Eric Krüger

谢谢！我添加了一些信息到问题中。 - Isaia Ismaele

这些矩阵是否至少是正定的？如果是，您可以使用Cholesky算法进行高斯消元，该算法在计算上比朴素方法更快。 - Sven-Eric Krüger

我认为Cholesky分解只适用于对称正定（半）矩阵，而它们并不是对称的。 - Hans Olsson

如果你有数百万个8x8矩阵，使用类似莱布尼兹公式的朴素算法在GPU上计算它们的行列式并将其与0进行比较可能会更快。即使这涉及到$O(n!)$的工作量而不是高斯消元的$O(n^3)$，但它避免了任何条件分支，因此可以在GPU上以最快的速度运行。（条件分支可能会导致CPU上的相同减速，但影响较小。） - j_random_hacker

@j_random_hacker，这实际上非常有趣，但幸运的是我不需要进行那么多的计算。 - Isaia Ismaele

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- anatolyg · Accepted Answer

使用高斯消元法将矩阵转换为三角形式。如果在此过程中任何对角线元素变为0，则该矩阵的秩较小。

由于您拥有如此多的独立矩阵，因此可以轻松进行并行计算（易于在线程之间进行最小同步）。