C++中最快的计算矩阵秩的方法/库是什么？

Question

C++中最快的计算矩阵秩的方法/库是什么？

c++windowslinear-algebrasparse-matrix

4

什么库可以最快地计算矩阵的秩？或者，是否有任何开放的代码可以相当迅速地完成此操作？

我正在使用Eigen3，但它似乎比Python的numpy rank函数要慢。我只需要这一个函数运行得快，绝对没有其他问题。如果您建议的软件包除此之外都无关紧要，甚至包括易用性。

我所看到的矩阵大小通常为 n × (n选择3)，其条目为1或0....主要是0。

谢谢。

编辑1：秩在R上。

- ReverseFlow

你介意算法是随机的吗？但它只要终止就能保证正确，或者即使它是随机的，并且有些几率出错呢？ - Chris Beck

我不关心跟随，我只关心速度。 - ReverseFlow

如果你可以容忍大约0.0001%的失败率，根据这篇论文，你应该能够在矩阵大小的线性时间内使用他们的第一个结果（第2页）完成它。https://cs.uwaterloo.ca/~lapchi/papers/matrix-rank.pdf 编辑：（3）结果也应该能为您完成同样的事情，但实现可能更难，我不确定。重点是，如果您有n乘以n选择3的大小，则论文中的值n^{w}在这些表达式中是可以忽略的，因为w < 3。不知道这些在实践中如何，但理论上我想它们是最优的。 - Chris Beck

1

n的取值范围为5到12。所有列都有3个1，其余为0。 - ReverseFlow

你是如何在Eigen中计算rank的？有许多不同的方法可以做到这一点，它们在速度、精度等方面具有不同的权衡。（如果您添加了“eigen”标签并显示了您的Eigen代码，则更有可能获得有关如何改进它的提示） - Marc Glisse

显示剩余7条评论

1个回答

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

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

- Matthew Gunn · Accepted Answer

总的来说，BLAS/LAPACK函数非常快。这个链接建议使用GESVD或GESDD函数来计算奇异值。非零奇异值的数量将是矩阵的秩。

LAPACK是numpy使用的库。

简而言之，您可以使用相同的LAPACK库调用。除非稀疏性和特殊结构允许更有效的方法，否则很难超越BLAS/LAPACK函数。如果是这样，您可能需要查找实现稀疏SVD求解器的替代库。

还要注意，有多个BLAS/LAPACK实现。

更新

这篇文章似乎认为LU分解在计算秩时不可靠，最好使用SVD。在使用BLAS/LAPACK之前，您可能需要查看eigen调用的速度（我从未使用过eigen），以避免麻烦。