相关疑难解决方法(0)

我对大型稀疏矩阵的Cholesky分解感兴趣.我遇到的问题是Cholesky因子不一定是稀疏的(就像两个稀疏矩阵的乘积不一定稀疏).

例如,对于仅沿第一行,第一列和对角线具有非零的矩阵,Cholesky因子具有100%填充(下三角和上三角是100%密集的).在下图中,灰色不为零,白色为零.

我知道的一个解决方案是找到置换P矩阵并进行P ^T AP的Cholesky分解 .例如,通过应用排列矩阵来使用相同的矩阵,该排列矩阵将第一行移动到最后一行并且将第一列移动到最后一列,Cholesky因子是稀疏的.

我的问题是如何确定P一般？

要了解A和P ^T AP的Cholesky分解与更逼真的矩阵的区别,请参见下图.我从http://www.seas.ucla.edu/~vandenbe/103/lectures/chol.pdf中获取了所有这些图像.

据讲义说

存在许多启发式方法(我们没有涵盖)用于选择良好的置换矩阵P.

我想知道其中一些方法是什么(C,C++甚至Java中的代码都是理想的).

我已经问了类似的东西,但这次我会更具体.

我需要在for循环内执行通常大的正定对称矩阵(约1000x1000)的Cholesky分解.现在,要做到这一点,我一直试图:

1)Apache Math库

2)并行Colt库

3)JLapack库

在上述三种情况中的任何一种情况下,例如,与MATLAB相比,时间消耗非常长.

因此,我想知道在Java中是否存在用于Cholesky分解的高度优化的外部工具:例如,我一直在考虑CHOLMOD算法,其实际上是内部调用的MATLAB和其他工具.

我真的很感激能够对此事进行全面的反馈.