大型线性系统与分数阶方程求解及在电磁计算中的应用

发布时间：2018-03-31 07:02

本文选题：Krylov子空间方法　切入点：线性方程组　出处：《电子科技大学》2017年博士论文

【摘要】：科学计算中的大量问题都与如何高效地求解大型线性系统有关。如电磁散(辐)射数值仿真,材料力学中的近场动力学特征建模,模拟物质的反常(对流)扩散过程中的分数阶微分方程求解等。因此,线性方程组的高性能算法研究也成为科学计算中活跃的分支之一。通常情况下,许多工程仿真所涉及的线性方程组的系数矩阵都是具有某些特定的结构,如何科学合理地挖掘和利用这些结构性质来构造快速稳健的线性系统解法是一个重要的课题。本文针对几类具有特殊结构的大型线性方程组的高性能解法进行了系统的研究,特别是研究了复对称线性系统的Krylov子空间算法、求解具有Toeplitz矩阵结构的线性系统的预处理迭代法以及求解位移线性方程组的迭代法。研究内容与主要成果可以归纳如下:1.针对求解大型复对称线性系统问题,两种流行的Krylov子空间算法(即COCG和COCR)都是基于斜投影的原理创建的,在实际计算中常常出现不规则的收敛行为,甚至发生停滞或中断。为了改善这一数值不足,推导出两类新的Krylov子空算法,即QMRCOCG算法和QMRCOCR算法,改善了COCG算法和COCR算法法的数值行为,消除了残差收敛行为不规则的现象。最后,将新导出的两类算法应用于三组典型的电磁仿真模型问题的求解中,数值实验表明,这两种新方法可有效的平滑残差曲线,保证了数值计算的稳健性。2.对Clemens等在1996年提出的SCBiCG(Γ,n)算法的回溯研究发现,该算法实际上包含了van der Vorst和Melissen提出的COCG算法,Clemens等提出的BiCGCR算法以及Sogabe和Zhang提出的COCR算法。将SCBiCG类算法的原理等做了系统的数学阐述,证明了BiCGCR算法和COCR算法是数学上等价的,但由于后者只需要两次内积运算而略具优势。最后,通过求解三组典型的电磁计算模型问题产生的离散线性系统实验,对比了COCG,BiCGCR,COCR和SQMR四种Krylov子空间算法的数值表现。BiCGCR和COCR在数值收敛行为也非常相似,且比COCG算法的收敛行为要更平滑。此外针对准静磁场数值离散系统建立了一种两步预处理技术。数值实验证实了该预处理技术特别适合处理上述准静磁场仿真问题。3.材料科学中的近场动力学建模中常用到伪积微分方程,由于算子的非局部性,使得该类方程的数值离散产生稠密线性方程组。Tian和Wang于2013年发现了该离散线性系统具有Toeplitz结构,并利用了快速Toeplitz矩阵-向量乘法来提升CG算法的计算效率。为了提高CG算法处理该病态Galerkin离散系统的效率,本文挖掘了系数矩阵具有Toeplitz结构加对称三对角部分的信息之后改进了经典的循环预处理子,并分析了预处理矩阵的特征值几乎都聚集在1附近。最后,数值实验说明了所提出的新循环预处理子在加速CG算法的计算效率上是有效的。4.将Sogabe提出的BiCR算法和Abe及Sleijpen提出的BiCRStab算法推广到求解位移线性系统问题,并成功导出了两种新的Krylov子空间算法,即位移BiCR算法和位移BiCRStab算法。因为这两种算法法保持了Krylov子空间的位移不变性,从而在求解位移线性方程组时需要的矩阵-向量乘法个数等价于求解单个系统时的矩阵-向量乘法次数,而且新算法大大减少了计算量和存储量。数值实验表明,这两个新方法都分别比位移BiCG和位移BiCGStab算法收敛的快,而且通常比后两者具有更光滑的残差收敛行为。5.针对空间分数阶扩散方程,设计了一种新的数值求解格式。首先对分数阶扩散方程做空间半离散,将原问题转化为求解一个常微分方程组。最后利用无条件稳定的时间离散方法将离散问题转化为一个大型结构线性系统。因其系数矩阵具有Toeplitz结构,则Krylov子空间算法并不需要存储系数矩阵来快速地求解该离散线性系统。为了加快算法的收敛速度,构造了块循环(block circulant,BC)及带循环块的块循环(block circulan with circulant block,BCCB)两种预处理子。并通过理论和数值实验分析了所设计的快速算法能比较有效地处理分数阶扩散方程,同时避免经典的显隐式格式所面临的复杂稳定性分析等问题。
[Abstract]:A lot of problems in scientific computing are related to how to efficiently solve large linear systems. Such as electromagnetic powder (spoke) jet numerical simulation, near field dynamics modeling in mechanics of materials, simulation of material (anomalous convection) in the diffusion process of fractional differential equation solving. Because of this, high performance algorithm of linear equations the group has also become one of the active branches in scientific computing. Normally, many engineering simulation involves the coefficient matrix of the linear equations are with certain structure, how to excavate and utilize these properties to construct fast and robust solution of linear systems is an important subject scientifically and reasonably. Large linear equation the high performance solution aimed at several classes with special structure are studied, especially the research of the Krylov subspace algorithm for complex symmetric linear systems, solving with Toeplitz Linear system matrix structure of the preconditioned iteration method for solving displacement and linear equations of the iterative method. The research content and the main results can be summarized as follows: 1. for solving large complex symmetric linear systems, two kinds of popular Krylov subspace algorithm (COCG and COCR) are created based on the principle of oblique projection, convergence the irregular behavior often appear in the actual calculation, even stopped or interrupted. In order to improve the numerical problems, derived two new kinds of Krylov subspace algorithm, QMRCOCG algorithm and QMRCOCR algorithm, improved COCG algorithm and COCR algorithm of numerical method, eliminate the residual convergence behavior of irregular phenomenon. Finally, the new solution derived two kinds of algorithm is applied to the problem of the electromagnetic simulation model of three typical in numerical experiments show that these two kinds of methods can effectively ensure the smooth residual curve, numerical calculation The robustness of.2. proposed in 1996 by Clemens and SCBiCG (P, n) algorithm retrospective study found that the algorithm actually contains van Vorst and Der COCG algorithm proposed by Melissen, the COCR algorithm proposed by Clemens and Sogabe and BiCGCR algorithm proposed by Zhang. The SCBiCG algorithm principle describes the system in mathematics, it is proved that the BiCGCR algorithm and the COCR algorithm is mathematically equivalent, but because the latter requires only two inner product and slightly advantage. Finally, through the experiment of discrete linear system solving electromagnetic calculation model of three typical problems, compared to COCG, BiCGCR,.BiCGCR and COCR numerical performance of four kinds of Krylov subspace the algorithms of COCR and SQMR are very similar in the numerical convergence, and convergence behavior of COCG algorithm are more smooth. In addition a two step pretreatment technique for quasi-static magnetic field numerical discrete system numerical. The experiments show that the pretreatment technique is especially suitable for peridynamic modeling the quasi-static magnetic field simulation of.3. in materials science to the commonly used pseudo Integro differential equation, the nonlocal operator, the numerical discretization of the equation of dense linear equations of.Tian and Wang in 2013 found that the discrete linear system with Toeplitz the structure, calculation efficiency and the use of a fast Toeplitz matrix vector multiplication to improve CG algorithm. In order to improve the efficiency of the CG algorithm to deal with the ill conditioned Galerkin discrete system, after mining the coefficient matrix has a Toeplitz structure with symmetric three diagonal part information improves the sub cycle pretreatment classic, and analyzed the characteristics of the preconditioning matrix the value of almost all gathered in the vicinity of 1. Finally, the numerical experiments show the new cycle pretreatment proposed in computational efficiency of CG algorithm is accelerated The effect of.4. BiCRStab algorithm is extended to solve the displacement problem of a linear system proposed by Sogabe and Abe and BiCR algorithm proposed by Sleijpen, and successfully derived two new Krylov subspace algorithm, BiCR algorithm and BiCRStab displacement displacement algorithm. Because these two kinds of algorithm keeps the displacement invariance of the Krylov subspace, resulting in solving linear equations to the displacement matrix vector multiplication number is equivalent to solving a single system when the number of matrix vector multiplication, and the new algorithm greatly reduces the amount of calculation and storage. Numerical experiments show that these two new methods are respectively BiCG and BiCGStab displacement displacement algorithm converges fast, and usually more than after both.5. residual convergence behavior more smooth for the space fractional diffusion equation, the design of a new numerical format. First, the space discretization of the fractional diffusion equation, the The original problem is transformed into solving a system of ordinary differential equations. Finally using unconditionally stable time discretization method of the discrete problem is transformed into a large linear system. Because of its coefficient matrix has Toeplitz structure, Krylov subspace algorithm does not need to store the coefficient matrix to quickly solve the discrete linear system in order to speed up the convergence. The speed of the algorithm, construct block circulant (block circulant, BC) and block cyclic block (block circulan with circulant block, BCCB) two kinds of preconditioners. And through theoretical and numerical experiments of a fast algorithm design can effectively handle the fractional diffusion equation, while avoiding the complex stability analysis of the explicit implicit format of classic faces.

【学位授予单位】：电子科技大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：O441;O241

【参考文献】