本文選題：Krylov子空間方法　切入點(diǎn)：線性方程組　出處：《電子科技大學(xué)》2017年博士論文

【摘要】：科學(xué)計算中的大量問題都與如何高效地求解大型線性系統(tǒng)有關(guān)。如電磁散(輻)射數(shù)值仿真,材料力學(xué)中的近場動力學(xué)特征建模,模擬物質(zhì)的反常(對流)擴(kuò)散過程中的分?jǐn)?shù)階微分方程求解等。因此,線性方程組的高性能算法研究也成為科學(xué)計算中活躍的分支之一。通常情況下,許多工程仿真所涉及的線性方程組的系數(shù)矩陣都是具有某些特定的結(jié)構(gòu),如何科學(xué)合理地挖掘和利用這些結(jié)構(gòu)性質(zhì)來構(gòu)造快速穩(wěn)健的線性系統(tǒng)解法是一個重要的課題。本文針對幾類具有特殊結(jié)構(gòu)的大型線性方程組的高性能解法進(jìn)行了系統(tǒng)的研究,特別是研究了復(fù)對稱線性系統(tǒng)的Krylov子空間算法、求解具有Toeplitz矩陣結(jié)構(gòu)的線性系統(tǒng)的預(yù)處理迭代法以及求解位移線性方程組的迭代法。研究內(nèi)容與主要成果可以歸納如下:1.針對求解大型復(fù)對稱線性系統(tǒng)問題,兩種流行的Krylov子空間算法(即COCG和COCR)都是基于斜投影的原理創(chuàng)建的,在實(shí)際計算中常常出現(xiàn)不規(guī)則的收斂行為,甚至發(fā)生停滯或中斷。為了改善這一數(shù)值不足,推導(dǎo)出兩類新的Krylov子空算法,即QMRCOCG算法和QMRCOCR算法,改善了COCG算法和COCR算法法的數(shù)值行為,消除了殘差收斂行為不規(guī)則的現(xiàn)象。最后,將新導(dǎo)出的兩類算法應(yīng)用于三組典型的電磁仿真模型問題的求解中,數(shù)值實(shí)驗(yàn)表明,這兩種新方法可有效的平滑殘差曲線,保證了數(shù)值計算的穩(wěn)健性。2.對Clemens等在1996年提出的SCBiCG(Γ,n)算法的回溯研究發(fā)現(xiàn),該算法實(shí)際上包含了van der Vorst和Melissen提出的COCG算法,Clemens等提出的BiCGCR算法以及Sogabe和Zhang提出的COCR算法。將SCBiCG類算法的原理等做了系統(tǒng)的數(shù)學(xué)闡述,證明了BiCGCR算法和COCR算法是數(shù)學(xué)上等價的,但由于后者只需要兩次內(nèi)積運(yùn)算而略具優(yōu)勢。最后,通過求解三組典型的電磁計算模型問題產(chǎn)生的離散線性系統(tǒng)實(shí)驗(yàn),對比了COCG,BiCGCR,COCR和SQMR四種Krylov子空間算法的數(shù)值表現(xiàn)。BiCGCR和COCR在數(shù)值收斂行為也非常相似,且比COCG算法的收斂行為要更平滑。此外針對準(zhǔn)靜磁場數(shù)值離散系統(tǒng)建立了一種兩步預(yù)處理技術(shù)。數(shù)值實(shí)驗(yàn)證實(shí)了該預(yù)處理技術(shù)特別適合處理上述準(zhǔn)靜磁場仿真問題。3.材料科學(xué)中的近場動力學(xué)建模中常用到偽積微分方程,由于算子的非局部性,使得該類方程的數(shù)值離散產(chǎn)生稠密線性方程組。Tian和Wang于2013年發(fā)現(xiàn)了該離散線性系統(tǒng)具有Toeplitz結(jié)構(gòu),并利用了快速Toeplitz矩陣-向量乘法來提升CG算法的計算效率。為了提高CG算法處理該病態(tài)Galerkin離散系統(tǒng)的效率,本文挖掘了系數(shù)矩陣具有Toeplitz結(jié)構(gòu)加對稱三對角部分的信息之后改進(jìn)了經(jīng)典的循環(huán)預(yù)處理子,并分析了預(yù)處理矩陣的特征值幾乎都聚集在1附近。最后,數(shù)值實(shí)驗(yàn)說明了所提出的新循環(huán)預(yù)處理子在加速CG算法的計算效率上是有效的。4.將Sogabe提出的BiCR算法和Abe及Sleijpen提出的BiCRStab算法推廣到求解位移線性系統(tǒng)問題,并成功導(dǎo)出了兩種新的Krylov子空間算法,即位移BiCR算法和位移BiCRStab算法。因?yàn)檫@兩種算法法保持了Krylov子空間的位移不變性,從而在求解位移線性方程組時需要的矩陣-向量乘法個數(shù)等價于求解單個系統(tǒng)時的矩陣-向量乘法次數(shù),而且新算法大大減少了計算量和存儲量。數(shù)值實(shí)驗(yàn)表明,這兩個新方法都分別比位移BiCG和位移BiCGStab算法收斂的快,而且通常比后兩者具有更光滑的殘差收斂行為。5.針對空間分?jǐn)?shù)階擴(kuò)散方程,設(shè)計了一種新的數(shù)值求解格式。首先對分?jǐn)?shù)階擴(kuò)散方程做空間半離散,將原問題轉(zhuǎn)化為求解一個常微分方程組。最后利用無條件穩(wěn)定的時間離散方法將離散問題轉(zhuǎn)化為一個大型結(jié)構(gòu)線性系統(tǒng)。因其系數(shù)矩陣具有Toeplitz結(jié)構(gòu),則Krylov子空間算法并不需要存儲系數(shù)矩陣來快速地求解該離散線性系統(tǒng)。為了加快算法的收斂速度,構(gòu)造了塊循環(huán)(block circulant,BC)及帶循環(huán)塊的塊循環(huán)(block circulan with circulant block,BCCB)兩種預(yù)處理子。并通過理論和數(shù)值實(shí)驗(yàn)分析了所設(shè)計的快速算法能比較有效地處理分?jǐn)?shù)階擴(kuò)散方程,同時避免經(jīng)典的顯隱式格式所面臨的復(fù)雜穩(wěn)定性分析等問題。
[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.

【學(xué)位授予單位】：電子科技大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2017
【分類號】：O441;O241

【參考文獻(xiàn)】

相關(guān)博士學(xué)位論文 前1條

1 孟靜;新型Krylov子空間算法及其應(yīng)用研究[D];電子科技大學(xué);2015年

，

本文編號：1689642