Preconditioned GMRES methods with incomplete Givens orthogonalization method for large sparse least-squares problems

We propose to precondition the GMRES method by using the incomplete Givens orthogonalization (IGO) method for the solution of large sparse linear least-squares problems. Theoretical analysis shows that the preconditioner satisfies the sufficient condition that can guarantee that the preconditioned GMRES method will never break down and always give the least-squares solution of the original problem. Numerical experiments further confirm that the new preconditioner is efficient. We also find that the IGO preconditioned BA-GMRES method is superior to the corresponding CGLS method for ill-conditioned and singular least-squares problems.     

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.     

关于“求解加权线性最小二乘问题的一类预处理GAOR方法”一文的注记

在"求解加权线性最小二乘问题的一类预处理GAOR方法"一文中,作者提出了求解加权线性最小二乘问题等价$2\times 2$块线性系统的一类预处理GAOR方法,并给出了几个比较定理来说明新提出预处理GAOR方法的优越性.本文我们将指出该文中几个比较定理的不完善之处和证明的错误之处,并给出正确的证明.     

Block-Projections Algorithms with Blocks Containing Mutually Orthogonal Rows and Columns

In this paper we present an algorithm which, for a given (sparse) matrix, constructs a partition of its set of row-indices, such that each subset of this partition (except the last one obtained) contains indices which correspond to mutually orthogonal rows. We then use such decompositions in some classes of block-projections methods, previously extended by the author to general inconsistent linear least-squares problems. Numerical experiments on an inconsistent and rank-deficient least-squares model problem are described in the last section of the paper.     

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.     

Greville��s method for preconditioning least squares problems

In this paper, we propose a preconditioning algorithm for least squares problems $\displaystyle{\min_{x\in{{\mathbb{R}}}^n}}\|b-Ax\|_2$ , where A can be matrices with any shape or rank. The preconditioner is constructed to be a sparse approximation to the Moore?CPenrose inverse of the coefficient matrix A. For this preconditioner, we provide theoretical analysis to show that under our assumption, the least squares problem preconditioned by this preconditioner is equivalent to the original problem, and the GMRES method can determine a solution to the preconditioned problem before breakdown happens. In the end of this paper, we also give some numerical examples showing the performance of the method.     

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

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

Multi-level preconditioned block accelerated overrelaxation iteration method for z-matrices

A class of multi-level preconditioners and corresponding preconditioned block AOR iterative method are presented and studied in this paper. We analyze the convergence performance of the new method and give the comparison theorems for different preconditioning level. Numerical results further verify our theoretical analysis and show that the proposed method has faster convergence speed than existing preconditioned block AOR method.     

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.     

Extensions of block-projections methods with relaxation parameters to inconsistent and rank-deficient least-squares problems

There exist many classes of block-projections algorithms for approximating solutions of linear least-squares problems. Generally, these methods generate sequences convergent to the minimal norm least-squares solution only for consistent problems. In the inconsistent case, which usually appears in practice because of some approximations or measurements, these sequences do no longer converge to a least-squares solution or they converge to the minimal norm solution of a “perturbed” problem. In the present paper, we overcome this difficulty by constructing extensions for almost all the above classes of block-projections methods. We prove that the sequences generated with these extensions always converge to a least-squares solution and, with a suitable initial approximation, to the minimal norm solution of the problem. Numerical experiments, described in the last section of the paper, confirm the theoretical results obtained.     

Lyapunov-type least-squares problems over symmetric cones

The Lyapunov-type least-squares problem over symmetric cone is to find the least-squares solution of the Lyapunov equation with a constraint of symmetric cone in the Euclidean Jordan algebra, and it contains the Lyapunov-type least-squares problem over cone of semidefinite matrices as a special case. In this paper, we first give a detailed analysis for the image of Lyapunov operator in the Euclidean Jordan algebra. Relying on these properties together with some characterizations of symmetric cone, we then establish some necessary and?or sufficient conditions for solution existence of the Lyapunov-type least-squares problem. Finally, we study uniqueness of the least-squares solution.     

Preconditioned Krylov subspace method for the solution of least-squares problems

We consider preconditioned Krylov subspace iteration methods, e.g., CG, LSQR and GMRES, for the solution of large sparse least-squares problems min ∥Ax – b ∥₂, with A ∈ R ^m×n, based on the Krylov subspaces K_k (BA, Br) and K_k (AB, r), respectively, where B ∈ R ^n×m is the preconditioning matrix. More concretely, we propose and implement a class of incomplete QR factorization preconditioners based on the Givens rotations and analyze in detail the efficiency and robustness of the correspondingly preconditioned Krylov subspace iteration methods. A number of numerical experiments are used to further examine their numerical behaviour. It is shown that for both overdetermined and underdetermined least-squares problems, the preconditioned GMRES methods are the best for large, sparse and ill-conditioned matrices in terms of both CPU time and iteration step. Also, comparisons with the diagonal scaling and the RIF preconditioners are given to show the superiority of the newly-proposed GMRES-type methods. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

The Optimal Preconditioning in the Domain Decomposition Method for Wilson Element

1.TheCollstructionofPreconditionerLetfil)eapolygolldolllaillillR',feL'(fl).Consi(lertheholllogeneousDiricllletboulldaryvalueProblenlofPoissonequation,Assllmethat,fordomainfi,thereareacoarsersubdivisionTHwitllIneshsizeHalldananotheroneThwithmeshsizeh,whichisobtainedbyrefiningTH'Thebotllsubdivisionssatisfythequasi-uniformityandtheillversehypothesis.FOragivenelemelltT,Pm(T)dellotesthespaceofallpolynomialswiththedegreenotgreaterthanm,Qm(T)denotesthespaceofallpolynomialswiththedegreecorres…     

A block inverse-free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems

The inverse-free preconditioned Krylov subspace method of Golub and Ye [G.H. Golub, Q. Ye, An inverse free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems, SIAM J. Sci. Comp. 24 (2002) 312-334] is an efficient algorithm for computing a few extreme eigenvalues of the symmetric generalized eigenvalue problem. In this paper, we first present an analysis of the preconditioning strategy based on incomplete factorizations. We then extend the method by developing a block generalization for computing multiple or severely clustered eigenvalues and develop a robust black-box implementation. Numerical examples are given to illustrate the analysis and the efficiency of the block algorithm.     

Preconditioning techniques for a mixed Stokes/Darcy model in porous media applications

We study numerical methods for a mixed Stokes/Darcy model in porous media applications. The global model is composed of two different submodels in a fluid region and a porous media region, coupled through a set of interface conditions. The weak formulation of the coupled model is of a saddle point type. The mixed finite element discretization applied to the saddle point problem leads to a coupled, indefinite, and nonsymmetric linear system of algebraic equations. We apply the preconditioned GMRES method to solve the discrete system and are particularly interested in efficient and effective decoupled preconditioning techniques. Several decoupled preconditioners are proposed. Theoretical analysis and numerical experiments show the effectiveness and efficiency of the preconditioners. Effects of physical parameters on the convergence performance are also investigated.     

Modified hierarchy basis for solving singular boundary value problems

In this paper, we develop an efficient preconditioning method on the basis of the modified hierarchy basis for solving the singular boundary value problem by the Galerkin method. After applying the preconditioning method, we show that the condition number of the linear system arising from the Galerkin method is uniformly bounded. In particular, the condition number of the preconditioned system will be bounded by 2 for the case q(x)=0 (see Eq. (1) in the paper). Numerical results are presented to confirm our theoretical results.     

A Black-Box Multigrid Preconditioner for the Biharmonic Equation

We examine the convergence characteristics of a preconditioned Krylov subspace solver applied to the linear systems arising from low-order mixed finite element approximation of the biharmonic problem. The key feature of our approach is that the preconditioning can be realized using any “black-box” multigrid solver designed for the discrete Dirichlet Laplacian operator. This leads to preconditioned systems having an eigenvalue distribution consisting of a tightly clustered set together with a small number of outliers. Numerical results show that the performance of the methodology is competitive with that of specialized fast iteration methods that have been developed in the context of biharmonic problems. This revised version was published online in July 2006 with corrections to the Cover Date.     

关于二阶椭圆方程区域分裂法的最优预处理

§0.引言 区域分裂是与微分方程数值解的并行计算的数学基础密切相关的,预处理共轭梯度法是区域分裂的一个主要途径,寻找好的预处理子是关键问题,本文给出一个较一般性的方法,预处理过程包括一个整体小规模问题和若干个独立的局部子问题,整体问题和局部问题的选取均有极大的任意性,预处理条件数的估计是由整体问题和局部问题的一些特     

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.     

Algebraic multigrid preconditioning for iterative eigensolvers

The objective is a comparative study of iterative solvers for eigenproblems arising from elliptic and self–adjoint partial differential operators. Typically only a few of the smallest eigenvalues of these problems are to be computed. We discuss various gradient based preconditioned eigensolvers which make use of algebraic multigrid preconditioning. We present some algorithms together with numerical results. Performance characteristics are derived by comparison with the solutions of standard problems. We show that known advantages of algebraic multigrid preconditioning (e.g. for boundary–value problems with large jumps in the coefficients) transfer to AMG–preconditioned eigensolvers. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)