Block triangular preconditioners for nonsymmetric saddle point problems: field-of-values analysis

A preconditioned minimal residual method for nonsymmetric saddle point problems is analyzed. The proposed preconditioner is of block triangular form. The aim of this article is to show that a rigorous convergence analysis can be performed by using the field of values of the preconditioned linear system. As an example, a saddle point problem obtained from a mixed finite element discretization of the Oseen equations is considered. The convergence estimates obtained by using a field–of–values analysis are independent of the discretization parameter h. Several computational experiments supplement the theoretical results and illustrate the performance of the method. Received March 20, 1997 / Revised version received January 14, 1998     

BTTB preconditioners for BTTB least squares problems

In this paper, we consider solving the least squares problem min_x‖b-Tx‖₂ by using preconditioned conjugate gradient (PCG) methods, where T is a large rectangular matrix which consists of several square block-Toeplitz-Toeplitz-block (BTTB) matrices and b is a column vector. We propose a BTTB preconditioner to speed up the PCG method and prove that the BTTB preconditioner is a good preconditioner. We then discuss the construction of the BTTB preconditioner. Numerical examples, including image restoration problems, are given to illustrate the efficiency of our BTTB preconditioner. Numerical results show that our BTTB preconditioner is more efficient than the well-known Level-1 and Level-2 circulant preconditioners.     

On block-circulant preconditioners for high-order compact approximations of convection-diffusion problems

We study some properties of block-circulant preconditioners for high-order compact approximations of convection-diffusion problems. For two-dimensional problems, the approximation gives rise to a nine-point discretisation matrix and in three dimensions, we obtain a nineteen-point matrix. We derive analytical expressions for the eigenvalues of the block-circulant preconditioner and this allows us to establish the invertibility of the preconditioner in both two and three dimensions. The eigenspectra of the preconditioned matrix in the two-dimensional case is described for different test cases. Our numerical results indicate that the block-circulant preconditioning leads to significant reduction in iteration counts and comparisons between the high-order compact and upwind discretisations are carried out. For the unpreconditioned systems, we observe fewer iteration counts for the HOC discretisation but for the preconditioned systems, we find similar iteration counts for both finite difference approximations of constant-coefficient two-dimensional convection-diffusion problems.     

Limiting accuracy of segregated solution methods for nonsymmetric saddle point problems

Nonsymmetric saddle point problems arise in a wide variety of applications in computational science and engineering. The aim of this paper is to discuss the numerical behavior of several nonsymmetric iterative methods applied for solving the saddle point systems via the Schur complement reduction or the null-space projection approach. Krylov subspace methods often produce the iterates which fluctuate rather strongly. Here we address the question whether large intermediate approximate solutions reduce the final accuracy of these two-level (inner–outer) iteration algorithms. We extend our previous analysis obtained for symmetric saddle point problems and distinguish between three mathematically equivalent back-substitution schemes which lead to a different numerical behavior when applied in finite precision arithmetic. Theoretical results are then illustrated on a simple model example.     

A class of Uzawa-SOR methods for saddle point problems

In this paper, we consider a class of Uzawa-SOR methods for saddle point problems, and prove the convergence of the proposed methods. We solve a lower triangular system per iteration in the proposed methods, instead of solving a linear equation Az=b. Actually, the new methods can be considered as an inexact iteration method with the Uzawa as the outer iteration and the SOR as the inner iteration. Although the proposed methods cannot achieve the same convergence rate as the GSOR methods proposed by Bai et al. [Z.-Z. Bai, B.N. Parlett, Z.-Q. Wang, On generalized successive overrelaxation methods for augmented linear systems, Numer. Math. 102 (2005) 1-38], but our proposed methods have less workloads per iteration step. Experimental results show that our proposed methods are feasible and effective.     

Parameterized preconditioning for generalized saddle point problems arising from the Stokes equation

A parameterized preconditioning framework is proposed to improve the conditions of the generalized saddle point problems. Based on the eigenvalue estimates for the generalized saddle point matrices, a strategy to minimize the upper bounds of the spectral condition numbers of the matrices is given, and the explicit expression of the quasi-optimal preconditioning parameter is obtained. In numerical experiment, parameterized preconditioning techniques are applied to the generalized saddle point problems derived from the mixed finite element discretization of the stationary Stokes equation. Numerical results demonstrate that the involved preconditioning procedures are efficient.     

On nonsymmetric saddle point matrices that allow conjugate gradient iterations

Linear systems in saddle point form are usually highly indefinite,which often slows down iterative solvers such as Krylov subspace methods. It has been noted by several authors that negating the second block row of a symmetric indefinite saddle point matrix leads to a nonsymmetric matrix ${{\mathcal A}}Linear systems in saddle point form are usually highly indefinite,which often slows down iterative solvers such as Krylov subspace methods. It has been noted by several authors that negating the second block row of a symmetric indefinite saddle point matrix leads to a nonsymmetric matrix whose spectrum is entirely contained in the right half plane. In this paper we study conditions so that is diagonalizable with a real and positive spectrum. These conditions are based on necessary and sufficient conditions for positive definiteness of a certain bilinear form,with respect to which is symmetric. In case the latter conditions are satisfied, there exists a well defined conjugate gradient (CG) method for solving linear systems with . We give an efficient implementation of this method, discuss practical issues such as error bounds, and present numerical experiments. In memory of Gene Golub (1932–2007), our wonderful friend and colleague, who had a great interest in the conjugate gradient method and the numerical solution of saddle point problems. The work of J?rg Liesen was supported by the Emmy Noether-Program and the Heisenberg-Program of the Deutsche Forschungsgemeinschaft.     

The spectral properties of the preconditioned matrix for nonsymmetric saddle point problems

In this paper, on the basis of matrix splitting, two preconditioners are proposed and analyzed, for nonsymmetric saddle point problems. The spectral property of the preconditioned matrix is studied in detail. When the iteration parameter becomes small enough, the eigenvalues of the preconditioned matrices will gather into two clusters—one is near (0,0) and the other is near (2,0)—for the PPSS preconditioner no matter whether A is Hermitian or non-Hermitian and for the PHSS preconditioner when A is a Hermitian or real normal matrix. Numerical experiments are given, to illustrate the performances of the two preconditioners.     

Circulant and skew-circulant preconditioners for skew-hermitian type Toeplitz systems

We study the solutions of Toeplitz systemsA _n x=b by the preconditioned conjugate gradient method. Then ×n matrixA _n is of the forma ₀ I+H _n wherea ₀ is a real number,I is the identity matrix andH _n is a skew-Hermitian Toeplitz matrix. Such matrices often appear in solving discretized hyperbolic differential equations. The preconditioners we considered here are the circulant matrixC _n and the skew-circulant matrixS _n whereA _n =1/2(C _n +S _n ). The convergence rate of the iterative method depends on the distribution of the singular values of the matricesC ^–1 _n A_n andS ^–1 _n A _n . For Toeplitz matricesA _n with entries which are Fourier coefficients of functions in the Wiener class, we show the invertibility ofC _n andS _n and prove that the singular values ofC ^–1 _n A _n andS ^–1 _n A _n are clustered around 1 for largen. Hence, if the conjugate gradient method is applied to solve the preconditioned systems, we expect fast convergence.     

Hartley preconditioners for Toeplitz systems generated by positive continuous functions

In this paper, we consider the solution ofn-by-n symmetric positive definite Toeplitz systemsT _n x=b by the preconditioned conjugate gradient (PCG) method. The preconditionerM _n is defined to be the minimizer of T _n –B _{n F} over allB _n H _n whereH _n is the Hartley algebra. We show that if the generating functionf ofT _n is a positive 2-periodic continuous even function, then the spectrum of the preconditioned systemM _n ^–1 T _n will be clustered around 1. Thus, if the PCG method is applied to solve the preconditioned system, the convergence rate will be superlinear.     

The spectral properties of the Hermitian and skew-Hermitian splitting preconditioner for generalized saddle point problems

In this paper, we consider the Hermitian and skew-Hermitian splitting (HSS) preconditioner for generalized saddle point problems with nonzero (2, 2) blocks. The spectral property of the preconditioned matrix is studied in detail. Under certain conditions, all eigenvalues of the preconditioned matrix with the original system being non-Hermitian will form two tight clusters, one is near (0, 0) and the other is near (2, 0) as the iteration parameter approaches to zero from above, so do all eigenvalues of the preconditioned matrix with the original system being Hermitian. Numerical experiments are given to demonstrate the results.     

A class of iterative methods for solving saddle point problems

Summary We consider the numerical solution of indefinite systems of linear equations arising in the calculation of saddle points. We are mainly concerned with sparse systems of this type resulting from certain discretizations of partial differential equations. We present an iterative method involving two levels of iteration, similar in some respects to the Uzawa algorithm. We relate the rates of convergence of the outer and inner iterations, proving that, under natural hypotheses, the outer iteration achieves the rate of convergence of the inner iteration. The technique is applied to finite element approximations of the Stokes equations.The work of this author was supported by the Office of Naval Research under contract N00014-82K-0197, by Avions Marcel Dassault, 78 Quai Marcel Dassault, 92214 St Cloud, France, and by Direction des Recherches Etudes et Techniques, 26 boulevard Victor, F-75996 Paris Armées, FranceThe work of this author was supported by Avions Marcel Daussault-Breguet Aviation, 78 quai Marcel Daussault, F-92214 St Cloud, France and by Direction des Recherches Etudes et Techniques, 26 boulevard Victor, F-75996 Paris Armées, FranceThe work of this author was supported by Konrad-Zuse-Zentrum für Informationstechnik Berlin, Federal Republic of Germany     

A note on best conditioned preconditioners

We discuss the solution of Hermitian positive definite systemsAx=b by the preconditioned conjugate gradient method with a preconditionerM. In general, the smaller the condition number(M ^–1/2 AM ^–1/2 ) is, the faster the convergence rate will be. For a given unitary matrixQ, letM _Q = {Q* _N Q | _n is ann-by-n complex diagonal matrix} andM _Q ⁺ ={Q* _n Q | _n is ann-by-n positive definite diagonal matrix}. The preconditionerM _b that minimizes(M ^–1/2 AM ^–1/2 ) overM _Q ⁺ is called the best conditioned preconditioner for the matrixA overM _Q ⁺ . We prove that ifQAQ* has Young's Property A, thenM _b is nothing new but the minimizer of M –A _F overM _Q . Here · _F denotes the Frobenius norm. Some applications are also given here.     

Spectral properties of primal-based penalty preconditioners for saddle point problems

For large and sparse saddle point linear systems, this paper gives further spectral properties of the primal-based penalty preconditioners introduced in [C.R. Dohrmann, R.B. Lehoucq, A primal-based penalty preconditioner for elliptic saddle point systems, SIAM J. Numer. Anal. 44 (2006) 270-282]. The regions containing the real and non-real eigenvalues of the preconditioned matrix are obtained. The model of the Stokes problem is supplemented to illustrate the theoretical results and to test the quality of the primal-based penalty preconditioner.     

Perturbation analysis of generalized saddle point systems

We discuss the perturbation analysis of generalized saddle point systems in this paper. We give the nonlinear perturbation bounds, then derive the condition numbers, and analyze the sensitivity of the computed solutions.     

A note on constraint preconditioners for nonsymmetric saddle point problems

A class of constraint preconditioners for solving two‐by‐two block linear equations with the (1,2)‐block being the transpose of the (2,1)‐block and the (2,2)‐block being zero was investigated in a recent paper of Cao (Numer. Math. 2006; 103 :47–61). In this short note, we extend his idea by allowing the (1,2)‐block to be not equal to the transpose of the (2,1)‐block. Results concerning the spectrum, the form of the eigenvectors and the convergence behaviour of a Krylov subspace method, such as GMRES are presented. Copyright © 2007 John Wiley & Sons, Ltd.     

A numerical study of optimized sparse preconditioners

Preconditioning strategies based on incomplete factorizations and polynomial approximations are studied through extensive numerical experiments. We are concerned with the question of the optimal rate of convergence that can be achieved for these classes of preconditioners.Our conclusion is that the well-known Modified Incomplete Cholesky factorization (MIC), cf. e.g., Gustafsson [20], and the polynomial preconditioning based on the Chebyshev polynomials, cf. Johnson, Micchelli and Paul [22], have optimal order of convergence as applied to matrix systems derived by discretization of the Poisson equation. Thus for the discrete two-dimensional Poisson equation withn unknowns,O(n ^1/4) andO(n ^1/2) seem to be the optimal rates of convergence for the Conjugate Gradient (CG) method using incomplete factorizations and polynomial preconditioners, respectively. The results obtained for polynomial preconditioners are in agreement with the basic theory of CG, which implies that such preconditioners can not lead to improvement of the asymptotic convergence rate.By optimizing the preconditioners with respect to certain criteria, we observe a reduction of the number of CG iterations, but the rates of convergence remain unchanged.Supported by The Norwegian Research Council for Science and the Humanities (NAVF) under grants no. 413.90/002 and 412.93/005.Supported by The Royal Norwegian Council for Scientific and Industrial Research (NTNF) through program no. STP.28402: Toolkits in industrial mathematics.     

A note on skewcirculant preconditioners for elliptic problems

In a recent paper Chan and Chan study the use of circulant preconditioners for the solution of elliptic problems. They prove that circulant preconditioners can be chosen so that the condition number of the preconditioned system can be reduced fromO(n ² ) toO(n). In addition, using the Fast Fourier Transform, the computation of the preconditioner is highly parallelizable. To obtain their result, Chan and Chan introduce a shift /p/n ² for some >0. The aim of this paper is to consider skewcirculant preconditioners, and to show that in this case the condition number ofO(n) can easily be shown without using the somewhat unsatisfactory shift /p/n ². Furthermore, our estimates are more precise.     

On parameterized block triangular preconditioners for generalized saddle point problems

In this paper, we discuss two classes of parameterized block triangular preconditioners for the generalized saddle point problems. These preconditioners generalize the common block diagonal and triangular preconditioners. We will give distributions of the eigenvalues of the preconditioned matrix and provide estimates for the interval containing the real eigenvalues. Numerical experiments of a model Stokes problem are presented.