Steepest descent preconditioning for nonlinear GMRES optimization

Steepest descent preconditioning is considered for the recently proposed nonlinear generalized minimal residual (N‐GMRES) optimization algorithm for unconstrained nonlinear optimization. Two steepest descent preconditioning variants are proposed. The first employs a line search, whereas the second employs a predefined small step. A simple global convergence proof is provided for the N‐GMRES optimization algorithm with the first steepest descent preconditioner (with line search), under mild standard conditions on the objective function and the line search processes. Steepest descent preconditioning for N‐GMRES optimization is also motivated by relating it to standard non‐preconditioned GMRES for linear systems in the case of a standard quadratic optimization problem with symmetric positive definite operator. Numerical tests on a variety of model problems show that the N‐GMRES optimization algorithm is able to very significantly accelerate convergence of stand‐alone steepest descent optimization. Moreover, performance of steepest‐descent preconditioned N‐GMRES is shown to be competitive with standard nonlinear conjugate gradient and limited‐memory Broyden–Fletcher–Goldfarb–Shanno methods for the model problems considered. These results serve to theoretically and numerically establish steepest‐descent preconditioned N‐GMRES as a general optimization method for unconstrained nonlinear optimization, with performance that appears promising compared with established techniques. In addition, it is argued that the real potential of the N‐GMRES optimization framework lies in the fact that it can make use of problem‐dependent nonlinear preconditioners that are more powerful than steepest descent (or, equivalently, N‐GMRES can be used as a simple wrapper around any other iterative optimization process to seek acceleration of that process), and this potential is illustrated with a further application example. Copyright © 2012 John Wiley & Sons, Ltd.     

非Hermite线性方程组的若干预处理迭代算法

非Hermite线性方程组在科学和工程计算中有着重要的理论研究意义和使用价值,因此如何高效求解该类线性方程组,一直是研究者所探索的方向.通过提出一种预处理方法,对非Hermite线性方程组和具有多个右端项的复线性方程组求解的若干迭代算法进行预处理,旨在提高原算法的收敛速度.最后通过数值试验表明,所提出的若干预处理迭代算法与原算法相比较,预处理算法迭代次数大大降低,且收敛速度明显优于原算法.除此之外,广义共轭A-正交残量平方法(GCORS2)的预处理算法与其他算法相比,具有良好的收敛性行为和较好的稳定性.     

Preconditioned Barzilai-Borwein method for the numerical solution of partial differential equations

The preconditioned Barzilai-Borwein method is derived and applied to the numerical solution of large, sparse, symmetric and positive definite linear systems that arise in the discretization of partial differential equations. A set of well-known preconditioning techniques are combined with this new method to take advantage of the special features of the Barzilai-Borwein method. Numerical results on some elliptic test problems are presented. These results indicate that the preconditioned Barzilai-Borwein method is competitive and sometimes preferable to the preconditioned conjugate gradient method.This author was partially supported by the Parallel and Distributed Computing Center at UCV.This author was partially supported by BID-CONICIT, project M-51940.     

On preconditioned eigensolvers and Invert-Lanczos processes

This paper deals with the convergence analysis of various preconditioned iterations to compute the smallest eigenvalue of a discretized self-adjoint and elliptic partial differential operator. For these eigenproblems several preconditioned iterative solvers are known, but unfortunately, the convergence theory for some of these solvers is not very well understood.The aim is to show that preconditioned eigensolvers (like the preconditioned steepest descent iteration (PSD) and the locally optimal preconditioned conjugate gradient method (LOPCG)) can be interpreted as truncated approximate Krylov subspace iterations. In the limit of preconditioning with the exact inverse of the system matrix (such preconditioning can be approximated by multiple steps of a preconditioned linear solver) the iterations behave like Invert-Lanczos processes for which convergence estimates are derived.     

求解时谐涡流模型鞍点问题的分块交替分裂隐式迭代算法的改进

分块交替分裂隐式迭代方法是求解具有鞍点结构的复线性代数方程组的一类高效迭代法.本文通过预处理技巧得到原方法的一种加速改进方法,称之为预处理分块交替分裂隐式迭代方法·理论分析给出了新方法的收敛性结果.对于一类时谐涡旋电流模型问题,我们给出了若干满足收敛条件的迭代格式.数值实验验证了新型算法是对原方法的有效改进.     

On decomposition-based block preconditioned iterative methods for half-quadratic image restoration

Image restoration is a fundamental problem in image processing. Except for many different filters applied to obtain a restored image in image restoration, a degraded image can often be recovered efficiently by minimizing a cost function which consists of a data-fidelity term and a regularization term. In specific, half-quadratic regularization can effectively preserve image edges in the recovered images and a fixed-point iteration method is usually employed to solve the minimization problem. In this paper, the Newton method is applied to solve the half-quadratic regularization image restoration problem. And at each step of the Newton method, a structured linear system of a symmetric positive definite coefficient matrix arises. We design two different decomposition-based block preconditioning matrices by considering the special structure of the coefficient matrix and apply the preconditioned conjugate gradient method to solve this linear system. Theoretical analysis shows the eigenvector properties and the spectral bounds for the preconditioned matrices. The method used to analyze the spectral distribution of the preconditioned matrix and the correspondingly obtained spectral bounds are different from those in the literature. The experimental results also demonstrate that the decomposition-based block preconditioned conjugate gradient method is efficient for solving the half-quadratic regularization image restoration in terms of the numerical performance and image recovering quality.     

A parallel block overlap preconditioning with inexact submatrix inversion for linear elasticity problems

We present a parallel preconditioned iterative solver for large sparse symmetric positive definite linear systems. The preconditioner is constructed as a proper combination of advanced preconditioning strategies. It can be formally seen as being of domain decomposition type with algebraically constructed overlap. Similar to the classical domain decomposition technique, inexact subdomain solvers are used, based on incomplete Cholesky factorization. The proper preconditioner is shown to be near optimal in minimizing the so‐called K‐condition number of the preconditioned matrix. The efficiency of both serial and parallel versions of the solution method is illustrated on a set of benchmark problems in linear elasticity. Copyright © 2002 John Wiley & Sons, Ltd.     

非对称线性代数方程组的块向量算法

预条件广义共轭余量法并行和向量计算的关键是预条件计算是否可并行和向量计算，我们利用分而治之的原则，构造了一处块预条件矩阵Ｍ，这里的矩阵Ｍ是通过对线性代数方程组Ａｘ＝ｆ的矩阵Ａ进行块分解，在块分解中利用近似逆技术。这样分解形成的预条件矩阵Ｍ在迭代计算时，可向量或并行计算。     

Superlinear PCG Algorithms: Symmetric Part Preconditioning and Boundary Conditions

The superlinear convergence of the preconditioned CGM is studied for nonsymmetric elliptic problems (convection-diffusion equations) with mixed boundary conditions. A mesh independent rate of superlinear convergence is given when symmetric part preconditioning is applied to the FEM discretizations of the BVP. This is the extension of a similar result of the author for Dirichlet problems. The discussion relies on suitably developed Hilbert space theory for linear operators.     

Preconditioned GAOR methods for solving weighted linear least squares problems

In this paper, we present the preconditioned generalized accelerated overrelaxation (GAOR) method for solving linear systems based on a class of weighted linear least square problems. Two kinds of preconditioning are proposed, and each one contains three preconditioners. We compare the spectral radii of the iteration matrices of the preconditioned and the original methods. The comparison results show that the convergence rate of the preconditioned GAOR methods is indeed better than the rate of the original method, whenever the original method is convergent. Finally, a numerical example is presented in order to confirm these theoretical results.     

A splitting preconditioner for saddle point problems

For large sparse systems of linear equations iterative techniques are attractive. In this paper, we study a splitting method for an important class of symmetric and indefinite system. Theoretical analyses show that this method converges to the unique solution of the system of linear equations for all t>0 (t is the parameter). Moreover, all the eigenvalues of the iteration matrix are real and nonnegative and the spectral radius of the iteration matrix is decreasing with respect to the parameter t. Besides, a preconditioning strategy based on the splitting of the symmetric and indefinite coefficient matrices is proposed. The eigensolution of the preconditioned matrix is described and an upper bound of the degree of the minimal polynomials for the preconditioned matrix is obtained. Numerical experiments of a model Stokes problem and a least‐squares problem with linear constraints presented to illustrate the effectiveness of the method. Copyright © 2011 John Wiley & Sons, Ltd.     

An efficient numerical method for preconditioned saddle point problems

In this paper, we consider the solution of linear systems of saddle point type by a preconditioned numerical method. We first transform the original linear system into two sub-systems with small size by a preconditioning strategy, then employ the conjugate gradient (CG) method to solve the linear system with a SPD coefficient matrix, and a splitting iteration method to solve the other sub-system, respectively. Numerical experiments show that the new method can achieve faster convergence than several effective preconditioners published in the recent literature in terms of total runtime and iteration steps.     

A splitting preconditioner for the iterative solution of implicit Runge-Kutta and boundary value methods

We study preconditioned iterative methods for the linear systems arising in the numerical integration of ODEs and time-dependent PDEs by implicit Runge-Kutta and boundary value methods. A preconditioning strategy based on a Kronecker product splitting of the coefficient matrix is proposed, and some useful properties of the preconditioned matrix are established. Numerical examples are presented to illustrate the effectiveness of this approach.     

Efficient preconditioning of linear systems arising from the discretization of hyperbolic conservation laws

In this paper, we describe a novel formulation of a preconditioned BiCGSTAB algorithm for the solution of ill-conditioned linear systems Ax=b. The developed extension enables the control of the residual r _m =b–Ax _m of the approximate solution x _m independent of the specific left, right or two-sided preconditioning technique considered. Thereby, the presented modification does not require any additional computational effort and can be introduced directly into existing computer codes. Furthermore, the proceeding is not restricted to the BiCGSTAB method, hence the strategy can serve as a guideline to extend similar Krylov sub-space methods in the same manner. Based on the presented algorithm, we study the behavior of different preconditioning techniques. We introduce a new physically motivated approach within an implicit finite volume scheme for the system of the Euler equations of gas dynamics which is a typical representative of hyperbolic conservation laws. Thereupon a great variety of realistic flow problems are considered in order to give reliable statements concerning the efficiency and performance of modern preconditioning techniques.     

A preconditioning technique for a class of PDE-constrained optimization problems

We investigate the use of a preconditioning technique for solving linear systems of saddle point type arising from the application of an inexact Gauss?CNewton scheme to PDE-constrained optimization problems with a hyperbolic constraint. The preconditioner is of block triangular form and involves diagonal perturbations of the (approximate) Hessian to insure nonsingularity and an approximate Schur complement. We establish some properties of the preconditioned saddle point systems and we present the results of numerical experiments illustrating the performance of the preconditioner on a model problem motivated by image registration.     

Preconditioned Kaczmarz-Extended algorithm with relaxation parameters

We analyse in this paper the possibility of using preconditioning techniques as for square non-singular systems, also in the case of inconsistent least-squares problems. We find conditions in which the minimal norm solution of the preconditioned least-squares problem equals that of the original problem. We also find conditions such that the Kaczmarz-Extended algorithm with relaxation parameters (analysed by the author in [4]), can be adapted to the preconditioned least-squares problem. In the last section of the paper we present numerical experiments, with two variants of preconditioning, applied to an inconsistent linear least-squares model problem.     

Preconditioning for radial basis functions with domain decomposition methods

In our previous work, an effective preconditioning scheme that is based upon constructing least-squares approximation cardinal basis functions (ACBFs) from linear combinations of the RBF-PDE matrix elements has shown very attractive numerical results. The preconditioner costs O(N²) flops to set up and O(N) storage. The preconditioning technique is sufficiently general that it can be applied to different types of different operators. This was applied to the 2D multiquadric method, with c~1/√N on the Poisson test problem, the preconditioned GMRES converges in tens of iterations. In this paper, we combine the RBF methods and the ACBF preconditioning technique with the domain decomposition method (DDM). We studied different implementations of the ACBF-DDM scheme and provide numerical results for N > 10,000 nodes. We shall demonstrate that the efficiency of the ACBF-DDM scheme improves dramatically as successively finer partitions of the domain are considered.     

Eigenvalue estimates for a preconditioned Galerkin matrix arising from mixed finite element discretizations of viscous incompressible flows

The article deals with Galerkin matrices arising with finite element discretizations of the Navier–Stokes system. Usually these matrices are indefinite and nonsymmetric. They have to be preconditioned if a related linear system is to be solved efficiently by an iterative method. We consider preconditioning by a pressure mass matrix. It is shown how upper and lower bounds of the eigenvalues of a preconditioned Galerkin matrix may be found by variational arguments.     

PMHSS iteration method and preconditioners for Stokes control PDE-constrained optimization problems

Numerical Algorithms - The preconditioned modified Hermitian/skew-Hermitian splitting (PMHSS) iteration method and the corresponding preconditioning technique can achieve satisfactory results for...     

On approximated ILU and UGS preconditioning methods for linearized discretized steady incompressible Navier-Stokes equations

When the artificial compressibility method in conjunction with high-order upwind compact finite difference schemes is employed to discretize the steady-state incompressible Navier-Stokes equations, in each pseudo-time step we need to solve a structured system of linear equations approximately by, for example, a Krylov subspace method such as the preconditioned GMRES. In this paper, based on the special structure and concrete property of the linear system we construct a structured preconditioner for its coefficient matrix and estimate eigenvalue bounds of the correspondingly preconditioned matrix. Numerical examples are given to illustrate the effectiveness of the proposed preconditioning methods.