大规模稀疏线性系统的稀疏近似逆预处理技术

Sparse Approximate Inverse Preconditioning for Large Sparse Linear Systems

作者: 专业:数学 导师:贾仲孝 年度:2013 学位:博士 

关键词
预处理 稀疏近似逆 舍弃阈值 非规则稀疏问题 Sherman-Morrison-

Keywords
preconditioning, sparse approximate inverse, dropping tolerance, irregularsparse problem, Sherman-Morrison-Woodbury formula
        科学与工程计算中的核心问题之一是求解大规模稀疏线性系统,此类问题广泛来源于椭圆或抛物型偏微分方程的离散、电路的设计与计算机分析等诸多应用领域.预处理的Krylov子空间方法已成为目前求解此类问题的重要途径.稀疏近似逆预处理技术因其广泛的适用性和高度的并行性已得到普遍关注,并成为时下最流行最重要的预处理技术之一.为了尽可能保证此类预处理技术的有效性和实用性,人们通常在构造预处理子过程中采用非常关键的“舍弃”策略.具有普适性的舍弃策略是设定舍弃阈值,即给定一个阈值,然后将绝对值在其下的元素重置为零.一直以来,人们往往根据经验或直觉选择阈值,例如,简单选为103,104等.但是,这样经验性的选择会带来很大风险,很可能导致整个预处理过程的失败.因此,阀值的选择对于算法的健壮性和有效性至关重要,其中应存在深刻的数学机理,应当引起足够的重视.然而,迄今为止,稀疏近似逆在此方面仍旧存在理论和技术上的空白.本论文对舍弃阈值的选择建立了严格的数学理论,揭示了阈值与稀疏近似逆预处理子的质量之间的紧密关系.应用这些理论,分别针对F-范数最小化和因子形式的稀疏近似逆技术,本论文为舍弃阈值的选择提供了合理有效的标准,从而显著提高了这两类稀疏近似逆算法的健壮性和有效性.大量的数值实验证明了本文所给出的阈值选择标准的良好适用性.一个稀疏矩阵有若干列稠密时,我们称它为非规则稀疏矩阵,现实应用中需要求解大量的系数矩阵非规则稀疏的大规模线性方程组.一些稀疏近似逆算法(如SPAI、PSAI等)往往对规则稀疏问题的预处理有效,但用于非规则问题时就会遇到本质的困难,由于算法本身原因可能会导致预处理子质量低下甚至无效,或者导致算法开销太大不可承受.以著名的Sherman-Morrison-Woodbury公式为核心工具,本论文找到了一种将稀疏近似逆技术有效、廉价地应用于非规则稀疏问题的途径,仔细考察和分析了其中涉及到的若干重要问题,并给出了较充分的数学理论.本论文测试了大量的非规则稀疏矩阵,对比了新方法与直接应用稀疏近似逆技术的标准方法,充分证明了新方法在实用性和有效性方面的突出优势,从而大大扩展了稀疏近似逆预处理技术的适用范围.
    Solving large sparse linear systems is a central task in scientific and engineeringcomputing. The systems are from the real-world application such as the discretization ofelliptic and parabolic PDEs, the design and computer analysis of circuits, etc. Precondi-tioned Krylov subspace methods have been one class of the most well-known solvers forthese systems.Sparse approximate inverse (SAI) techniques have attracted the universal attentionduetotheirwideapplicabilityandhighparallelism,andhavebecomeoneclassofthemostpopular and important general-purpose preconditioning for Krylov solvers. To make SAIpreconditioners practical and effective, one has to use dropping techniques during thesetup process. That is to say, if the size of an entry is below some positive quantity (drop-ping tolerance), then it is set to zero. Therefore, dropping tolerance criteria play a centralrole in SAI preconditioning. However, one commonly takes some small quantities em-pirically or intuitively, say103,104, etc. as the dropping tolerances. Such empiricallychosen tolerances are not robust and at risk, may not be effective or even lead to failurein preconditioning. Therefore, dropping tolerances criteria strongly affect the robustnessand effectiveness of a SAI preconditioner and deserve enough attention, and there mustexist some deep mechanism behind them. However, this area still exists some kind ofblank in theory and technology. In the thesis, we establish a rigorous mathematical the-ory that reveals the intrinsic relationship between the dropping tolerances and the qualityand effectiveness of the SAI preconditioner. Using the theory, we derive an adaptivedropping criterion that is used to drop entries of small magnitude dynamically during thesetup process of the preconditioners, for F-norm minimization-based SAI and factorizedSAI,respectively. Numerical experimentsconfirm thetheoryand illustratetherobustnessand effectiveness of the dropping criteria.A sparse matrix is called irregular sparse if it has at least one dense column. Thereare quite a lot of irregular sparse problems in applications. Some SAI preconditioningprocedures such as SPAI and PSAI algorithms are usually effective for regular sparseproblems. However, when applied to irregular problems, they probably encounter intrin-sic difficulty, such as the low equality and the ineffectiveness of the preconditioner, or the large unacceptable cost. In the thesis, using the Sherman-Morrison-Woodbury formula asa powerful tool, we propose an approach to making the SAI algorithms more practicaland effective for irregular sparse problems. We carefully investigate and analyze severalimportant practical issues, and provide solid mathematical theory support, making ourapproach robust and effective. Numerical results from the vast majority of irregular prob-lems demonstrate the considerable superiority of our approach to the direct application ofSAI procedures to the original problem. In conclusion, our approach widely extends thepracticability of the SAI techniques.
        

大规模稀疏线性系统的稀疏近似逆预处理技术

摘要3-4
Abstract4-5
主要符号对照表8-9
第1章 引言9-20
    1.1 预处理技术的发展及现状10-18
        1.1.1 ILU预处理技术的发展及现状11-14
        1.1.2 SAI预处理技术的发展及现状14-17
        1.1.3 其他预处理技术的发展及现状17-18
    1.2 本论文的研究内容和成果18-20
第2章 大规模稀疏线性系统的迭代法与SAI预处理技术20-50
    2.1 引言20-21
    2.2 定常迭代法21-23
    2.3 Krylov子空间方法23-25
    2.4 线性方程组预处理的动机25-28
        2.4.1 方程组扰动分析26-27
        2.4.2 CG与GMRES的收敛性分析27-28
    2.5 大规模稀疏线性系统的预处理技术28-33
        2.5.1 ILU预处理技术30-32
        2.5.2 SAI预处理技术32-33
    2.6 基于F-范数最小化的SAI预处理技术33-44
        2.6.1 理论基础34-37
        2.6.2 预测近似逆的稀疏结构 J37-39
        2.6.3 SPAI算法39-41
        2.6.4 PSAI算法41-44
    2.7 因子形式的SAI预处理技术44-50
        2.7.1 AINV算法45-47
        2.7.2 FSAI算法47-50
第3章 F-范数最小化的SAI中舍弃阈值的选择50-73
    3.1 引言50-51
    3.2 准备工作51-52
    3.3 几个重要定理52-56
    3.4 舍弃阈值的选择56-59
    3.5 数值实验59-72
        3.5.1 PSAI(tol)的数值结果61-68
        3.5.2 三种静态SAI过程的数值结果68-72
    3.6 本章小结72-73
第4章 因子形式的SAI舍弃阈值的选择73-79
    4.1 引言73
    4.2 LDU分解与双边共轭过程的关系73-76
    4.3 AINV算法舍弃阈值的选择76
    4.4 数值实验76-78
    4.5 本章小结78-79
第5章 非规则问题的基于F-范数稀疏近似逆技术79-98
    5.1 引言79-80
    5.2 原问题的规则化变换80-82
    5.3 方法的提出和若干重要细节问题的解决82-88
    5.4 数值实验88-97
        5.4.1 SPAI相关的数值结果91-93
        5.4.2 PSAI(tol)相关的数值结果93-95
        5.4.3 SPAI和PSAI(tol)的有效性比较95-97
    5.5 本章小结97-98
第6章 总结和展望98-101
    6.1 全文总结98
    6.2 本论文创新点98-99
    6.3 对未来工作的展望99-101
参考文献101-113
致谢113-115
附录A BPSAI过程中的LS解的块形式更新115-117
附录B Davis关于非规则稀疏问题在现实中的调研117-120
附录C 一些相关定义120-121
附录D 数值实验环境121-122
个人简历、在学期间发表的学术论文与研究成果122


本文地址:

上一篇:外力场中的Hartree方程的动力学研究
下一篇:不确定图与不确定网络

分享到: 分享大规模稀疏线性系统的稀疏近似逆预处理技术到腾讯微博           收藏
发表网-大规模稀疏线性系统的稀疏近似逆预处理技术-在线咨询