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

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

该项目主要考虑并行计算中通讯延迟的改进要慢于浮点运算速度和网络带宽的提高（浮点运算每年提高的速度是59%，带宽每年提高26%，而通讯延迟提高的幅度则小得多，每年只有15%左右），针对并行LU分解中的通讯延迟，提出基于binary tree和flat tree的选主元策略，并保持算法数值稳定性；相关工作已接收发表。算法用于大规模稀疏矩阵，由于非零元素的填充需要大量内存，涉及到矩阵重排技术（整体上用图剖分，如hMetis，PaToH等；局部用MMD，AMD等）。该并行策略还可用于RRQR，据分解所得上三角阵判定数值秩。相关内容已整理完稿即将发表。这里涉及到的LU和QR矩阵分解是数值计算中非常基本的问题，对它们的改进将会使已有数值软件更高效，具有理论意义和实际意义。