Conditioning analysis of block incomplete factorizations and its application to elliptic equations

Summary. The paper deals with eigenvalue estimates for block incomplete factorization methods for symmetric matrices. First, some previous results on upper bounds for the maximum eigenvalue of preconditioned matrices are generalized to each eigenvalue. Second, upper bounds for the maximum eigenvalue of the preconditioned matrix are further estimated, which presents a substantial improvement of earlier results. Finally, the results are used to estimate bounds for every eigenvalue of the preconditioned matrices, in particular, for the maximum eigenvalue, when a modified block incomplete factorization is used to solve an elliptic equation with variable coefficients in two dimensions. The analysis yields a new upper bound of type for the condition number of the preconditioned matrix and shows clearly how the coefficients of the differential equation influence the positive constant . Received March 27, 1996 / Revised version received December 27, 1996     

Preconditioning Indefinite Systems in Interior Point Methods for Optimization

Every Newton step in an interior-point method for optimization requires a solution of a symmetric indefinite system of linear equations. Most of today's codes apply direct solution methods to perform this task. The use of logarithmic barriers in interior point methods causes unavoidable ill-conditioning of linear systems and, hence, iterative methods fail to provide sufficient accuracy unless appropriately preconditioned. Two types of preconditioners which use some form of incomplete Cholesky factorization for indefinite systems are proposed in this paper. Although they involve significantly sparser factorizations than those used in direct approaches they still capture most of the numerical properties of the preconditioned system. The spectral analysis of the preconditioned matrix is performed: for convex optimization problems all the eigenvalues of this matrix are strictly positive. Numerical results are given for a set of public domain large linearly constrained convex quadratic programming problems with sizes reaching tens of thousands of variables. The analysis of these results reveals that the solution times for such problems on a modern PC are measured in minutes when direct methods are used and drop to seconds when iterative methods with appropriate preconditioners are used.     

Numerical experiments in computing bounds for the norm of the error in the preconditioned conjugate gradient algorithm

In this paper we consider algorithms to compute bounds of the A-norm of the error in the preconditioned conjugate gradient (PCG) algorithm. We extend to PCG formulas that were given in an earlier paper [8]. We give numerical experiments which show that good upper and lower bounds can be obtained provided estimates of the lowest and largest eigenvalues of the preconditioned matrix are given or adaptively computed. This revised version was published online in August 2006 with corrections to the Cover Date.     

Eigenvalue bounds for block preconditioned matrices

In the symmetric positive definite case, two-sided eigenvalue bounds for block Jacobi scaled matrices and upper eigenvalue bounds for matrices preconditioned with an incomplete block factorization are derived. A quantitative characterization of block matrix partitionings is also suggested, which can be used when analyzing various block preconditioning methods. Bibliography: 13 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 219, 1994, pp. 5–41.     

Error bounds for the finite-element approximation of the exterior Stokes equations in two dimensions

In this paper we design high-order (non)local artificial boundaryconditions (ABCs) which are different from those proposed byHan, H. & Bao, W. (1997 Numer. Math., 77, 347–363)for incompressible materials, and present error bounds for thefinite-element approximation of the exterior Stokes equationsin two dimensions. The finite-element approximation (especiallyits corresponding stiff matrix) becomes much simpler (sparser)when it is formulated in a bounded computational domain usingthe new (non)local approximate ABCs. Our error bounds indicatehow the errors of the finite-element approximations depend onthe mesh size, terms used in the approximate ABCs and the locationof the artificial boundary. Numerical examples of the exteriorStokes equations outside a circle in the plane are presented.Numerical results demonstrate the performance of our error bounds.     

Preconditioning of two-by-two block matrix systems with square matrix blocks,with applications

Two-by-two block matrices of special form with square matrix blocks arise in important applications, such as in optimal control of partial differential equations and in high order time integration methods.Two solution methods involving very efficient preconditioned matrices, one based on a Schur complement reduction of the given system and one based on a transformation matrix with a perturbation of one of the given matrix blocks are presented. The first method involves an additional inner solution with the pivot matrix block but gives a very tight condition number bound when applied for a time integration method. The second method does not involve this matrix block but only inner solutions with a linear combination of the pivot block and the off-diagonal matrix blocks.Both the methods give small condition number bounds that hold uniformly in all parameters involved in the problem, i.e. are fully robust. The paper presents shorter proofs, extended and new results compared to earlier publications.     

Residual a posteriori error estimates for a 3D mortar finite-element method: the Stokes system

We consider a non-conforming domain decomposition techniquefor the discretization of the three-dimensional Stokes equationsby the mortar finite-element method. Relying on the velocity–pressureformulation of the system, we perform the numerical analysisof residual error indicators for this problem and we prove thatthe error estimators provide upper and lower bounds for theenergy norm of the mortar finite-element solution.     

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.     

Bounds for the solution set of linear complementarity problems

We give here bounds for the feasible domain and the solution norm of Linear Complementarity Problems (LCP). These bounds are motivated by formulating the LCP as a global quadratic optimization problem and are characterized by the eigenstructure of the corresponding matrix. We prove boundedness of the feasible domain when the quadratic problem is concave, and give easily computable bounds for the solution norm for the convex case. We also obtain lower and upper bounds for the solution norm of the general nonconvex problem.     

Block‐triangular preconditioners for PDE‐constrained optimization

In this paper we investigate the possibility of using a block‐triangular preconditioner for saddle point problems arising in PDE‐constrained optimization. In particular, we focus on a conjugate gradient‐type method introduced by Bramble and Pasciak that uses self‐adjointness of the preconditioned system in a non‐standard inner product. We show when the Chebyshev semi‐iteration is used as a preconditioner for the relevant matrix blocks involving the finite element mass matrix that the main drawback of the Bramble–Pasciak method—the appropriate scaling of the preconditioners—is easily overcome. We present an eigenvalue analysis for the block‐triangular preconditioners that gives convergence bounds in the non‐standard inner product and illustrates their competitiveness on a number of computed examples. Copyright © 2010 John Wiley & Sons, Ltd.     

Equality conditions for lower bounds on the smallest singular value of a bidiagonal matrix

Several lower bounds have been proposed for the smallest singular value of a square matrix, such as Johnson’s bound, Brauer-type bound, Li’s bound and Ostrowski-type bound. In this paper, we focus on a bidiagonal matrix and investigate the equality conditions for these bounds. We show that the former three bounds give strict lower bounds if all the bidiagonal elements are non-zero. For the Ostrowski-type bound, we present an easily verifiable necessary and sufficient condition for the equality to hold.     

New upper solution bounds of the discrete algebraic Riccati matrix equation

In this note, we present upper matrix bounds for the solution of the discrete algebraic Riccati equation (DARE). Using the matrix bound of Theorem 2.2, we then give several eigenvalue upper bounds for the solution of the DARE and make comparisons with existing results. The advantage of our results over existing upper bounds is that the new upper bounds of Theorem 2.2 and Corollary 2.1 are always calculated if the stabilizing solution of the DARE exists, whilst all existing upper matrix bounds might not be calculated because they have been derived under stronger conditions. Finally, we give numerical examples to demonstrate the effectiveness of the derived results.     

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.     

BANDED TOEPLITZ PRECONDITIONERS FOR TOEPLITZ MATRICES FROM SINC METHODS

We give general expressions, analyze algebraic properties and derive eigenvalue bounds for a sequence of Toeplitz matrices associated with the sinc discretizations of various orders of differential operators. We demonstrate that these Toeplitz matrices can be satisfactorily preconditioned by certain banded Toeplitz matrices through showing that the spectra of the preconditioned matrices are uniformly bounded. In particular, we also derive eigenvalue bounds for the banded Toeplitz preconditioners. These results are elementary in constructing high-quality structured preconditioners for the systems of linear equations arising from the sinc discretizations of ordinary and partial differential equations, and are useful in analyzing algebraic properties and deriving eigenvalue bounds for the corresponding preconditioned matrices. Numerical examples are given to show effectiveness of the banded Toeplitz preconditioners.     

一类Toeplitz线性代数方程组的预处理GMRES方法

本文研究一类来源于分数阶特征值问题的Toeplitz线性代数方程组的求解.构造Strang循环矩阵作为预处理矩阵来求解该Toeplitz线性代数方程组,分析了预处理后系数矩阵的特征值性质.提出求解该线性代数方程组的预处理广义极小残量法（PGMRES）,并给出该算法的计算量.数值算例表明了该方法的有效性.     

On SSOR‐like preconditioners for non‐Hermitian positive definite matrices

We construct, analyze, and implement SSOR‐like preconditioners for non‐Hermitian positive definite system of linear equations when its coefficient matrix possesses either a dominant Hermitian part or a dominant skew‐Hermitian part. We derive tight bounds for eigenvalues of the preconditioned matrices and obtain convergence rates of the corresponding SSOR‐like iteration methods as well as the corresponding preconditioned GMRES iteration methods. Numerical implementations show that Krylov subspace iteration methods such as GMRES, when accelerated by the SSOR‐like preconditioners, are efficient solvers for these classes of non‐Hermitian positive definite linear systems. Copyright © 2015 John Wiley & Sons, Ltd.     

正则化HSS预处理鞍点矩阵的特征值估计

最近,Bai和Benzi针对鞍点问题提出了一类正则化HSS（Regularized Hermitian and skew-Hermitian splitting,RHSS）预处理子（BIT Numer.Math.,57（2017）287-311）.为了进一步分析RHSS预处理子的效果,本文重点研究了RHSS预处理鞍点矩阵特征值的估计,分析了复特征值实部和模的上下界、实特征值的上下界,还给出了特征值均为实数的充分条件.当正则化矩阵取为零矩阵时,RHSS预处理子退化为HSS预处理子,分析表明本文给出的复特征值实部的界比已有的结果更精确.数值算例验证了本文给出的理论结果.     

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.     

A preconditioner for generalized saddle point problems: Application to 3D stationary Navier‐Stokes equations

In this article we consider the stationary Navier‐Stokes system discretized by finite element methods which do not satisfy the inf‐sup condition. These discretizations typically take the form of a variational problem with stabilization terms. Such a problem may be transformed by iteration methods into a sequence of linear, Oseen‐type variational problems. On the algebraic level, these problems belong to a certain class of linear systems with nonsymmetric system matrices (“generalized saddle point problems”). We show that if the underlying finite element spaces satisfy a generalized inf‐sup condition, these problems have a unique solution. Moreover, we introduce a block triangular preconditioner and we show how the eigenvalue bounds of the preconditioned system matrix depend on the coercivity constant and continuity bounds of the bilinear forms arising in the variational problem. Finally we prove that the stabilized P1‐P1 finite element method proposed by Rebollo is covered by our theory and we show that the condition number of the preconditioned system matrix is independent of the mesh size. Numerical tests with 3D stationary Navier‐Stokes flows confirm our results. © 2006 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2006     

Finite-element investigation of the stress-strain state of an inhomogeneous rectangular plate

With the use of the finite-element method, the generalized plane stressed state of a rectangle of isotropic functionally gradient materials under the action of normal load is investigated. A finite-element model is constructed by the Bubnov–Galerkin method. The domain of the body is split into rectangular gradient elements that take into account dependences of Young’s modulus and Poisson’s ratios on coordinates. Numerical calculations are performed for the case where Young’s modulus is a polynomial function. The influence of the material gradientness and the sizes of the rectangle on its stress-strain state is analyzed.