基于解空间分解的GMRES算法及其在图像处理中的应用

提出一种基于解空间分解的加速GMRES算法来求解不适定问题,该算法将解空间分解为Krylov子空间和一个辅助子空间,其中一部分解用一种加速GMRES法迭代得到,另一部分解用直接求解的方法得到。数值实验和分析表明这种算法是行之有效的,在达到相同的估计精度的条件下,迭代速度大大提高,求解时间只有普通GMRES算法的五分之一,甚至更少;而且在迭代次数相同的情况下,解的精度更高,如解的均方误差平均是普通GMRES算法的五分之三。最后将该方法应用到光学图像复原,实验结果表明该方法能够明显改善光学图像的质量。     

Convergence analysis of modified PGSS methods for singular saddle-point problems

Recently, variants of shift-splitting iteration method have been proposed for solving singular saddle-point problems. However, these methods can only be proved to converge to one of the solutions of the consistent singular linear system, not knowing any further information about this solution. In this work, we consider a modified preconditioned generalized shift-splitting (MPGSS) iteration method for solving both consistent and inconsistent singular saddle-point problems. This method is proved to converge to the best least squares solution. Moreover, based on the iteration form, a preconditioner is obtained to accelerate Krylov subspace methods. Theoretical analysis shows that the preconditioned GMRES method also converges to the best least squares solution of the consistent singular saddle-point problem. In addition, numerical results are presented to show the effectiveness and robustness of the proposed iteration method and preconditioner.     

Block preconditioners for elliptic PDE-constrained optimization problems

For the structured systems of linear equations arising from the Galerkin finite-element discretizations of the distributed control problems, we construct block-counter-diagonal and block-counter-tridiagonal preconditioning matrices to precondition the Krylov subspace methods such as GMRES. We derive explicit expressions for the eigenvalues and eigenvectors of the corresponding preconditioned matrices. Numerical implementations show that these structured preconditioners may lead to satisfactory experimental results of the preconditioned GMRES methods when the regularization parameter is suitably small.     

Preconditioned Krylov subspace methods for solving radiative transfer problems with scattering and reflection

Two Krylov subspace methods, the GMRES and the BiCGSTAB, are analyzed for solving the linear systems arising from the mixed finite element discretization of the discrete ordinates radiative transfer equation. To increase their convergence rate and stability, the Jacobi and block Jacobi methods are used as preconditioners for both Krylov subspace methods. Numerical experiments, designed to test the effectiveness of the (preconditioned) GMRES and the BiCGSTAB, are performed on various radiative transfer problems: (i) transparent, (ii) absorption dominant, (iii) scattering dominant, and (iv) with specular reflection. It is observed that the BiCGSTAB is superior to the GMRES, with lower iteration counts, solving times, and memory consumption. In particular, the BiCGSTAB preconditioned by the block Jacobi method performed best amongst the set of other solvers. To better understand the discrete systems for radiative problems (i) to (iv), an eigenvalue spectrum analysis has also been performed. It revealed that the linear system conditioning deteriorates for scattering media problems in comparison to absorbing or transparent media problems. This conditioning further deteriorates when reflection is involved.     

Efficient nonlinear solvers for Laplace–Beltrami smoothing of three-dimensional unstructured grids

The Laplace–Beltrami system of nonlinear, elliptic, partial differential equations has utility in the generation of computational grids on complex and highly curved geometry. Discretization of this system using the finite-element method accommodates unstructured grids, but generates a large, sparse, ill-conditioned system of nonlinear discrete equations. The use of the Laplace–Beltrami approach, particularly in large-scale applications, has been limited by the scalability and efficiency of solvers. This paper addresses this limitation by developing two nonlinear solvers based on the Jacobian-Free Newton–Krylov (JFNK) methodology. A key feature of these methods is that the Jacobian is not formed explicitly for use by the underlying linear solver. Iterative linear solvers such as the Generalized Minimal RESidual (GMRES) method do not technically require the stand-alone Jacobian; instead its action on a vector is approximated through two nonlinear function evaluations. The preconditioning required by GMRES is also discussed. Two different preconditioners are developed, both of which employ existing Algebraic Multigrid (AMG) methods. Further, the most efficient preconditioner, overall, for the problems considered is based on a Picard linearization. Numerical examples demonstrate that these solvers are significantly faster than a standard Newton–Krylov approach; a speedup factor of approximately 26 was obtained for the Picard preconditioner on the largest grids studied here. In addition, these JFNK solvers exhibit good algorithmic scaling with increasing grid size.     

二维三温能量方程组的预条件迭代软件包研制——离散所得稀疏线性方程组的求解

首先针对二维三温能量方程组,系统分析了求解所得到的稀疏线性方程组时,采用多种传统预条件技术时将遇到的问题,并提出了相应的适应性改进。其次,在集成这些预条件,以及新提出的MRILUT预条件的基础上,基于Fortran语言研制了一个性能高、可读性强、可扩展性好的预条件Krylov子空间迭代法软件包PreIT2D3T。最后,对2个实际惯性约束聚变问题的全程数值模拟进行了实验,实验结果表明MRILUT优于ILUT,同时PreIT2D3T的性能也优于SPARSKIT软件包。     

二维三温能量方程组的预条件迭代软件包研制 ——离散所得稀疏线性方程组的求解

首先针对二维三温能量方程组,系统分析了求解所得到的稀疏线性方程组时,采用多种传统预条件技术时将遇到的问题,并提出了相应的适应性改进。其次,在集成这些预条件,以及新提出的MRILUT预条件的基础上,基于Fortran语言研制了一个性能高、可读性强、可扩展性好的预条件Krylov子空间迭代法软件包PreIT2D3T。最后,对2个实际惯性约束聚变问题的全程数值模拟进行了实验,实验结果表明MRILUT优于ILUT,同时PreIT2D3T的性能也优于SPARSKIT软件包。     

一种GMRES与GMERR的混和算法

近年来Krylov子空间类算法得到了很大的发展，其中GMRES算法已成为求解大型稀疏非对称线性系统的一种成熟并且很有效的解法，但该算法有时会出现停滞，并且它是以残量来判断收敛，并不能很好地衡量近似解的精确程度，而GMERR算法是最近几年出现的另一种Krylov子空间类算法，它和GMRES算法相比是各有千秋，文章结合两种算法的优点，提出了一种组合算法，它对求解大型稀疏非对称线性系统相当有效。     

Some preconditioners for elliptic PDE-constrained optimization problems

For the structured systems of linear equations arising from the Galerkin finite element discretizations of elliptic PDE-constrained optimization problems, some preconditioners are proposed to accelerate the convergence rate of Krylov subspace methods such as GMRES for both cases of the Tikhonov parameter $\beta$ not very small (equal or greater than 1e?6) and sufficiently small (less than 1e?6), respectively. We derive the explicit expressions for the eigenvalues and eigenvectors of the corresponding preconditioned matrices. Numerical results show that the corresponding preconditioned GMRES methods perform and match well with the theoretical results.     

The Influence of Interface Conditions on Convergence of Krylov-Schwarz Domain Decomposition for the Advection-Diffusion Equation

Several variants of Schwarz domain decomposition, which differ in the choice of interface conditions, are studied in a finite volume context. Krylov subspace acceleration, GMRES in this paper, is used to accelerate convergence. Using a detailed investigation of the systems involved, we can minimize the memory requirements of GMRES acceleration. It is shown how Krylov subspace acceleration can be easily built on top of an already implemented Schwarz domain decomposition iteration, which makes Krylov-Schwarz algorithms easy to use in practice. The convergence rate is investigated both theoretically and experimentally. It is observed that the Krylov subspace accelerated algorithm is quite insensitive to the type of interface conditions employed.     

A Matrix-free Two-grid Preconditioner for Solving Boundary Integral Equations in Electromagnetism

In this paper, we describe a matrix-free iterative algorithm based on the GMRES method for solving electromagnetic scattering problems expressed in an integral formulation. Integral methods are an interesting alternative to differential equation solvers for this problem class since they do not require absorbing boundary conditions and they mesh only the surface of the radiating object giving rise to dense and smaller linear systems of equations. However, in realistic applications the discretized systems can be very large and for some integral formulations, like the popular Electric Field Integral Equation, they become ill-conditioned when the frequency increases. This means that iterative Krylov solvers have to be combined with fast methods for the matrix-vector products and robust preconditioning to be affordable in terms of CPU time. In this work we describe a matrix-free two-grid preconditioner for the GMRES solver combined with the Fast Multipole Method. The preconditioner is an algebraic two-grid cycle built on top of a sparse approximate inverse that is used as smoother, while the grid transfer operators are defined using spectral information of the preconditioned matrix. Experiments on a set of linear systems arising from real radar cross section calculation in industry illustrate the potential of the proposed approach for solving large-scale problems in electromagnetism.     

Determination of a good value of the time step and preconditioned Krylov subspace methods for the Navier-Stokes equations

The main purpose of this paper is to develop stable versions of some Krylov subspace methods for solving the linear systems of equations Ax = b which arise in the difference solution of 2-D nonstationary Navier-Stokes equations using implicit scheme and to determine a good value of the time step. Our algorithms are based on the conjugate-gradient method with a suitable preconditioner for solving the symmetric positive definite system and preconditioned GMRES, Orthomin(K), QMR methods for solving the nonsymmetric and (in)definite system. The performance of these methods is compared. In addition, we show that by using the condition number of the first nonsymmetric coefficient matrix, it is possible to determine a good value of the time step.     

Krylov子空间方法解线性方程组的并行性能分析及应用

许多并行计算问题,在结合并行机的特有体系结构时,要对算法的并行性能及其可扩展性进行分析。它决定了该算法解决有关问题是否有效,并进一步判断所用的并行计算系统是否符合求解问题的要求。文章通过对Ｋｒｙｌｏｖ子空间中两种有效算法－ＰＣＧ算法和ＧＭＲＥＳ（ｍ）算法在一类并行系统中形成的并行算法的性能进行了分析,给出了其求解问题规模与处理机数与加速比的关系结果表明。ＧＭＲＥＳ（ｍ）算法比ＰＣＧ算法更适合于并行。     

A real‐time algorithm for nonlinear receding horizon control using multiple shooting and continuation/Krylov method

In this paper, we propose a real‐time algorithm for nonlinear receding horizon control using multiple shooting and the continuation/GMRES method. Multiple shooting is expected to improve numerical accuracy in calculations for solving boundary value problems. The continuation method is combined with a Krylov subspace method, GMRES, to update unknown quantities by solving a linear equation. At the same time, we apply condensing, which reduces the size of the linear equation, to speed up numerical calculations. A numerical example shows that both numerical accuracy and computational speed improve using the proposed algorithm by combining multiple shooting with condensing. Copyright © 2008 John Wiley & Sons, Ltd.     

On the numerical modeling of convection-diffusion problems by finite element multigrid preconditioning methods

During the last decades, multigrid methods have been extensively used in order to solve large scale linear systems derived from the discretization of partial differential equations using the finite difference method. The effectiveness of the multigrid method can be also exploited by using the finite element method. Finite Element Approximate Inverses in conjunction with Richardon’s iterative method could be used as smoothers in the multigrid method. Thus, a new class of smoothers based on approximate inverses can be derived. Effectiveness of explicit approximate inverses relies in the fact that they are close approximants to the inverse of the coefficient matrix and are fast to compute in parallel. Furthermore, the proposed class of finite element approximate inverses in conjunction with the explicit preconditioned Richardson method yield improved results against the classic smoothers such as Jacobi method. Moreover, a dynamic relaxation scheme is proposed based on the Dynamic Over/Under Relaxation (DOUR) algorithm. Furthermore, results for multigrid preconditioned Krylov subspace methods, such as GMRES(res), IDR(s) and BiCGSTAB based on approximate inverse smoothing and a dynamic relaxation technique are presented for the steady-state convection-diffusion equation.     

三维热传导方程的Krylov子空间方法并行分析

热传导方程在地下水流动数值模拟、油藏数值模拟等工程计算中有着广泛应用,其并行实现是加速问题求解速度、提高问题求解规模的重要手段,因此热传导方程的并行求解具有重要意义。对Krylov子空间方法中的CG和GMRES算法进行并行分析,并对不同的预处理CG算法作了比较。在Linux集群系统上,以三维热传导模型为例进行了数值实验。实验结果表明,CG算法比GMRES算法更适合建立三维热传导模型的并行求解。此外,CG算法与BJACOBI预条件子的整合在求解该热传导模型时,其并行程序具有良好的加速比和效率。因此,采用BJACOBI预处理技术的CG算法是一种较好的求解三维热传导模型的并行方案。     

The Uzawa-PPS iteration methods for nonsingular and singular non-Hermitian saddle point problems

In this paper, based on the positive-definite and positive-semidefinite splitting (PPS) iteration scheme, we establish a class of Uzawa-PPS iteration methods for solving nonsingular and singular non-Hermitian saddle point problems with the (1,1) part of the coefficient matrix being non-Hermitian positive definite. Theoretical analyses show that the convergence and semi-convergence properties of the proposed methods can be guaranteed under suitable conditions. Furthermore, we consider acceleration of the Uzawa-PPS methods by Krylov subspace (like GMRES) methods and discuss the spectral properties of the corresponding preconditioned matrix. Numerical experiments are given to confirm the theoretical results which show that the feasibility and effectiveness of the proposed methods and preconditioners.     

基于MG-GMRES算法的图像超分辨率重建

提出了一种基于多层网格(MG)和广义极小残余(GMRES)算法相结合的图像超分辨率重建快速算法.首先采用正则化方法给出图像超分辨率重建模型;然后在系统介绍MG和GMRES算法的基础上,针对图像超分辨率重建中非对称线性稀疏方程的求解,提出多层网格-广义极小残余(MG-GMRES)算法;详细讨论了MG-GMRES算法的光滑、限制、插值操作以及计算复杂度.实验研究表明该算法的重建结果相当有效,与MG、GMRES和Richrdson迭代相比,具有更快的收敛速度.     

On semi-convergence of Hermitian and skew-Hermitian splitting methods for singular linear systems

For the singular, non-Hermitian, and positive semidefinite systems of linear equations, we derive necessary and sufficient conditions for guaranteeing the semi-convergence of the Hermitian and skew-Hermitian splitting (HSS) iteration methods. We then investigate the semi-convergence factor and estimate its upper bound for the HSS iteration method. If the semi-convergence condition is satisfied, it is shown that the semi-convergence rate is the same as that of the HSS iteration method applied to a linear system with the coefficient matrix equal to the compression of the original matrix on the range space of its Hermitian part, that is, the matrix obtained from the original matrix by restricting the domain and projecting the range space to the range space of the Hermitian part. In particular, an upper bound is obtained in terms of the largest and the smallest nonzero eigenvalues of the Hermitian part of the coefficient matrix. In addition, applications of the HSS iteration method as a preconditioner for Krylov subspace methods such as GMRES are investigated in detail, and several examples are used to illustrate the theoretical results and examine the numerical effectiveness of the HSS iteration method served either as a preconditioner for GMRES or as a solver.     

Auto-tuned Krylov methods on cluster of graphics processing unit

Exascale computers are expected to have highly hierarchical architectures with nodes composed by multiple core processors (CPU; central processing unit) and accelerators (GPU; graphics processing unit). The different programming levels generate new difficult algorithm issues. In particular when solving extremely large linear systems, new programming paradigms of Krylov methods should be defined and evaluated with respect to modern state of the art of scientific methods. Iterative Krylov methods involve linear algebra operations such as dot product, norm, addition of vectors and sparse matrix–vector multiplication. These operations are computationally expensive for large size matrices. In this paper, we aim to focus on the best way to perform effectively these operations, in double precision, on GPU in order to make iterative Krylov methods more robust and therefore reduce the computing time. The performance of our algorithms is evaluated on several matrices arising from engineering problems. Numerical experiments illustrate the robustness and accuracy of our implementation compared to the existing libraries. We deal with different preconditioned Krylov methods: Conjugate Gradient for symmetric positive-definite matrices, and Generalized Conjugate Residual, Bi-Conjugate Gradient Conjugate Residual, transpose-free Quasi Minimal Residual, Stabilized BiConjugate Gradient and Stabilized BiConjugate Gradient (L) for the solution of sparse linear systems with non symmetric matrices. We consider and compare several sparse compressed formats, and propose a way to implement effectively Krylov methods on GPU and on multicore CPU. Finally, we give strategies to faster algorithms by auto-tuning the threading design, upon the problem characteristics and the hardware changes. As a conclusion, we propose and analyse hybrid sub-structuring methods that should pave the way to exascale hybrid methods.