基于多层半可分结构矩阵的快速算法与并行实现

摘要：

基于多层半可分(HSS)结构矩阵的快速算法可有效降低具有数值低秩属性的稠密线性方程组求解的复杂度.采用随机取样和保结构秩显(SPRR)分解相结合的方法替代秩显QR(RRQR)分解可以快速构造HSS结构矩阵.该方法将压缩构造HSS结构矩阵转换成小矩阵计算,减少存储和通信开销,使构造HSS结构矩阵的时间复杂度进一步降低.在分布式机群上采用ScaLapack的二维循环块分布方式存储各矩阵块,将HSS树和处理机网格进行映射.构造HSS结构矩阵的并行算法包括对矩阵的多层块压缩,数据交换和重分布,然后结合并行ULV分解和并行三角求解实现快速并行求解,分析了该并行算法的复杂度.最后以二维电磁散射问题为例,数值结果表明该算法不仅比直接LU分解快一个数量级,而且具有良好的并行可扩展性.

关键词：多层半可分、数值低秩、随机取样、ULV分解、并行算法

所属期刊栏目：38

资助基金：国家自然科学基金项目11301506,91430214;863项目2015AA01A303

在线出版日期：2018-05-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共12页

页码：37-48