三对角矩阵特征系统的并行算法

计算科学 线性代数 算法 本征系统
2021-11-28 03:40:39

我正在对一个大型稀疏矩阵（约 200 万个元素）进行 Lanczos 对角化。Lanzcos 算法中的几乎所有步骤都是在 GPU 上并行完成的，除了对 Lanczos 矩阵进行对角化以检查收敛性。为此，我一直在使用来自 Numerical Recipes 的 TQLI 算法。是否有方法可以找到并行或易于并行化的三对角矩阵的特征系统？是否存在 TQLI 的并行版本？

3个回答

TQL 不能并行化。

标准的并行算法是 Cuppen 的算法：

JJM Cuppen，对称三对角特征问题的分治法，1980。http
://www.springerlink.com/content/t21365q2gh702714/

也可以看看：

F. Tisseur，分布式内存架构上对称特征值问题的并行分治算法，1999
http://eprints.ma.man.ac.uk/981/01/covered/MIMS_ep2007_225.pdf

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.75.4109&rep=rep1&type=pdf

http://www14.in.tum.de/konferenzen/Jass09/courses/2/Kleine_Albers_paper.pdf

我建议使用像SLEPc这样的库，其中包含许多不同方法的接口，用于以串行或并行方式求解特征系统。用户手册包括对解决特征值问题的几种不同方法的参考。

我建议对并行三对角特征求解使用并行多重相对鲁棒表示 (PMRRR)。它可以计算三对角矩阵的所有特征对O(n2)并行工作。您可以在此处找到该方法的概述。ScaLAPACK 中也有实现，这里讨论。

其它你可能感兴趣的问题
上一篇最快的高维数据 PCA 算法 下一篇科学代码性能的底层结构是什么？