求解大规模线性方程组的并行多层低秩分解方法研究

项目名称： 求解大规模线性方程组的并行多层低秩分解方法研究

项目编号： No.11301506

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

立项/批准年度： 2014

项目学科： 数理科学和化学

项目作者： 王武

作者单位： 中国科学院计算机网络信息中心

项目金额： 22万元

中文摘要： 在科学与工程计算中，主要任务之一是求解由偏微分方程或积分方程离散得到的大规模线性方程组。因此对于大规模稠密问题或病态的稀疏问题，研究快速、高效的并行求解算法尤为重要。本项目基于多层半可分（HSS）结构矩阵的低秩分解理论,研究快速求解线性方程组的数值方法及相关并行算法。多层递归低秩分解方法具有线性或近似线性的复杂度，而且能达到任意给定的精度，因此既可以作为快速、稳定的直接法求解器，也可以用来构造高效的预条件子，加快迭代求解器的收敛速度。 基于并行多层递归低秩分解方法，本项目拟开发能够在分布式计算平台上快速求解上亿未知量规模的电磁散射问题的并行程序，并运用所形成的算法和程序在高性能计算环境下完成具有复杂纳米结构的光子晶体和电磁超材料的上亿规模的数值模拟，推进快速并行算法在计算电磁学中的应用。

中文关键词： HSS 结构矩阵；随机取样；ULV 分解；低秩压缩；并行算法

英文摘要： One of the main tasks in scientific and engineering computing is solving large systems of linear equations derived from discretized partial differential equations or integral equations. So it's particularly important to study fast and efficient parellel solvers for large-scale dense systems or ill-conditioned sparse systems. Based on the theory of low-rank factorizations for the hierarchical semiseparatable structured (HSS) matrix, this project will study numerical methods and related parallel algorithms on the fast solution of linear equations. Hierarchically recursive low-rank factorization method has a linear or near linear complexity, and can reach any given accuracy, so it can not only be used as a fast and stable direct solver, but also be used to construct a high-efficient preconditioner to accelerate the convergence of iterative solvers. Based on the parallel hierarchical recursive low-rank factorization method, this project will develop a parallel program for the fast solution of electromagnetic scattering problems with hundreds of millions of unknows on distributed computing platform, and use the formed algorithm and program to simulate hundred-million scale problems about photonic crystals and electromagnetic metamaterials with complex nano-structures under high performance computing enviro

英文关键词： HSS structured matrices；randomized sampling；ULV factorization；low-rank compression；parallel algorithm