On HSS-based constraint preconditioners for generalized saddle-point problems

For the generalized saddle-point problems with non-Hermitian (1,1) blocks, we present an HSS-based constraint preconditioner, in which the (1,1) block of the preconditioner is constructed by the HSS method for solving the non-Hermitian positive definite linear systems. We analyze the invertibility of the HSS-based constraint preconditioner and prove the convergence of the preconditioned iteration method. Numerical experiments are used to demonstrate the efficiency of the preconditioner as well as the corresponding preconditioned iteration method, especially when the (1,1) block of the saddle-point matrix is essentially non-Hermitian.     

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     

Preconditioned sor methods for generalized least-squares problems

1.IntroductionThegeneralizedleastsquaresproblem,definedasmin(Ax--b)"W--'(Ax--b),(1.1)xacwhereAERm",m>n,bERm,andWERm'misasymmetricandpositivedefinitematrix,isfrequentlyfoundwhensolvingproblemsinstatistics,engineeringandeconomics.Forexample,wegetgeneralizedleastsquaresproblemswhensolvingnonlinearregressionanalysisbyquasi-likelihoodestimation,imagereconstructionproblemsandeconomicmodelsobtainedbythemaximumlikelihoodmethod(of.[1,21).Paige[3,4]investigatestheproblemexplicitly.Hechangestheorig…     

On preconditioned Uzawa methods and SOR methods for saddle-point problems

This paper studies convergence analysis of a preconditioned inexact Uzawa method for nondifferentiable saddle-point problems. The SOR-Newton method and the SOR-BFGS method are special cases of this method. We relax the Bramble-Pasciak-Vassilev condition on preconditioners for convergence of the inexact Uzawa method for linear saddle-point problems. The relaxed condition is used to determine the relaxation parameters in the SOR-Newton method and the SOR-BFGS method. Furthermore, we study global convergence of the multistep inexact Uzawa method for nondifferentiable saddle-point problems.     

On block preconditioners for saddle point problems with singular or indefinite (1, 1) block

We discuss a class of preconditioning methods for the iterative solution of symmetric algebraic saddle point problems, where the (1, 1) block matrix may be indefinite or singular. Such problems may arise, e.g. from discrete approximations of certain partial differential equations, such as the Maxwell time harmonic equations. We prove that, under mild assumptions on the underlying problem, a class of block preconditioners (including block diagonal, triangular and symmetric indefinite preconditioners) can be chosen in a way which guarantees that the convergence rate of the preconditioned conjugate residuals method is independent of the discretization mesh parameter. We provide examples of such preconditioners that do not require additional scaling. Copyright © 2010 John Wiley & Sons, Ltd.     

Substructuring preconditioners for saddle-point problems arising from Maxwell's equations in three dimensions

This paper is concerned with the saddle-point problems arising from edge element discretizations of Maxwell's equations in a general three dimensional nonconvex polyhedral domain. A new augmented technique is first introduced to transform the problems into equivalent augmented saddle-point systems so that they can be solved by some existing preconditioned iterative methods. Then some substructuring preconditioners are proposed, with very simple coarse solvers, for the augmented saddle-point systems. With the preconditioners, the condition numbers of the preconditioned systems are nearly optimal; namely, they grow only as the logarithm of the ratio between the subdomain diameter and the finite element mesh size.

     

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 modified positive-definite and skew-Hermitian splitting preconditioner for generalized saddle point problems from the Navier-Stokes equation

In this paper, we extend the relaxed positive-definite and skew-Hermitian splitting preconditioner (RPSS) for generalized saddle-point problems in [J.-L. Zhang, C.-Q. Gu and K. Zhang, Appl. Math. Comput. 249(2014)468-479] by introducing an additional parameter. The spectral properties of the presented new preconditioned matrix for generalized saddle-point problem are investigated, meanwhile, the infinite termination merit of the iterative step is also discussed if the Krylov subspace method preconditioned by the modified positive-definite and skew-Hermitian splitting preconditioner (MPSS) is applied. Some numerical experiments illustrate that the efficiency of the proposed new preconditioner.     

Optimal convergence analysis of mixed finite element methods for fourth‐order elliptic and parabolic problems

By using a special interpolation operator developed by Girault and Raviart (finite element methods for Navier‐Stokes Equations, Springer‐Verlag, Berlin, 1986), we prove that optimal error bounds can be obtained for a fourth‐order elliptic problem and a fourth‐order parabolic problem solved by mixed finite element methods on quasi‐uniform rectangular meshes. Optimal convergence is proved for all continuous tensor product elements of order k ≥ 1. A numerical example is provided for solving the fourth‐order elliptic problem using the bilinear element. © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2006     

Hilbert空间的正交分解及其应用

基于Riesz-表示算子,给出了实Hilbert内积空间按某种连续双线性泛函的正交分解的刻划,应用于鞍点变分问题,获得了解的分离及其强制型于问题.     

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].     

PRECONDITIONING MIXED ELEMENT METHOD FOR NONSELFADJOINT AND INDEFINITE SECOND ORDER ELLIPTIC PROBLEMS*

In this paper, an equivalence between mixed element method and nonconforming element method for nonselfad joint and indefinite second order elliptic problems is established without using any bubble functions. It is proved that the H~1-condition number of preconditioned operator B_h~(-1)A_h is uniformly bounded and its B_h-singular values cluster in a positive finite interval, where A_h is the equivalent nonconforming element discretization of nonselfad joint and indefinite second order elliptic operator A, B_h is usual noncon forming element discretization of selfadjoint and positive definite second order elliptic operator B. Finally a simple V-cycle multigrid implementation of B_h~(-1) is given.     

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.     

Incomplete block-matrix factorization iterative methods for convection-diffusion problems

Standard Galerkin finite element methods or finite difference methods for singular perturbation problems lead to strongly unsymmetric matrices, which furthermore are in general notM-matrices. Accordingly, preconditioned iterative methods such as preconditioned (generalized) conjugate gradient methods, which have turned out to be very successful for symmetric and positive definite problems, can fail to converge or require an excessive number of iterations for singular perturbation problems.This is not so much due to the asymmetry, as it is to the fact that the spectrum can have both eigenvalues with positive and negative real parts, or eigenvalues with arbitrary small positive real parts and nonnegligible imaginary parts. This will be the case for a standard Galerkin method, unless the meshparameterh is chosen excessively small. There exist other discretization methods, however, for which the corresponding bilinear form is coercive, whence its finite element matrix has only eigenvalues with positive real parts; in fact, the real parts are positive uniformly in the singular perturbation parameter.In the present paper we examine the streamline diffusion finite element method in this respect. It is found that incomplete block-matrix factorization methods, both on classical form and on an inverse-free (vectorizable) form, coupled with a general least squares conjugate gradient method, can work exceptionally well on this type of problem. The number of iterations is sometimes significantly smaller than for the corresponding almost symmetric problem where the velocity field is close to zero or the singular perturbation parameter =1.The 2 ^nd author's research was sponsored by Control Data Corporation through its PACER fellowship program.The 3 ^rd author's research was supported by the Netherlands organization for scientific research (NWO).On leave from the Institute of Mathematics, Academy of Science, 1090 Sofia, P.O. Box 373, Bulgaria.     

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.     

Inexact inner–outer Golub–Kahan bidiagonalization method: A relaxation strategy

We study an inexact inner–outer generalized Golub–Kahan algorithm for the solution of saddle-point problems with a two-times-two block structure. In each outer iteration, an inner system has to be solved which in theory has to be done exactly. Whenever the system is getting large, an inner exact solver is, however, no longer efficient or even feasible and iterative methods must be used. We focus this article on a numerical study showing the influence of the accuracy of an inner iterative solution on the accuracy of the solution of the block system. Emphasis is further given on reducing the computational cost, which is defined as the total number of inner iterations. We develop relaxation techniques intended to dynamically change the inner tolerance for each outer iteration to further minimize the total number of inner iterations. We illustrate our findings on a Stokes problem and validate them on a mixed formulation of the Poisson problem.     

A domain embedding preconditioner for the Lagrange multiplier system

Finite element approximations for the Dirichlet problem associated to a second-order elliptic differential equation are studied. The purpose of this paper is to discuss domain embedding preconditioners for discrete systems. The essential boundary condition on the interior interface is removed by introducing Lagrange multipliers. The associated discrete system, with a saddle point structure, is preconditioned by a block diagonal preconditioner. The main contribution of this paper is to propose a new operator, constructed from the -inner product, for the block of the preconditioner corresponding to the multipliers.

     

广义块Toeplitz特征值问题的基于sine变换的预处理子

在求块Toeplitz矩阵束（Amn，Bmn）特征值的Lanczos过程中，通过对移位块Toepltz矩阵Amn-ρBmn进行基于sine变换的块预处理，从而改进了位移块Toeplitz矩阵的谱分布，加速了Lanczos过程的收敛速度．该块预处理方法能通过快速算法有效快速执行．本文证明了预处理后Lanczos过程收敛迅速，并通过实验证明该算法求解大规模矩阵问题尤其有效．     

New a priori analysis of first‐order system least‐squares finite element methods for parabolic problems

We provide new insights into the a priori theory for a time‐stepping scheme based on least‐squares finite element methods for parabolic first‐order systems. The elliptic part of the problem is of general reaction‐convection‐diffusion type. The new ingredient in the analysis is an elliptic projection operator defined via a nonsymmetric bilinear form, although the main bilinear form corresponding to the least‐squares functional is symmetric. This new operator allows to prove optimal error estimates in the natural norm associated to the problem and, under additional regularity assumptions, in the L² norm. Numerical experiments are presented which confirm our theoretical findings.     

Uzawa type algorithms for nonsymmetric saddle point problems

In this paper, we consider iterative algorithms of Uzawa type for solving linear nonsymmetric saddle point problems. Specifically, we consider systems, written as usual in block form, where the upper left block is an invertible linear operator with positive definite symmetric part. Such saddle point problems arise, for example, in certain finite element and finite difference discretizations of Navier-Stokes equations, Oseen equations, and mixed finite element discretization of second order convection-diffusion problems. We consider two algorithms, each of which utilizes a preconditioner for the operator in the upper left block. Convergence results for the algorithms are established in appropriate norms. The convergence of one of the algorithms is shown assuming only that the preconditioner is spectrally equivalent to the inverse of the symmetric part of the operator. The other algorithm is shown to converge provided that the preconditioner is a sufficiently accurate approximation of the inverse of the upper left block. Applications to the solution of steady-state Navier-Stokes equations are discussed, and, finally, the results of numerical experiments involving the algorithms are presented.