矩阵分解的低延迟并行算法

项目名称： 矩阵分解的低延迟并行算法

项目编号： No.10901125

项目类型： 青年科学基金项目

立项/批准年度： 2010

项目学科： 自动化技术、计算机技术

项目作者： 向华

作者单位： 武汉大学

项目金额： 16万元

中文摘要： 在并行计算中通讯延迟的改进要慢于浮点运算速度和网络带宽的提高，针对并行LU分解中的通讯延迟，提出一种新的选主元策略以减少其通讯开销，改进目前ScaLAPACK中的PDGETRF函数。考察此分解过程的增长因子和向后误差，用统计和分析的方法总结分析这一选主元策略的数值稳定性。对于大规模稀疏矩阵的LU分解，非零元的填充需要大量内存，矩阵重排技术变得格外重要，对矩阵重排整体上利用图剖分技术，如hMetis，PaToH等；局部用MMD，AMD等方法，来减少非零元的填充，并使重排后的数据结构适合于并行化。类似的并行策略用到Rank Revealing QR，以少的通讯次数选出范数较大的列，从而减少通讯延迟，改进ScaLAPACK中的PxGEQPF函数，提高现有数值软件的效率。并将结果用于低秩逼近，构造Schur补预条件子，改善Krylov子空间迭代法的收敛。

中文关键词： 通讯延迟；选主元；LU分解；QR分解；并行计算

英文摘要：

英文关键词： communication latency；pivoting strategy；LU decomposition；QR decomposition；parallel computing