兰州大学机构库 >数学与统计学院
大型稀疏结构线性系统的快速算法研究
Alternative TitleFast algorithm research for solving large sparse structured linear systems
廖丽丹
Subtype博士
Thesis Advisor张国凤
2018-04-11
Degree Grantor兰州大学
Place of Conferral兰州
Degree Name博士
KeywordPDE 约束优化问题 图像去噪 鞍点问题 复对称问题 Krylov 子空间方法 预处理子 最优参数
Abstract

许多工程和科学计算的数值求解均可转化为大型线性和非线性方程组的求解. 如不可压液态流问题的数值求解, 具有广泛应用的PDE 约束问题以及病态的反问题数值求解等. 通过适当的数值离散, 它们最终均可转化为具有某些特殊结构的大型线性方程组. 这些线性方程组一般具有某种特殊结构, 如块结构:2*2 块或3*3块结构,大型、 稀疏病态, 有些甚至是奇异的. 高效快速求解这类线性系统一直是科学计算的核心问题之一, 具有非常重要的意义. 面对实际问题中涉及的形态各异的大型系数结构线性系统, 如何高度利用问题自身的结构和特性来构造稳定、高效的算法是现代数值计算的重要课题和研究热点之一。

本论文分共有七章, 主要研究离散PDE 约束优化问题、几类PDE 及一些不适定问题中涉及的大型线性和非线性方程组的求解, 重点针对具有块2*2结构的线性系统, 提出了一系列具有针对性的快速、稳定的迭代算法及预处理技术。第一章介绍了问题的研究背景、研究意义以及研究现状, 并简单介绍了本文的主要研究内容和创新点。第二章主要研究由几类特殊的偏微分方程(如Helmholtz 方程) 离散得到的复对称线性方程组的数值求解问题. 针对复线性方程组的实等价块2*2结构的线性系统,得到了两类具有更好特性的块预处理子. 所得到的块预处理子在某些特定条件下有更聚集的特征值分布, 理论证明了预处理矩阵特征值的界与问题参数无关, 体现了它的鲁棒性和有效性. 数值例子进一步验证了理论的正确性以及新预处理子的有效和鲁棒性。第三章主要研究了由PDE 约束优化问题导出的离散结构线性系统的快速算法.针对离散得到的特殊的块2×2 结构复线性方程组进一步研究了目前最有效的三个块预处理子, 发现并导出了三个预处理子间的关系, 即相应的预处理矩阵的特征值都是受同一矩阵的影响. 通过讨论最优参数的选取得到了三个预处理的最有效的形式. 此外, 基于多步预处理的思想, 又构造了两个两步预处理子. 理论分及数值实验都证明了新的两步预处理子比现有的预处理子有更聚集的谱分布, 且与问题参数无关, 说明了所提出的预处理子的有效性和鲁棒性。第四章针对图像复原问题所得到的结构化线性系统我们提出了有效的数值算法.基于Pan 等人(SIAM, 2014) 提出的一类新的 HSS (NHSS) 预处理子, 通过引入两个迭代参数, 提出了一个广义的两半步交替方向(GNHSS) 的迭代方法, 理论分析了该迭代方法的收敛性质以及预处理矩阵的谱性质, 讨论了双参数的选择方式. 数值试验表明 GNHSS 迭代法及相应预处理子都是非常有效的。第五章主要针对不可压缩Navier-Stokes 方程导出的鞍点结构的线性系统, 设计了一种有效的预处理子, 研究了预处理矩阵的谱性质, 给出了新的预处理子与已有预处理子的算法复杂性比较, 表明给出的预处理子在计算方面具有很大的优势. 此外,我们还讨论了最优参数的选择并给出了一种比较实用的参数选择方法。第六章针对一般广义鞍点问题, 考虑了一种块乘积型高效预处理子及迭代方法.研究了迭代方法的收敛性条件以及预处理矩阵的相关性质, 讨论了参数的选择办法.数值实验结果表明新预处理子及参数选择办法是非常有效的。第七章对本文做了简要总结并对未来的工作进行了展望.

Other Abstract

Large sparse structured linear (algebraic) systems arise from a wide variety of applications in computational science and engineering fields,such as the incompressible liquid flow problem,the widely used PDE constraint problems,the ill-conditioned inverse problems and so on.By using proper discretization,these problems can eventually be changed into large linear systems,which generally have some special structure,ill posed and singular properties.Numerical solution for solving  linear systems is a central task in scientific and engineering computing,which is of great both theoretical and practical significance.In the face of  the different structures of linear systems in practical problems,how to make use of the structure and characteristics of the problem itself to construct a stable and efficient algorithm is an important aspect of modern numerical computation and a research focus of the numerical scientists.This thesis aims at numerical solutions for solving the large sparse structured linear systems arising in the discrete PDE constrained optimization problems, a few kinds of PDE and ill-posed problems, focuses on a piece of 2*2 structure of linear system and propose a series of efficient and robust iteration methods and preconditioning techniques.

In Chapter 1,we review the backgrounds and motivations of this thesis are introduced, and reviews the present research situation.The main contents, results and innovations of this thesis are given in the end of this chapter. In Chapter 2, we mainly study the numerical solution of the complex symmetric linear equations derived from several special partial differential equations (such as the Helmholtz equation).Two classes of block preconditioners with better properties are obtained to solve the the real equivalent block 2 ×2 linear system. Particularly, when 𝑊 − 𝑇 or 𝑇 − 𝑊 is symmetric positive semidefinite, the exact eigenvalue bounds are obtained which are much tighter than the state of the art. At last, numerical experiments are presented to show the effectiveness of the optimized preconditioners. In Chapter 3, we mainly study the fast algorithm of the discrete structural linear system derived from the PDE constrained optimization problem. For a class of twoby-two complex linear systems arising from the optimal control problems constrained by time-harmonic parabolic equations,we further study and optimize the most effective three block preconditioners. The relationship between the three preconditioners is found and derived, i.e.,the eigenvalues of the corresponding preconditioned matrix are all affected by the same matrix. By discussing the selection of the optimal parameters, three most effective preconditioners are obtained. In addition, based on the idea of multi-step preconditioning,two two-step preconditioners are constructed. Theoretical analysis and numerical experiments have proved the effectiveness and robustness of these preconditioners.In chapter 4,we propose an effective iterative method for the structured linear system obtained from the image restoration problem. Based on new HSS (NHSS) preconditioner proposed by Pan et al.in 2014.By introducing two iterative parameters, a generalization of the NHSS preconditioner and the corresponding iterative method are presented. The convergence properties of the iterative method and the spectral properties of the preconditioned matrix are analyzed theoretically.The optimal choice of the parameters are discussed.Numerical experiments show that the GNHSS iterative method and the corresponding preconditioner have excellent performance when accelerating the GMRES method.In Chapter 5,we mainly focus on solving the saddle point structure linear system derived from the incompressible Navier-Stokes equations. An effective preconditioner is designed, the spectral properties of the preconditioning matrix are studied. The comparisons of complexity of the algorithms between the new preconditioner and the existing preconditioner are obtained,which shows that the new preconditioners enjoy the computational advantage. In addition,we also discuss the choice of optimal parameters and give a more practical selection for selecting parameter. Numerical examples are given to verify the validity and stability of the new preconditioners. In Chapter 6, a block product (BP) preconditioner is established to solve block two-by-two linear systems. Convergence analysis of the corresponding BP splitting iteration and spectral propensities of the BP preconditioned matrix are studied in depth.Besides,an explicit expression of quasi-optimal parameter is obtained and a practical estimate for the quasi-optimal parameters is given.Moreover,the implementation of the preconditioned method is given, which shows that the computational cost of applying the BP preconditioner to accelerate GMRES is lower as compared with some other preconditioners.The numerical results show that the BP preconditioner costs much less time at each step and is effect under the parameters we have provided. Finally, a summary of the full thesis and future research directions are discussed in the last chapter. 

URL查看原文
Language中文
Document Type学位论文
Identifierhttps://ir.lzu.edu.cn/handle/262010/225566
Collection数学与统计学院
Recommended Citation
GB/T 7714
廖丽丹. 大型稀疏结构线性系统的快速算法研究[D]. 兰州. 兰州大学,2018.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Altmetrics Score
Google Scholar
Similar articles in Google Scholar
[廖丽丹]'s Articles
Baidu academic
Similar articles in Baidu academic
[廖丽丹]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[廖丽丹]'s Articles
Terms of Use
No data!
Social Bookmark/Share
No comment.
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.