【作者】 李良；

【导师】 黄廷祝；

【作者基本信息】 电子科技大学 ， 应用数学， 2009， 博士

【摘要】 计算数学与科学工程计算涉及到航空航天、现代生物与医学、石油勘探、环境科学、隐身器件设计等国民经济与国防建设的各个方面,其中往往需要求解一个或一系列大型线性系统.而且,随着问题规模的增大,相应线性系统的未知数个数大大增加,动辄上百万、千万,甚至上亿.这些大型线性方程组的求解是求解整个问题的基础和关键所在,其计算量也占整个计算过程非常大的比重,有的甚至达到80%以上.超大规模线性系统求解能力的缺乏成为解决某些实际问题的瓶颈.大型线性方程组求解研究是现代科学计算的重要课题和焦点之一,高效、快速的求解方法研究既有理论意义又有实际价值.本文旨在深入研究求解大型线性系统的高性能算法,并特别针对电磁计算中产生的大型线性系统,构造有效的算法.构造对称正定矩阵的不完全分解预条件子.不完全分解预条件迭代法的通常做法是,先对系数矩阵进行重排,再不完全分解,然后再进行预条件迭代求解.本文将近似最小度排序嵌入不完全分解过程,提出了一类新型的高效预条件技术.给出了基于IKJ高斯消元的不完全Cholesky分解,并讨论了一些实现细节,然后分析了精确计算和近似计算分解过程中节点度的方法.结合CG方法,提出的预处理技术能很大地加快迭代法收敛速度.最后用丰富的数值实验表明与最小度排序耦合的不完全分解预条件技术的效率,要高于按照一般做法得到的预条件子的效率.深入研究求解非Hermitian正定线性方程组的Hermitian与Skew-Hermitian分裂(HSS)方法,提出了称为非平衡(lopsided) HSS (LHSS)与非对称(asymmetric) HSS (AHSS)方法.这类方法包含两步迭代,本文从理论上研究了其收敛性以及最优参数的选择问题.在LHSS迭代和AHSS迭代的每一步,都需要求解两个线性方程组.如果用直接法求解这两个方程组,其每个方程组的计算量与求解原方程组相当,那么这里的两步迭代就失去了意义.为了加快两步迭代的收敛速度,在求解这两个方程组时,不准确求出其解,而是用迭代法求其近似解,得到了所谓的ILHSS与IAHSS方法.给出的数值例子验证了本章提出方法的有效性.基于选主元策略研究对称不定矩阵的较为稳定的预条件技术.该类预条件子修正不完全Choleksy(MIC)分解来构造,在分解过程中采用RBBI选主元策略,得到的预条件子一般也具有不定性,期望与原方程组的系数矩阵更相近.通过数值例子表明,作用于SQMR方法时,该类预条件子显示出了很好的效果.针对非对称矩阵,研究基于Givens变换的不完全正交预处理技术.直接将得到的不完全QR分解作为原方程组的预条件子,并通过数值实验验证了提出的预条件方法的高效性.然后着重研究了排序对Givens旋转的QR分解的影响,给出了一种减少QR分解中所作Givens旋转次数的排序算法.针对开域电磁计算问题中出现的大型线性方程组,研究适用有效的预条件子..先讨论用FEM方法求解散射问题时遇到的线性方程组的求解,提出并实现了MIC分解预条件子,然后研究FEM/MoM混合方法求解辐射和散射问题中产生的复杂线性方程组的求解.更多还原

【Abstract】 Computational mathematics and scientific computing are involved in many appli-cations, such as aeromechanics, modern biomedicine, oil reservoir, stealth technology. Usually, we are required to solve one or a series of systems of linear equations. With the increment of the size of the underlying problem, the size of the corresponding linear system increases dramatically. The order of the coefficient matrix often turns out to be millions or even hundreds of millions. The solution to the linear system is the key of the solution to the entire problem. Lack of efficient solutions to large-scale linear systems becomes a bottleneck in solving certain practical problems. Therefore, study of effec-tive solutions to very large linear systems turns out to be one of the focuses in modern scientific computing. This dissertation attempts to develop and construct algorithms of high performance for solutions of linear systems in depth, especially those arising from computational electromagnetics.Effective preconditioners involving incomplete factorization for symmetric positive definite matrices are developed. What we do in the common procedure of the precon-ditioned iterative methods is that we firstly reorder the original coefficient matrix, and then decompose the reordered matrix in an incomplete manner, and finally proceed with the preconditioned iterative methods. We investigate an effective preconditioning tech-nique, which interleaves the incomplete Cholesky (IC) factorization with an approximate minimum degree ordering. An IC factorization algorithm derived from the IKJ-version Gaussian elimination is proposed and some details on its implementation are presented. Then we discuss how to compute the degrees of the unnumbered nodes both exactly and approximately. When used in conjunction with the conjugate gradient algorithm, the new preconditioners usually lead to fast convergence. Numerical experiments show that the preconditioners generated by the interleaving of symbolic ordering and numerical IC fac-torization are better than those generated by the IC factorization without ordering or with purely symbolic ordering ahead of the factorization.A class of lopsided Hermitian/skew-Hermitian (LHSS) methods and a class of asym-metric Hermitian/skew-Hermitian (AHSS) methods to solve non-Hermitian and positive-definite systems of linear equations are established. Convergence properties and optimal parameter selections of these methods are studied. In each iteration of both LHSS and AHSS, two subsystems should be solved. If these subsystems are solved exactly with direct solvers, the HSS iterations are meaningless, because the cost for solving the sub-systems is equal to that for solving the original system by direct solvers. Consequently, we solve them inexactly by iterative solvers and develop ILHSS and IAHSS methods. The presented numerical methods illustrate the effectiveness of the proposed methods.Indefinite preconditioners for solving symmetric indefinite matrices are studied. These preconditioners are developed through a modified incomplete Cholesky (MIC) fac-torization with the pivoting strategy employed in the RBBK algorithm. Both the coef-ficient matrix and the preconditioner are indefinite, so the preconditioned matrix is ex-pected to have more favorable properties for iterative solution. When combined with the SQMR algorithm, this kind of preconditioners works very well according to the presented numerical examples.Preconditioning techniques for solving unsymmetric systems of linear equations are investigated. We study the incomplete orthogonal factorization based on the Givens ro-tations. An FQIGO preconditioning technique is developed, and its efficiency is demon-strated by the presented numerical tests. Then we have an investigation on how the order-ing affects the QR factorization and propose a reordering scheme to reduce the number of Givens rotations in the QR factorization.Finally, we study preconditioning techniques for the solution to the linear systems arising from electromagnetic computation. A kind of MIC preconditioners is proposed to solve the complex symmetric linear systems when FEM is used to handle scattering problems. Then block preconditioners are proposed when hybrid FEM/MoM is employed to deal with electromagnetic radiation and scattering problems.更多还原