Indefinitely preconditioned conjugate gradient method for large sparse equality and inequality constrained quadratic problems

This paper is concerned with the numerical solution of a symmetric indefinite system which is a generalization of the Karush–Kuhn–Tucker system. Following the recent approach of Luk?an and Vl?ek, we propose to solve this system by a preconditioned conjugate gradient (PCG) algorithm and we devise two indefinite preconditioners with good theoretical properties. In particular, for one of these preconditioners, the finite termination property of the PCG method is stated. The PCG method combined with a parallel version of these preconditioners is used as inner solver within an inexact Interior‐Point (IP) method for the solution of large and sparse quadratic programs. The numerical results obtained by a parallel code implementing the IP method on distributed memory multiprocessor systems enable us to confirm the effectiveness of the proposed approach for problems with special structure in the constraint matrix and in the objective function. Copyright © 2002 John Wiley & Sons, Ltd.     

A variant of block incomplete factorization preconditioners for a symmetricH-matrix

We propose a variant of parallel block incomplete factorization preconditioners for a symmetric block-tridiagonalH-matrix. Theoretical properties of these block preconditioners are compared with those of block incomplete factorization preconditioners for the corresponding comparison matrix. Numerical results of the preconditioned CG(PCG) method using these block preconditioners are compared with those of PCG using other types of block incomplete factorization preconditioners. Lastly, parallel computations of the block incomplete factorization preconditioners are carried out on the Cray C90.     

Factorized sparse approximate inverse preconditionings. III. Iterative construction of preconditioners

This paper presents new results of the theoretical study of factorized sparse approximate inverse (FSAI) preconditionings. In particular, the effect of the a posteriori Jacobi scaling and the possibility of constructing FSAI preconditioners iteratively are analyzed. A simple stopping criterion for the termination of local iterations in constructing approximate FSAI preconditioners using the PCG method is proposed. The results of numerical experiments with 3D finite-element problems from linear elasticity are presented. Bibliography21 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 248, 1998, pp. 17–48. Translated by L. Yu. Kolotilina.     

A QMR-based interior-point algorithm for solving linear programs

A new approach for the implementation of interior-point methods for solving linear programs is proposed. Its main feature is the iterative solution of the symmetric, but highly indefinite 2×2-block systems of linear equations that arise within the interior-point algorithm. These linear systems are solved by a symmetric variant of the quasi-minimal residual (QMR) algorithm, which is an iterative solver for general linear systems. The symmetric QMR algorithm can be combined with indefinite preconditioners, which is crucial for the efficient solution of highly indefinite linear systems, yet it still fully exploits the symmetry of the linear systems to be solved. To support the use of the symmetric QMR iteration, a novel stable reduction of the original unsymmetric 3×3-block systems to symmetric 2×2-block systems is introduced, and a measure for a low relative accuracy for the solution of these linear systems within the interior-point algorithm is proposed. Some indefinite preconditioners are discussed. Finally, we report results of a few preliminary numerical experiments to illustrate the features of the new approach.     

非匹配网格上Stokes-Darcy模型的非协调元方法及其预条件技术

本文讨论了非匹配网格上Stokes-Darcy模型的两种低阶非协调元方法,证明了离散问题的适定性并得到了最优的误差估计.对离散出来的非对称不定线性方程组,我们提出了几种有效的预条件子,证明了预条件子的最优性.最后,数值试验验证了我们的理论结果.     

Smoothed aggregation multigrid for incompressible flows

We discuss the advantages of using algebraic multigrid based on smoothed aggregation for solving indefinite linear problems. The ingredients of smoothed aggregation are used to construct a black-box monolithic multigrid method with indefinite coarse problems. Although we discuss some techniques for enforcing the uniform inf-sup stability on all coarse levels, numerical experiments suggest that it is not strictly necessary. The proposed multigrid preconditioner shows robust behaviour for different time-step parameters and even for very elongated geometries, where other techniques based on h -independent preconditioners of the pressure Schur complement lose their efficiency. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Combination preconditioning of saddle point systems for positive definiteness

Amongst recent contributions to preconditioning methods for saddle point systems, standard iterative methods in nonstandard inner products have been usefully employed. Krzy?anowski (Numerical Linear Algebra with Applications 2011; 18 :123–140) identified a two‐parameter family of preconditioners in this context and Stoll and Wathen (SIAM Journal on Matrix Analysis and Applications 2008; 30 :582–608) introduced combination preconditioning, where two preconditioners, self‐adjoint with respect to different inner products, can lead to further preconditioners and associated bilinear forms or inner products. Preconditioners that render the preconditioned saddle point matrix nonsymmetric but self‐adjoint with respect to a nonstandard inner product always allow a MINRES‐type method (‐PMINRES) to be applied in the relevant inner product. If the preconditioned matrix is also positive definite with respect to the inner product, a more efficient CG‐like method (‐PCG) can be reliably used. We establish eigenvalue expressions for Krzy?anowski preconditioners and show that for a specific choice of parameters, although the Krzy?anowski preconditioned saddle point matrix is self‐adjoint with respect to an inner product, it is never positive definite. We provide explicit expressions for the combination of certain preconditioners and prove the rather counterintuitive result that the combination of two specific preconditioners for which only ‐PMINRES can be reliably used leads to a preconditioner for which, for certain parameter choices, ‐PCG is reliably applicable. That is, combining two indefinite preconditioners can lead to a positive definite preconditioner. This combination preconditioner outperforms either of the two preconditioners from which it is formed for a number of test problems. Copyright © 2012 John Wiley & Sons, Ltd.     

Schwarz preconditioned CG algorithm for the mortar finite element

We propose a simple and effective hybrid (multiplicative) Schwarz precondtioner for solving systems of algebraic equations resulting from the mortar finite element discretization of second order elliptic problems on nonmatching meshes. The preconditioner is embedded in a variant of the classical preconditioned conjugate gradient (PCG) for an effective implementation reducing the cost of computing the matrix-vector multiplication in each iteration of the PCG. In fact, it serves as a framework for effective implementation of a class of hybrid Schwarz preconditioners. The preconditioners of this class are based on solving a sequence of non-overlapping local subproblems exactly, and the coarse problems either exactly or inexactly (approximately). The classical PCG algorithm is reformulated in order to make reuse of the results of matrix-vector multiplications that are already available from the preconditioning step resulting in an algorithm which is cost effective. An analysis of the proposed preconditioner, with numerical results, showing scalability with respect to the number of subdomains, and a convergence which is independent of the jumps of the coefficients are given.     

A Korovkin-type theory for finite Toeplitz operators via matrix algebras

Preconditioned conjugate gradients (PCG) are widely and successfully used methods for solving a Toeplitz linear system [59,9,20,5,34,62,6,10,28,45,44,46,49]. Frobenius-optimal preconditioners are chosen in some proper matrix algebras and are defined by minimizing the Frobenius distance from . The convergence features of these PCG have been naturally studied by means of the Weierstrass–Jackson Theorem [17,36,45], owing to the profound relationship between the spectral features of the matrices , generated by the Fourier coefficients of a continuous function f, and the analytical properties of the symbol f itself. In this paper, we capsize this point of view by showing that the optimal preconditioners can be used to define both new and just known linear positive operators uniformly approximating the function f. On the other hand, by modifying the Korovkin Theorem to study the Frobenius-optimal preconditioning problem, we provide a new and unifying tool for analyzing all Frobenius-optimal preconditioners in any generic matrix algebra related to trigonometric transforms. Finally, the multilevel case is sketched and discussed by showing that a Korovkin-type Theory also holds in a multivariate sense. Received October 1, 1996 / Revised version received May 7, 1998     

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.     

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.     

Higher-order quadratures for circulant preconditioned Wiener-Hopf equations

In this paper, we consider solving matrix systems arising from the discretization of Wiener-Hopf equations by preconditioned conjugate gradient (PCG) methods. Circulant integral operators as preconditioners have been proposed and studied. However, the discretization of these preconditioned equations by employing higher-order quadratures leads to matrix systems that cannot be solved efficiently by using fast Fourier transforms (FFTs). The aim of this paper is to propose new preconditioners for Wiener-Hopf equations. The discretization of these preconditioned operator equations by higher-order quadratures leads to matrix systems that involve only Toeplitz, circulant and diagonal matrix-vector multiplications and hence can be computed efficiently by FFTs in each iteration. We show that with the proper choice of kernel functions of Wiener-Hopf equations, the resulting preconditioned operators will have clustered spectra and therefore the PCG method converges very fast. Numerical examples are given to illustrate the fast convergence of the method and the improvement of the accuracy of the computed solutions with using higher-order quadratures.Research supported by the Cooperative Research Centre for Advanced Computational Systems.Research supported in part by Lee Ka Shing scholarship.     

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.     

Preconditioners for non‐Hermitian Toeplitz systems

In this paper, we construct new ω‐circulant preconditioners for non‐Hermitian Toeplitz systems, where we allow the generating function of the sequence of Toeplitz matrices to have zeros on the unit circle. We prove that the eigenvalues of the preconditioned normal equation are clustered at 1 and that for (N, N)‐Toeplitz matrices with spectral condition number 𝒪(N^α) the corresponding PCG method requires at most 𝒪(N log² N) arithmetical operations. If the generating function of the Toeplitz sequence is a rational function then we show that our preconditioned original equation has only a fixed number of eigenvalues which are not equal to 1 such that preconditioned GMRES needs only a constant number of iteration steps independent of the dimension of the problem. Numerical tests are presented with PCG applied to the normal equation, GMRES, CGS and BICGSTAB. In particular, we apply our preconditioners to compute the stationary probability distribution vector of Markovian queuing models with batch arrival. Copyright © 2001 John Wiley & Sons, Ltd.     

Preconditioning Techniques for Newton's Method for the Incompressible Navier–Stokes Equations

Newton's method for the incompressible Navier—Stokes equations gives rise to large sparse non-symmetric indefinite matrices with a so-called saddle-point structure for which Schur complement preconditioners have proven to be effective when coupled with iterative methods of Krylov type. In this work we investigate the performance of two preconditioning techniques introduced originally for the Picard method for which both proved significantly superior to other approaches such as the Uzawa method. The first is a block preconditioner which is based on the algebraic structure of the system matrix. The other approach uses also a block preconditioner which is derived by considering the underlying partial differential operator matrix. Analysis and numerical comparison of the methods are presented.This revised version was published online in October 2005 with corrections to the Cover Date.     

ILUT: A dual threshold incomplete LU factorization

In this paper we describe an Incomplete LU factorization technique based on a strategy which combines two heuristics. This ILUT factorization extends the usual ILU(O) factorization without using the concept of level of fill-in. There are two traditional ways of developing incomplete factorization preconditioners. The first uses a symbolic factorization approach in which a level of fill is attributed to each fill-in element using only the graph of the matrix. Then each fill-in that is introduced is dropped whenever its level of fill exceeds a certain threshold. The second class of methods consists of techniques derived from modifications of a given direct solver by including a dropoff rule, based on the numerical size of the fill-ins introduced, traditionally referred to as threshold preconditioners. The first type of approach may not be reliable for indefinite problems, since it does not consider numerical values. The second is often far more expensive than the standard ILU(O). The strategy we propose is a compromise between these two extremes.     

Using constraint preconditioners with regularized saddle-point problems

The problem of finding good preconditioners for the numerical solution of a certain important class of indefinite linear systems is considered. These systems are of a 2 by 2 block (KKT) structure in which the (2,2) block (denoted by -C) is assumed to be nonzero. In Constraint preconditioning for indefinite linear systems, SIAM J. Matrix Anal. Appl. 21 (2000), Keller, Gould and Wathen introduced the idea of using constraint preconditioners that have a specific 2 by 2 block structure for the case of C being zero. We shall give results concerning the spectrum and form of the eigenvectors when a preconditioner of the form considered by Keller, Gould and Wathen is used but the system we wish to solve may have C ≠0. In particular, the results presented here indicate clustering of eigenvalues and, hence, faster convergence of Krylov subspace iterative methods when the entries of C are small; such a situations arise naturally in interior point methods for optimization and we present results for such problems which validate our conclusions.     

Symmetric-triangular decomposition and its applications part II: Preconditioners for indefinite systems

As an application of the symmetric-triangular (ST) decomposition given by Golub and Yuan (2001) and Strang (2003), three block ST preconditioners are discussed here for saddle point problems. All three preconditioners transform saddle point problems into a symmetric and positive definite system. The condition number of the three symmetric and positive definite systems are estimated. Therefore, numerical methods for symmetric and positive definite systems can be applied to solve saddle point problems indirectly. A numerical example for the symmetric indefinite system from the finite element approximation to the Stokes equation is given. Finally, some comments are given as well. AMS subject classification (2000) 65F10