特征值问题的高可扩展性算法研究

结题报告

项目介绍

AI项目解读

基本信息

批准号：
11801021
项目类别：
青年科学基金项目
资助金额：
25.0万
负责人：
徐飞
依托单位：
北京工业大学
学科分类：
A0501.算法基础理论与构造方法
结题年份：
2021
批准年份：
2018
项目状态：
已结题
起止时间：
2019-01-01 至2021-12-31

项目参与者：
许秀秀；姜坤；徐小帆；罗秀红；吴绍武；
关键词：
有限元方法多重网格法特征值问题并行计算自适应方法

项目摘要

Solving eigenvalue problem is an important issue in modern scientific and engineering computing. Due to the constraint of computation consumption and storage, the efficient solution of eigenvalue problem is always a hot and difficult topic in scientific research. Although it has been long studied, its achievements are far less than those of boundary value problems. For the general elliptic boundary value problem, a complete fast solution system, such as multigrid method and adaptive method, has been developed. Based on the multilevel correction method, we try to improve the efficiency of solving eigenvalue problem by merging the multigrid method and adaptive method, so as to derive the optimal computational work similar to the boundary value problem. Besides, because of the good parallel structure of the multilevel correction method, this project will further improve the efficiency and scale of computation based on the parallel technique to form an efficient and highly scalable finite element method for solving eigenvalue problems.

特征值问题的求解是现代科学与工程计算领域内的一个重要问题。由于计算量和存储量的限制，特征值问题的高效求解一直是科学研究的热点和难点。其研究历史虽然很长，但目前取得的成果远不及边值问题的相关研究。对于椭圆边值问题，已经发展了比较完备的快速求解体系，比如多重网格方法和自适应方法。本项目中，我们将在多重校正算法的基础上，把求解椭圆边值问题中采用的多重网格算法、自适应加密技术等高效算法融合进来，提升特征值问题求解的效率，使求解特征值问题具有与求解边值问题相似的最优计算复杂度。此外，由于多重校正算法具备很好的并行结构，本项目将在此基础上进一步结合并行技术来提升计算的效率和规模，最终得到特征值问题的高效、高可扩展性的有限元算法。

结项摘要

在科学与工程计算中，特征值问题的求解是一类重要的科学问题。但和边值问题不同，特征值问题需要的计算量随着问题规模的增加呈指数增长，因此特征值问题的高效求解一直是科学研究的热点和难点。其研究历史虽然很长，但目前取得的成果远不及边值问题的相关研究。对于椭圆边值问题，已经发展了比较完备的快速求解体系，比如多重网格方法和自适应方法。但对特征值问题，相应的高效数值算法较少。如何设计高效的数值求解方法，使特征值问题的求解达到和边值问题一致的计算效率，仍然是一个具有挑战性的问题。..本项目研究特征值问题求解的高效、高可扩展性数值算法。我们在多重校正算法的基础上，把求解椭圆边值问题中采用的多重网格算法、自适应加密技术等高效算法融合进来，极大提升了特征值问题求解的效率，使求解特征值问题具有与求解边值问题相似的最优计算复杂度，并将其应用到一些科学研究的具体实践中去。针对特征值问题设计的算法都具有严格的理论证明，为实际应用了提供理论保障。此外，本项目也结合并行计算技术及多重校正技巧，设计出具有较高可扩展性的并行算法，满足了高性能计算的要求。..在本项目的研究过程中，我们设计了特征值问题求解的多重网格方法并给出了严格理论证明，使特征值问题的求解获得了线性的计算量估计。我们设计了特征值问题求解的自适应算法并给出了严格理论证明，使特征值问题的自适应算法具有最优的误差估计和计算复杂度估计。这一系列算法使得求解特征值问题具有和求解边值问题一致的计算量。同时，本项目结合并行计算技术，设计了基于特征值划分的新型并行算法，实现了大规模特征值问题、多个特征值的高效计算，得多了近乎百分百的并行效率。此外，我们还将设计的算法推广到更复杂的非线性特征值题，设计了非线性特征值问题求解的多重网格、自适应以及并行算法，极大提升了非线性特征值问题的求解效率。