轨迹的并行、无矩阵估计

计算科学 线性代数 并行计算 无基质
2021-12-24 06:06:27

如果仅通过并行的“matvec”例程知道它对向量的作用,那么估计大型分布式矩阵的迹线的最佳方法是什么?

在我感兴趣的应用程序中,matvec 例程来自 PDE 的离散化。在大多数情况下,我无法修改此例程。

我不需要机器精度,并且对中等精度感到满意。

1个回答

首先,对于您实际上不需要的大多数稀疏矩阵nmatvecs 与单位向量来确定对角线条目。相反,如果您知道稀疏模式,您可以“着色”离散化中的节点,以便相同颜色的节点不会在矩阵中耦合。因此,您应该能够使用类似的东西来计算矩阵的迹线O(10100)matvecs,与矩阵的大小无关(但取决于您使用的离散化类型)。

但使用随机算法估计轨迹可能更便宜。我手头没有参考资料,但是如果您搜索“用于估计矩阵轨迹的随机算法”,您会找到一些。