新型Krylov子空间算法及其应用研究
发布时间：2018-07-16 20:09
【摘要】：科学与工程应用领域中的许多问题最终归结为大规模稀疏线性方程组数值求解问题。如量子色动力学(QCD)中的格点规范理论,流体力学中的Navier-Stokes方程求解,地震反演模拟过程中的Helmholtz偏微分方程求解等。随着科技的快速发展和应用,人们对上述问题的计算的速度和精度要求变得越来越高。尽管计算机的数值模拟的能力和存储性能在不断的提高,且各种迭代方法不断涌现,但仍没有一种高效且适用于各种形态的线性方程组的求解方法。因此,如何高效省时地求解这类方程组已经成为科学计算中的重要课题之一。本文围绕上述问题进行了研究,主要对两类序列线性系统(带位移线性系统和多右端线性系统)求解展开了讨论。研究内容与主要成果如下:1.基于Frommer于2003年给出了位移BiCGstab算法,提出了位移QMRCGstab方法与位移QMRCGstab2方法。这类方法融合拟最小化残差思想(quasi-minimum residual),改善了位移BiCGstab方法的数值行为,消除了残差收敛行为不规则的现象。同时保持了Krylov子空间位移不变性质,使得算法在求解一系列位移方程组所需的矩阵-向量乘的次数等同于求解单个方程组的次数,从而在一定程度上减少了计算量。数值实验表明,这类方法可有效的平滑残差曲线,保证了数值计算的稳定性。2.基于Ahuja等人于2012年提出的RBiCG算法,将其推广并应用到求解带位移的线性方程组中。然而,不同于传统子空间方法,该算法相应的扩张Krylov子空间(即加入循环不变子空间)不再具有位移不变性质。为此,借助于一种简单技巧来保持这个性质,同时设计了一种短递归位移算法(RBiCG-sh)。特别地,在算法实现上,重新设计了位移方程组的近似解的递归式,避免了额外的矩阵-向量乘积,有利于提高算法的执行速度,从而节省一定的计算量。数值实验表明,RBiCG-sh方法可有效且稳定的求解问题。3.基于Morgan于2005年给出的BGMRES-DR算法,首先提出了一种求解多右端线性系统的灵活变型算法。随后引入修正块Arnoldi列向量收缩技术,使得算法在迭代过程中能够检测并处理几乎线性或线性相关列向量,从而避免了算法执行过程中的中断现象。同时结合该列向量收缩技术,能够在一定程度上减少矩阵-向量乘积次数。另一方面,该方法继承了源算法的特征值收缩特性,在处理具有小特征值的棘手问题上更具有竞争优势。最后数值实验验证了DBFGMRES-DR算法的有效性与数值稳定性。4.针对多右端线性方程组求解问题,将GCROT(m,k)算法加以推广,提出了块状GCROT(m,k)(BGCROT(m,k))方法,并且相应的理论分析表明了BGCROT(m,k)方法产生的残差的F-范数是呈递减趋势的。另一方面,为了提高BGCROT(m,k)算法的求解速度,进一步刻画了灵活的BGCROT(m,k)方法。此外,我们再次引入了修正块Arnoldi收缩技巧以避免BGCROT(m,k)迭代过程中的中断现象,进而保证了算法的可行性与稳健性。数值实验表明与其他现有的块迭代方法相比,BGCROT(m,k)方法及相关的变型算法具有收敛快,稳健性高的竞争优势。
[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.
【学位授予单位】：电子科技大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O177
本文编号：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.
【学位授予单位】：电子科技大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O177
【参考文献】
相关博士学位论文 前1条
1 汪自庆;用格点QCD研究真空的拓扑结构[D];四川大学;2007年
，本文编号：2127538
本文链接：https://www.wllwen.com/kejilunwen/yysx/2127538.html
