对称逐步超松弛预处理共轭梯度法的改进迭代格式

51．引言线性方程组的求解方法可分为两大类：直接法和迭代法．对于大型问题，当系数矩阵为条件数较小的稀疏矩阵且右端项不多时，迭代法的求解效率高．尽管迭代法多种多样，但其迭代收敛速度毫不例外地取决于迭代矩阵的条件数，而预处理的唯一目的就是降低迭代矩阵的条件数，从而达到减少迭代次数和计算量的目的．共轭梯度法（CG法）具有许多内在的优点，如有限步收敛性质．在实际计算中，由于舍入误差的影响，特别是由于系数矩阵的条件数常常较大，CG法往往出现收敛慢的问题．预处理共轭梯度法（PCG法）就是在共轭梯度法中采用了预处理…     

基于雅可比矩阵逆预处理的快速潮流计算方法

随着电网规模变大，利用稳定双共轭梯度法（Bi-CGSTAB）求解潮流计算中的修正方程组时，收敛速度会变得很慢。通过寻找合适的预处理矩阵是解决问题的关键。研究了雅可比矩阵预处理方法，针对牛顿法求解潮流过程中雅可比矩阵的变化特性，提出将第一次外迭代的雅可比矩阵逆作为预处理矩阵，并与稳定双共轭梯度法相结合，提高潮流计算的收敛速度。借助InterPSS电力系统仿真软件，对IEEE118、IEEE162、IEEE300和一个欧洲大陆真实电力系统进行仿真计算，验证了在处理大规模电网时，所提方法相对稀疏近似逆预处理具备更好的有效性。     

基于分块存储格式的稀疏线性系统求解优化

针对基于GPU求解大规模稀疏线性方程组进行了研究,提出一种稀疏矩阵的分块存储格式HMEC（hybrid multiple ELL and CSR）。通过重排序优化系数矩阵的存储结构,将系数矩阵以一定的比例分块存储,采用ELL与CSR存储格式相结合的方式以适应不同的分块特征,分别使用适用于不对称矩阵的不完全LU分解预处理BICGStab法和对称正定矩阵的不完全Cholesky分解预处理共轭梯度法求解大规模稀疏线性系统。实验表明,应用HMEC格式存储稀疏矩阵并以调用GPU kernel的方式实现前述两种方法,与其他存储格式的实现方式作比较,最优可分别获得31.89%和17.50%的加速效果。     

基于GPU-CUDA的共轭斜量法实现及性能对比

偏微分方程数值解法(包括有限差分法、有限元法)以及大量的数学物理方程数值解法最终都会演变成求解大型线性方程组。因此,探讨快速、稳定、精确的大型线性方程组解法一直是数值计算领域不断深入研究的课题且具有特别重要的意义。在迭代法中,共轭斜量法(又称共轭梯度法)被公认为最好的方法之一。但是,该方法最大缺点是仅适用于线性方程组系数矩阵为对称正定矩阵的情况,而且常规的CPU算法实现非常耗时。为此,通过将线性方程组系数矩阵作转换成对称矩阵后实施基于GPU-CUDA的快速共轭斜量法来解决一般性大型线性方程组的求解问题。试验结果表明:在求解效率方面,基于GPU-CUDA的共轭斜量法运行效率高,当线性方程组阶数超过3000时,其加速比将超过14;在解的精确性与求解过程的稳定性方面,与高斯列主元消去法相当。基于GPU-CUDA的快速共轭斜量法是求解一般性大型线性方程组快速而非常有效的方法。     

基于工作站机群并行求解有限元线性方程组

随着计算机高速网络技术的发展,工作站机群正在成为并行计算的主要平台.有限元线性方程组在土木工程结构分析中是最常见的问题.预处理共轭梯度法(PCGM)是求解线性方程组的迭代方法.对预处理共轭梯度法进行并行化并在两个不同的机群上实现,对存储方式进行详细分析,编程中采用了稀疏矩阵向量相乘的优化技术.数值结果表明,设计的并行算法具有良好的加速比和并行效率,说明并行计算能更快地求解大规模问题.     

预处理技术在求解高度亏损系数矩阵的线性方程组中的应用

本文主要讨论的是预处理技术在求解具有高度亏损系数矩阵相应特征值按模小于1的线性方程组的应用。我们采取了一种预处理技术。研究怎样选择预处理子P，来改善重新开始方法的迭代过程。在求解线性方程组Ax=b时。对于高度亏损的系数矩阵A，我们应用预处理子A^r。然而,却导致谱半径变大。使得残量的收敛速度变慢。为此，预处理过程通过不完全LQ分解预处理技术来扩展Krylov子空间。预处理后的方程组由A^T Ax=A^T b变成L^-1A^TL^-Ty=L^-1A^T6．然后再使用GMRES方法和FOM方法。     

一种基于共轭梯度的LMBP改进学习算法

对神经网络中的LMBP（Levenberg-Marquardt BP）算法的收敛速度慢进行分析,针对矩阵J^TJ+µI求逆过程运算量过大而造成收敛速度慢的缺陷,根据无约束优化理论,提出一种基于共轭梯度方法的改进LMBP网络学习算法,利用求解大规模线性方程组的共轭梯度方法,避免了烦琐的求逆过程,降低了计算复杂度,加快了网络的收敛速度,通过Matlab仿真,比较了算法的收敛速度,证明了方法的有效性。     

求实对称矩阵部分特征值的并行算法

提出了并行求解实对称稠密矩阵部分特征值的反幂法的预处理方法.该方法基于带状矩阵特征问题反幂法的信息传递复杂度低的特点,采用Householder变换并行算法约化大型实对称稠密矩阵为一定带宽的带状矩阵,针对带状矩阵用反幂法求解矩阵的在某一点的近似特征值;其中针对反幂法迭代中遇到的线性方程组,采用文献中的并行预处理共轭梯度算法求解.最后在Lenovo深腾1800集群上进行数值实验,并与预处理前反幂法的计算结果进行了比较,实验结果表明,经过预处理后的并行性远高于直接采用反幂法的并行性.     

不完全乔莱斯基分解预优共轭梯度的模型

在超分辨率影像重建中，基于最大后验估计(MAP)框架的重建方法具有较大的优势，应用非常广泛。然而，常用的迭代求解方法如最速下降法、共轭梯度法等收敛速度慢、处理时间长，经常难以满足实际处理的需要。该文在MAP框架的基础上，提出了基于不完全乔莱斯基分解预优共轭梯度的模型求解方法，即在迭代求解过程中利用不完全乔莱斯基分解构造预优矩阵，降低系数矩阵的条件数，从而提高收敛速度，节省处理时间。实验结果证明，该方法是有效的、可行的。     

基于OpenMP的共轭梯度法并行加速

共轭梯度法是为求解线性方程组而独立提出的一种常用的数值计算方法,被广泛地应用于天气动力、物理海洋等数值计算中,其复杂的矩阵计算产生巨大工作量,成为业务化应用过程中的计算瓶颈。利用OpenMP共享并行技术,将大量计算并行化,实现基于OpenMP的共轭梯度法并行加速,为共轭梯度法的广泛应用提供了新的计算解决方案。     

一种LU分解与迭代法的结合策略及算法实现

在矩阵求解算法中，直接法或迭代法都不能有效地求解大规模稀疏或病态矩阵,因此提出一种LU分解与迭代法结合的策略。采用LU分解对矩阵进行预处理，以提高迭代法的收敛性,并采用一种判断策略使矩阵的LU分解结果可最大限度地重复利用。此结合策略应用于两种共轭梯度（CG）法，得到CLUCG和CLUTCG两种算法。它们已应用于模拟和混合信号电路模拟器ZeniVDE中。大量实验结果表明此结合策略是很有效的，得到的两种算法具有较快的速度和较好的收敛性。     

层流扩散燃烧在GPU上的并行计算和数值分析

在实际工程应用中,使用传统的CPU串行计算来开展燃烧数值模拟往往难以满足对模拟速度的要求。利用GPU比CPU更强的计算能力,通过在交错网格上将燃烧物理方程离散化,使用预处理稳定双共轭梯度法(PBiCGSTAB)求解离散化方程,并且探索面向GPU编程的矩阵向量乘并行算法和逆矩阵向量乘并行算法,从而给出一种在GPU上数值求解层流扩散燃烧的可行方法。实验结果表明,GPU并行程序获得了相对串行CPU程序约10倍以上的加速效果,且计算结果与实际情况相符,因而所提方法是可行且高效的。     

Preconditioned variational methods on rotated finite difference discretisation

Due to their rapid convergence properties, recent focus on iterative methods in the solution of linear system has seen a flourish on the use of gradient techniques which are primarily based on global minimisation of the residual vectors. In this paper, we conduct an experimental study to investigate the performance of several preconditioned gradient or variational techniques to solve a system arising from the so-called rotated (skewed) finite difference discretisation in the solution of elliptic partial differential equations (PDEs). The preconditioned iterative methods consist of variational accelerators, namely the steepest descent and conjugate gradient methods, applied to a special matrix ‘splitting’ preconditioned system. Several numerical results are presented and discussed.     

Normalized explicit finite element approximate inverse preconditioning

Normalized explicit approximate inverse matrix techniques for computing explicitly various families of normalized approximate inverses based on normalized approximate factorization procedures for solving sparse linear systems, which are derived from the finite difference and finite element discretization of partial differential equations are presented. Normalized explicit preconditioned conjugate gradient-type schemes in conjunction with normalized approximate inverse matrix techniques are presented for the efficient solution of linear and non-linear systems. Theoretical estimates on the rate of convergence and computational complexity of the normalized explicit preconditioned conjugate gradient method are also presented. Applications of the proposed methods on characteristic linear and non-linear problems are discussed and numerical results are given.     

Parallel and Systolic Solution of Normalized Explicit Approximate Inverse Preconditioning

A new class of normalized approximate inverse matrix techniques, based on the concept of sparse normalized approximate factorization procedures are introduced for solving sparse linear systems derived from the finite difference discretization of partial differential equations. Normalized explicit preconditioned conjugate gradient type methods in conjunction with normalized approximate inverse matrix techniques are presented for the efficient solution of sparse linear systems. Theoretical results on the rate of convergence of the normalized explicit preconditioned conjugate gradient scheme and estimates of the required computational work are presented. Application of the new proposed methods on two dimensional initial/boundary value problems is discussed and numerical results are given. The parallel and systolic implementation of the dominant computational part is also investigated.     

Convergence and instability in PCG methods for bordered systems

Bordered almost block diagonal systems arise from discretizing a linearized first-order system of n ordinary differential equations in a two-point boundary value problem with nonseparated boundary conditions. The discretization may use spline collocation, finite differences, or multiple shooting. After internal condensation, if necessary, the bordered almost block diagonal system reduces to a standard finite difference structure, which can be solved using a preconditioned conjugate gradient method based on a simple matrix splitting technique. This preconditioned conjugate gradient method is “guaranteed” to converge in at most 2n + 1 iterations. We exhibit a significant collection of two-point boundary value problems for which this preconditioned conjugate gradient method is unstable, and hence, convergence is not achieved.     

Explicit approximate inverse preconditioning techniques

Summary  The numerical treatment and the production of related software for solving large sparse linear systems of algebraic equations, derived mainly from the discretization of partial differential equation, by preconditioning techniques has attracted the attention of many researchers. In this paper we give an overview of explicit approximate inverse matrix techniques for computing explicitly various families of approximate inverses based on Choleski and LU—type approximate factorization procedures for solving sparse linear systems, which are derived from the finite difference, finite element and the domain decomposition discretization of elliptic and parabolic partial differential equations. Composite iterative schemes, using inner-outer schemes in conjunction with Picard and Newton method, based on approximate inverse matrix techniques for solving non-linear boundary value problems, are presented. Additionally, isomorphic iterative methods are introduced for the efficient solution of non-linear systems. Explicit preconditioned conjugate gradient—type schemes in conjunction with approximate inverse matrix techniques are presented for the efficient solution of linear and non-linear system of algebraic equations. Theoretical estimates on the rate of convergence and computational complexity of the explicit preconditioned conjugate gradient method are also presented. Applications of the proposed methods on characteristic linear and non-linear problems are discussed and numerical results are given.     

Overlapping Schwarz and Spectral Element Methods for Linear Elasticity and Elastic Waves

The classical overlapping Schwarz algorithm is here extended to the spectral element discretization of linear elastic problems, for both homogeneous and heterogeneous compressible materials. The algorithm solves iteratively the resulting preconditioned system of linear equations by the conjugate gradient or GMRES methods. The overlapping Schwarz preconditioned technique is then applied to the numerical approximation of elastic waves with spectral elements methods in space and implicit Newmark time advancing schemes. The results of several numerical experiments, for both elastostatic and elastodynamic problems, show that the convergence rate of the proposed preconditioning algorithm is independent of the number of spectral elements (scalability), is independent of the spectral degree in case of generous overlap, otherwise it depends inversely on the overlap size. Some results on the convergence properties of the spectral element approximation combined with Newmark schemes for elastic waves are also presented.