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.     

Preconditioned Conjugate Gradient Methods for Integral Equations of the Second Kind Defined on the Half-Line

1.IntroductionInthispaPer,westudynumericalsolutionstointegralequationsofthesecondkinddefinedonthehalfline.Morepreciselyweconsidertheequationy(t)+Iooa(t,s)y(s)ds=g(t),OS相似文献   

On Estimation of the A‐norm of the Error in CG and PCG

We concentrate on the preconditioned conjugate gradient method and describe a simple and numerically well‐justified way of estimation of the A‐norm of the error. In this way this note represents an extension of [5] and its aim is to mediate the analytic results from [5] to practical users of the preconditioned conjugate gradient method.     

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.     

Convergence Analysis of the Inexact Infeasible Interior-Point Method for Linear Optimization

We present the convergence analysis of the inexact infeasible path-following (IIPF) interior-point algorithm. In this algorithm, the preconditioned conjugate gradient method is used to solve the reduced KKT system (the augmented system). The augmented system is preconditioned by using a block triangular matrix. The KKT system is solved approximately. Therefore, it becomes necessary to study the convergence of the interior-point method for this specific inexact case. We present the convergence analysis of the inexact infeasible path-following (IIPF) algorithm, prove the global convergence of this method and provide complexity analysis. Communicated by Y. Zhang.     

一种有效的新预条件方法

该文首先提出一种有效的新预条件方法,并讨论了这种新预条件的几个重要性质;其次,证明了对于不可约严格对角占优的 Z -矩阵,新的预条件方法可以加速Jacobi迭代和Gauss-Seidel迭代法的收敛速度,并对相应迭代矩阵的谱半径做了比较,推广了已有的相关结论.文中的数值例子说明了该文提出的新预条件方法是有效的.     

解线性方程组的预条件Gauss-Seidel型迭代法

给出了解线性方程组的预条件Gauss-Seidel型方法,提出了选取合适的预条件因子．并讨论了对Z-矩阵应用这种方法的收敛性,给出了收敛最快时的系数取值．最后给出数值例子,说明选取合适的预条件因子应用Gauss-Seidel方法求解线性方程组是有效的．     

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 generalized preconditioned HSS method for non-Hermitian positive definite linear systems

Based on the HSS (Hermitian and skew-Hermitian splitting) and preconditioned HSS methods, we will present a generalized preconditioned HSS method for the large sparse non-Hermitian positive definite linear system. Our method is essentially a two-parameter iteration which can extend the possibility to optimize the iterative process. The iterative sequence produced by our generalized preconditioned HSS method can be proven to be convergent to the unique solution of the linear system. An exact parameter region of convergence for the method is strictly proved. A minimum value for the upper bound of the iterative spectrum is derived, which is relevant to the eigensystem of the products formed by inverse preconditioner and splitting. An efficient preconditioner based on incremental unknowns is presented for the actual implementation of the new method. The optimality and efficiency are effectively testified by some comparisons with numerical results.     

解线性互补问题的预处理加速模Gauss-Seidel迭代方法

本文提出了解线性互补问题的预处理加速模系Gauss-Seidel迭代方法,当线性互补问题的系统矩阵是M-矩阵时证明了方法的收敛性,并给出了该预处理方法关于原方法的一个比较定理.数值实验显示该预处理迭代方法明显加速了原方法的收敛.     

Preconditioned GSOR iterative method for a class of complex symmetric system of linear equations

In this paper, we present a preconditioned variant of the generalized successive overrelaxation (GSOR) iterative method for solving a broad class of complex symmetric linear systems. We study conditions under which the spectral radius of the iteration matrix of the preconditioned GSOR method is smaller than that of the GSOR method and determine the optimal values of iteration parameters. Numerical experiments are given to verify the validity of the presented theoretical results and the effectiveness of the preconditioned GSOR method. Copyright © 2015 John Wiley & Sons, Ltd.     

On a type of matrix splitting preconditioners for a class of block two-by-two linear systems

Recently, Bai et al. (2013) proposed an effective and efficient matrix splitting iterative method, called preconditioned modified Hermitian/skew-Hermitian splitting (PMHSS) iteration method, for two-by-two block linear systems of equations. The eigenvalue distribution of the iterative matrix suggests that the splitting matrix could be advantageously used as a preconditioner. In this study, the CGNR method is utilized for solving the PMHSS preconditioned linear systems, and the performance of the method is considered by estimating the condition number of the normal equations. Furthermore, the proposed method is compared with other PMHSS preconditioned Krylov subspace methods by solving linear systems arising in complex partial differential equations and a distributed control problem. The numerical results demonstrate the difference in the performance of the methods under consideration.     

A multigrid-based preconditioned Krylov subspace method for the Helmholtz equation with PML

In this paper, we generalize the complex shifted Laplacian preconditioner to the complex shifted Laplacian-PML preconditioner for the Helmholtz equation with perfectly matched layer (Helmholtz-PML equation). The Helmholtz-PML equation is discretized by an optimal 9-point difference scheme, and the preconditioned linear system is solved by the Krylov subspace method, especially by the biconjugate gradient stabilized method (Bi-CGSTAB). The spectral analysis of the linear system is given, and a new matrix-based interpolation operator is proposed for the multigrid method, which is used to approximately invert the preconditioner. The numerical experiments are presented to illustrate the efficiency of the preconditioned Bi-CGSTAB method with the multigrid based on the new interpolation operator, also, numerical results are given for comparing the performance of the new interpolation operator with that of classic bilinear interpolation operator and the one suggested in Erlangga et al. (2006) [10].     

求解加权线性最小二乘问题的一类预处理GAOR方法

为了快速求解一类来自加权线性最小二乘问题的2×2块线性系统,本文提出一类新的预处理子用以加速GAOR方法,也就是新的预处理GAOR方法.得到了一些比较结果,这些结果表明当GAOR方法收敛时,新方法比原GAOR方法和之前的一些预处理GAOR方法有更好的收敛性.而且,数值算例也验证了新预处理子的有效性．     

广义鞍点问题基于PSS的约束预条件子

对于(1,1)块为非Hermitian阵的广义鞍点问题,本文给出了一种基于正定和反对称分裂(Positive definite andskew-Hermitian splitting, PSS)的约束预条件子.该预条件子的(1,1)块由求解非Hermitian正定线性方程组时的PSS迭代法所构造得到.文中分析了PSS约束预条件子的一些性质并证明了预处理迭代法的收敛性.最后用数值算例验证了该预条件子的有效性.     

四阶微分方程Hermite有限元的预处理共轭梯度法

对一类四阶微分方程两点边值问题的Hermite有限元方法进行了研究.首先讨论了该方程通常意义下的Galerkin有限元离散,考虑到有限元离散得到的线性方程组的对称正定性,文中采用了预处理最速下降法和共轭梯度方法求解线性方程组,通过选择不同的预处理器,使得求解该方程组的迭代次数有了很大的改观.     

Krylov子空间投影法及其在油藏数值模拟中的应用

Krylov子空间投影法是一类非常有效的大型线性代数方程组解法,随着左右空间L_m、K_m的不同选取可以得到许多人们熟知的方法.按矩阵H_m的不同类型,将Krylov子空间方法分成两大类,简要分析了这两类方法的优缺点及其最新进展.将目前最为可靠实用的广义最小余量法(GMRES)应用于油藏数值模拟计算问题,利用矩阵分块技术,采用块拟消去法(PE)对系数阵进行预处理.计算结果表明本文的预处理GMRES方法优于目前使用较多的预处理正交极小化ORTHMIN方法,最后还讨论了投影类方法的局限和今后的可能发展方向.     

一类特殊矩阵方程的并行预处理变形共轭梯度算法

研究了求解一类矩阵方程AXB=C,提出了一种并行预处理变形共轭梯度法．该方法给出一种迭代法的预处理模式．首先给出的预处理矩阵是严格对角占优矩阵,构造并行迭代求解预处理矩阵方程的迭代格式,进而使用变形共轭梯度法并行求解．通过数值试验,预处理变形共轭梯度法与直接使用变形共轭梯度法相比较,该算法不仅有效提高了收敛速度,而且具有很高的并行性．     

Preconditioned Iterative Methods for Algebraic Systems from Multiplicative Half-Quadratic Regularization Image Restorations

<正>Image restoration is often solved by minimizing an energy function consisting of a data-fidelity term and a regularization term.A regularized convex term can usually preserve the image edges well in the restored image.In this paper,we consider a class of convex and edge-preserving regularization functions,i.e.,multiplicative half-quadratic regularizations,and we use the Newton method to solve the correspondingly reduced systems of nonlinear equations.At each Newton iterate,the preconditioned conjugate gradient method,incorporated with a constraint preconditioner,is employed to solve the structured Newton equation that has a symmetric positive definite coefficient matrix. The eigenvalue bounds of the preconditioned matrix are deliberately derived,which can be used to estimate the convergence speed of the preconditioned conjugate gradient method.We use experimental results to demonstrate that this new approach is efficient, and the effect of image restoration is reasonably well.