新型Krylov子空間算法及其應(yīng)用研究
發(fā)布時(shí)間：2018-07-16 20:09
【摘要】：科學(xué)與工程應(yīng)用領(lǐng)域中的許多問題最終歸結(jié)為大規(guī)模稀疏線性方程組數(shù)值求解問題。如量子色動(dòng)力學(xué)(QCD)中的格點(diǎn)規(guī)范理論,流體力學(xué)中的Navier-Stokes方程求解,地震反演模擬過程中的Helmholtz偏微分方程求解等。隨著科技的快速發(fā)展和應(yīng)用,人們對(duì)上述問題的計(jì)算的速度和精度要求變得越來越高。盡管計(jì)算機(jī)的數(shù)值模擬的能力和存儲(chǔ)性能在不斷的提高,且各種迭代方法不斷涌現(xiàn),但仍沒有一種高效且適用于各種形態(tài)的線性方程組的求解方法。因此,如何高效省時(shí)地求解這類方程組已經(jīng)成為科學(xué)計(jì)算中的重要課題之一。本文圍繞上述問題進(jìn)行了研究,主要對(duì)兩類序列線性系統(tǒng)(帶位移線性系統(tǒng)和多右端線性系統(tǒng))求解展開了討論。研究?jī)?nèi)容與主要成果如下:1.基于Frommer于2003年給出了位移BiCGstab算法,提出了位移QMRCGstab方法與位移QMRCGstab2方法。這類方法融合擬最小化殘差思想(quasi-minimum residual),改善了位移BiCGstab方法的數(shù)值行為,消除了殘差收斂行為不規(guī)則的現(xiàn)象。同時(shí)保持了Krylov子空間位移不變性質(zhì),使得算法在求解一系列位移方程組所需的矩陣-向量乘的次數(shù)等同于求解單個(gè)方程組的次數(shù),從而在一定程度上減少了計(jì)算量。數(shù)值實(shí)驗(yàn)表明,這類方法可有效的平滑殘差曲線,保證了數(shù)值計(jì)算的穩(wěn)定性。2.基于Ahuja等人于2012年提出的RBiCG算法,將其推廣并應(yīng)用到求解帶位移的線性方程組中。然而,不同于傳統(tǒng)子空間方法,該算法相應(yīng)的擴(kuò)張Krylov子空間(即加入循環(huán)不變子空間)不再具有位移不變性質(zhì)。為此,借助于一種簡(jiǎn)單技巧來保持這個(gè)性質(zhì),同時(shí)設(shè)計(jì)了一種短遞歸位移算法(RBiCG-sh)。特別地,在算法實(shí)現(xiàn)上,重新設(shè)計(jì)了位移方程組的近似解的遞歸式,避免了額外的矩陣-向量乘積,有利于提高算法的執(zhí)行速度,從而節(jié)省一定的計(jì)算量。數(shù)值實(shí)驗(yàn)表明,RBiCG-sh方法可有效且穩(wěn)定的求解問題。3.基于Morgan于2005年給出的BGMRES-DR算法,首先提出了一種求解多右端線性系統(tǒng)的靈活變型算法。隨后引入修正塊Arnoldi列向量收縮技術(shù),使得算法在迭代過程中能夠檢測(cè)并處理幾乎線性或線性相關(guān)列向量,從而避免了算法執(zhí)行過程中的中斷現(xiàn)象。同時(shí)結(jié)合該列向量收縮技術(shù),能夠在一定程度上減少矩陣-向量乘積次數(shù)。另一方面,該方法繼承了源算法的特征值收縮特性,在處理具有小特征值的棘手問題上更具有競(jìng)爭(zhēng)優(yōu)勢(shì)。最后數(shù)值實(shí)驗(yàn)驗(yàn)證了DBFGMRES-DR算法的有效性與數(shù)值穩(wěn)定性。4.針對(duì)多右端線性方程組求解問題,將GCROT(m,k)算法加以推廣,提出了塊狀GCROT(m,k)(BGCROT(m,k))方法,并且相應(yīng)的理論分析表明了BGCROT(m,k)方法產(chǎn)生的殘差的F-范數(shù)是呈遞減趨勢(shì)的。另一方面,為了提高BGCROT(m,k)算法的求解速度,進(jìn)一步刻畫了靈活的BGCROT(m,k)方法。此外,我們?cè)俅我肓诵拚龎KArnoldi收縮技巧以避免BGCROT(m,k)迭代過程中的中斷現(xiàn)象,進(jìn)而保證了算法的可行性與穩(wěn)健性。數(shù)值實(shí)驗(yàn)表明與其他現(xiàn)有的塊迭代方法相比,BGCROT(m,k)方法及相關(guān)的變型算法具有收斂快,穩(wěn)健性高的競(jìng)爭(zhēng)優(yōu)勢(shì)。
[Abstract]:Many problems in the field of science and engineering application are finally attributed to the numerical solution of large-scale sparse linear equations, such as the lattice gauge theory in quantum chromdynamics (QCD), the solution of Navier-Stokes equations in fluid mechanics, the solution of Helmholtz partial differential equations in the process of seismic inversion simulation, and so on. In application, the speed and precision of the calculation of the above problems are becoming higher and higher. Although the ability and storage performance of the computer simulation are constantly improved, and the various iterative methods are constantly emerging, there is still no efficient and suitable solution to the linear square group of various forms. Therefore, how to save time efficiently and efficiently Solving these equations has become one of the most important topics in scientific computing. This paper studies the above problems and discusses the solution of two classes of linear systems (linear systems with displacement and multiple right linear systems). The contents and main achievements are as follows: 1. based on Frommer in 2003, the displacement BiCGstab calculation is given. In this method, the displacement QMRCGstab method and the displacement QMRCGstab2 method are proposed. This method converges the quasi minimization residual thought (quasi-minimum residual), improves the numerical behavior of the displacement BiCGstab method and eliminates the irregular convergence behavior of the residual error. At the same time, it keeps the constant properties of the Krylov subspace displacement, making the algorithm in a series of solutions. The number of matrix vector multiplication required by the displacement equations is equal to the number of times for solving a single equation group, thus reducing the amount of calculation to a certain extent. The numerical experiment shows that this method can effectively smooth the residual curve and guarantee the stability of the numerical calculation based on the RBiCG algorithm proposed by Ahuja et al. In 2012, which is popularized and applied. To solve linear equations with displacement, however, different from the traditional subspace method, the corresponding extended Krylov subspace (that is, adding cyclic invariant subspace) no longer has the property of displacement. To this end, a simple technique is used to maintain this property, and a short recursive translation algorithm (RBiCG-sh) is designed, especially, In the realization of the algorithm, the recursive formula of the approximate solution of the displacement equations is redesigned, which avoids the additional matrix vector product. It is beneficial to improve the execution speed of the algorithm and thus save a certain amount of calculation. The numerical experiment shows that the RBiCG-sh method can effectively and stably solve the problem.3. based on the BGMRES-DR algorithm given by Morgan in 2005. First, a flexible variant algorithm for solving multiple right linear systems is proposed. Then the modified block Arnoldi column vector contraction technique is introduced, which enables the algorithm to detect and process almost linear or linear correlation column vectors during the iterative process, thus avoiding the interruption in the execution of the algorithm. On the other hand, the method inherits the eigenvalue contraction characteristics of the source algorithm, and has more competitive advantage on dealing with the difficult problems with small eigenvalues. Finally, the numerical experiments verify the validity and numerical stability of the DBFGMRES-DR algorithm for the solution of the multiple right linear equations. The GCROT (m, K) algorithm is generalized and the block GCROT (m, K) (BGCROT (m, K)) method is proposed, and the corresponding theoretical analysis shows that the residual norm of the residual error generated by BGCROT (m, K) method is subtraction. On the other hand, to improve the speed of the algorithm, the flexible method is also depicted. In addition, I We re introduced the modified block Arnoldi contraction technique to avoid the interruption in the BGCROT (m, K) iterative process, thus ensuring the feasibility and robustness of the algorithm. The numerical experiments show that compared with other existing block iterative methods, the BGCROT (m, K) method and the related variant algorithms have the competitive advantage of fast convergence and high robustness.
【學(xué)位授予單位】：電子科技大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2015
【分類號(hào)】：O177
本文編號(hào)：2127538
[Abstract]:Many problems in the field of science and engineering application are finally attributed to the numerical solution of large-scale sparse linear equations, such as the lattice gauge theory in quantum chromdynamics (QCD), the solution of Navier-Stokes equations in fluid mechanics, the solution of Helmholtz partial differential equations in the process of seismic inversion simulation, and so on. In application, the speed and precision of the calculation of the above problems are becoming higher and higher. Although the ability and storage performance of the computer simulation are constantly improved, and the various iterative methods are constantly emerging, there is still no efficient and suitable solution to the linear square group of various forms. Therefore, how to save time efficiently and efficiently Solving these equations has become one of the most important topics in scientific computing. This paper studies the above problems and discusses the solution of two classes of linear systems (linear systems with displacement and multiple right linear systems). The contents and main achievements are as follows: 1. based on Frommer in 2003, the displacement BiCGstab calculation is given. In this method, the displacement QMRCGstab method and the displacement QMRCGstab2 method are proposed. This method converges the quasi minimization residual thought (quasi-minimum residual), improves the numerical behavior of the displacement BiCGstab method and eliminates the irregular convergence behavior of the residual error. At the same time, it keeps the constant properties of the Krylov subspace displacement, making the algorithm in a series of solutions. The number of matrix vector multiplication required by the displacement equations is equal to the number of times for solving a single equation group, thus reducing the amount of calculation to a certain extent. The numerical experiment shows that this method can effectively smooth the residual curve and guarantee the stability of the numerical calculation based on the RBiCG algorithm proposed by Ahuja et al. In 2012, which is popularized and applied. To solve linear equations with displacement, however, different from the traditional subspace method, the corresponding extended Krylov subspace (that is, adding cyclic invariant subspace) no longer has the property of displacement. To this end, a simple technique is used to maintain this property, and a short recursive translation algorithm (RBiCG-sh) is designed, especially, In the realization of the algorithm, the recursive formula of the approximate solution of the displacement equations is redesigned, which avoids the additional matrix vector product. It is beneficial to improve the execution speed of the algorithm and thus save a certain amount of calculation. The numerical experiment shows that the RBiCG-sh method can effectively and stably solve the problem.3. based on the BGMRES-DR algorithm given by Morgan in 2005. First, a flexible variant algorithm for solving multiple right linear systems is proposed. Then the modified block Arnoldi column vector contraction technique is introduced, which enables the algorithm to detect and process almost linear or linear correlation column vectors during the iterative process, thus avoiding the interruption in the execution of the algorithm. On the other hand, the method inherits the eigenvalue contraction characteristics of the source algorithm, and has more competitive advantage on dealing with the difficult problems with small eigenvalues. Finally, the numerical experiments verify the validity and numerical stability of the DBFGMRES-DR algorithm for the solution of the multiple right linear equations. The GCROT (m, K) algorithm is generalized and the block GCROT (m, K) (BGCROT (m, K)) method is proposed, and the corresponding theoretical analysis shows that the residual norm of the residual error generated by BGCROT (m, K) method is subtraction. On the other hand, to improve the speed of the algorithm, the flexible method is also depicted. In addition, I We re introduced the modified block Arnoldi contraction technique to avoid the interruption in the BGCROT (m, K) iterative process, thus ensuring the feasibility and robustness of the algorithm. The numerical experiments show that compared with other existing block iterative methods, the BGCROT (m, K) method and the related variant algorithms have the competitive advantage of fast convergence and high robustness.
【學(xué)位授予單位】：電子科技大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2015
【分類號(hào)】：O177
【參考文獻(xiàn)】
相關(guān)博士學(xué)位論文 前1條
1 汪自慶;用格點(diǎn)QCD研究真空的拓?fù)浣Y(jié)構(gòu)[D];四川大學(xué);2007年
，本文編號(hào)：2127538
本文鏈接：http://www.sikaile.net/kejilunwen/yysx/2127538.html
最近更新
教材專著
