BCCB preconditioners for systems of BVM‐based numerical integrators

Boundary value methods (BVMs) for ordinary differential equations require the solution of non‐symmetric, large and sparse linear systems. In this paper, these systems are solved by using the generalized minimal residual (GMRES) method. A block‐circulant preconditioner with circulant blocks (BCCB preconditioner) is proposed to speed up the convergence rate of the GMRES method. The BCCB preconditioner is shown to be invertible when the BVM is A_k1,k2‐stable. The spectrum of the preconditioned matrix is clustered and therefore, the preconditioned GMRES method converges fast. Moreover, the operation cost in each iteration of the preconditioned GMRES method by using our BCCB preconditioner is less than that required by using block‐circulant preconditioners proposed earlier. In numerical experiments, we compare the number of iterations of various preconditioners. Copyright © 2003 John Wiley & Sons, Ltd.     

AMLI preconditioner for the p‐version of the FEM

From the literature it is known that the conjugate gradient method with domain decomposition preconditioners is one of the most efficient methods for solving systems of linear algebraic equations resulting from p‐version finite element discretizations of elliptic boundary value problems. One ingredient of such a preconditioner is a preconditioner related to the Dirichlet problems. In the case of Poisson's equation, we present a preconditioner for the Dirichlet problems which can be interpreted as the stiffness matrix K_h,k resulting from the h‐version finite element discretization of a special degenerated problem. We construct an AMLI preconditioner C_h,k for the matrix K_h,k and show that the condition number of C K_h,k is independent of the discretization parameter. This proof is based on the strengthened Cauchy inequality. The theoretical result is confirmed by numerical examples. Copyright © 2003 John Wiley & Sons, Ltd.     

Robust multigrid preconditioners for the high‐contrast biharmonic plate equation

We study the high‐contrast biharmonic plate equation with Hsieh–Clough–Tocher discretization. We construct a preconditioner that is robust with respect to contrast size and mesh size simultaneously based on the preconditioner proposed by Aksoylu et al. (Comput. Vis. Sci. 2008; 11 :319–331). By extending the devised singular perturbation analysis from linear finite element discretization to the above discretization, we prove and numerically demonstrate the robustness of the preconditioner. Therefore, we accomplish a desirable preconditioning design goal by using the same family of preconditioners to solve the elliptic family of PDEs with varying discretizations. We also present a strategy on how to generalize the proposed preconditioner to cover high‐contrast elliptic PDEs of order 2k, k>2. Moreover, we prove a fundamental qualitative property of the solution to the high‐contrast biharmonic plate equation. Namely, the solution over the highly bending island becomes a linear polynomial asymptotically. The effectiveness of our preconditioner is largely due to the integration of this qualitative understanding of the underlying PDE into its construction. Copyright © 2010 John Wiley & Sons, Ltd.     

On the preconditioning of matrices with skew-symmetric splittings

The rates of convergence of iterative methods with standard preconditioning techniques usually degrade when the skew-symmetric part S of the matrix is relatively large. In this paper, we address the issue of preconditioning matrices with such large skew-symmetric parts. The main idea of the preconditioner is to split the matrix into its symmetric and skew-symmetric parts and to invert the (shifted) skew-symmetric matrix. Successful use of the method requires the solution of a linear system with matrix I+S. An efficient method is developed using the normal equations, preconditioned by an incomplete orthogonal factorization.Numerical experiments on various systems arising in physics show that the reduction in terms of iteration count compensates for the additional work per iteration when compared to standard preconditioners.     

A comparison of abstract versions of deflation,balancing and additive coarse grid correction preconditioners

In this paper we consider various preconditioners for the conjugate gradient (CG) method to solve large linear systems of equations with symmetric positive definite system matrix. We continue the comparison between abstract versions of the deflation, balancing and additive coarse grid correction preconditioning techniques started in (SIAM J. Numer. Anal. 2004; 42 :1631–1647; SIAM J. Sci. Comput. 2006; 27 :1742–1759). There the deflation method is compared with the abstract additive coarse grid correction preconditioner and the abstract balancing preconditioner. Here, we close the triangle between these three methods. First of all, we show that a theoretical comparison of the condition numbers of the abstract additive coarse grid correction and the condition number of the system preconditioned by the abstract balancing preconditioner is not possible. We present a counter example, for which the condition number of the abstract additive coarse grid correction preconditioned system is below the condition number of the system preconditioned with the abstract balancing preconditioner. However, if the CG method is preconditioned by the abstract balancing preconditioner and is started with a special starting vector, the asymptotic convergence behavior of the CG method can be described by the so‐called effective condition number with respect to the starting vector. We prove that this effective condition number of the system preconditioned by the abstract balancing preconditioner is less than or equal to the condition number of the system preconditioned by the abstract additive coarse grid correction method. We also provide a short proof of the relationship between the effective condition number and the convergence of CG. Moreover, we compare the A‐norm of the errors of the iterates given by the different preconditioners and establish the orthogonal invariants of all three types of preconditioners. Copyright © 2008 John Wiley & Sons, Ltd.     

Multiple nontrivial solutions for resonant Neumann problems

We consider semilinear second order elliptic Neumann problems, which are resonant both at infinity (with respect to an eigenvalue λ_k, k ≥ 1) and at zero (with respect to the principal eigenvalue λ₀ = 0). Using techniques from Morse theory, combined with variational methods, we are able to show that the problem has at least four nontrivial smooth solutions (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Repeated Red-Black ordering: a new approach

Hereafter, we describe and analyze, from both a theoretical and a numerical point of view, an iterative method for efficiently solving symmetric elliptic problems with possibly discontinuous coefficients. In the following, we use the Preconditioned Conjugate Gradient method to solve the symmetric positive definite linear systems which arise from the finite element discretization of the problems. We focus our interest on sparse and efficient preconditioners. In order to define the preconditioners, we perform two steps: first we reorder the unknowns and then we carry out a (modified) incomplete factorization of the original matrix. We study numerically and theoretically two preconditioners, the second preconditioner corresponding to the one investigated by Brand and Heinemann [2]. We prove convergence results about the Poisson equation with either Dirichlet or periodic boundary conditions. For a meshsizeh, Brand proved that the condition number of the preconditioned system is bounded byO(h ^–1/2) for Dirichlet boundary conditions. By slightly modifying the preconditioning process, we prove that the condition number is bounded byO(h ^–1/3).     

Fast Fourier Transform Solvers and Preconditioners for Quadratic Spline Collocation

Quadratic Spline Collocation (QSC) methods of optimal order of convergence have been recently developed for the solution of elliptic Partial Differential Equations (PDEs). In this paper, linear solvers based on Fast Fourier Transforms (FFT)are developed for the solution of the QSC equations. The complexity of the FFT solvers is O(N ² log N), where N is the gridsize in one dimension. These direct solvers can handle PDEs with coefficients in one variable or constant, and Dirichlet, Neumann, alternating Dirichlet-Neumann or periodic boundary conditions, along at least one direction of a rectangular domain. General variable coefficient PDEs are handled by preconditioned iterative solvers. The preconditioner is the QSC matrix arising from a constant coefficient PDE. The convergence analysis of the preconditioner is presented. It is shown that, under certain conditions, the convergence rate is independent of the gridsize. The preconditioner is solved by FFT techniques, and integrated with one-step or acceleration methods, giving rise to asymptotically almost optimal linear solvers, with complexity O(N ² log N). Numerical experiments verify the effectiveness of the solvers and preconditioners, even on problems more general than the analysis assumes. The development and analysis of FFT solvers and preconditioners is extended to QSC equations corresponding to systems of elliptic PDEs.     

Preconditioning of elliptic problems by approximation in the transform domain

Preconditioned conjugate gradient method is applied for solving linear systemsAx=b where the matrixA is the discretization matrix of second-order elliptic operators. In this paper, we consider the construction of the trnasform based preconditioner from the viewpoint of image compression. Given a smooth image, a major portion of the energy is concentrated in the low frequency regions after image transformation. We can view the matrixA as an image and construct the transform based preconditioner by using the low frequency components of the transformed matrix. It is our hope that the smooth coefficients of the given elliptic operator can be approximated well by the low-rank matrix. Numerical results are reported to show the effectiveness of the preconditioning strategy. Some theoretical results about the properties of our proposed preconditioners and the condition number of the preconditioned matrices are discussed.     

On the two classes of high‐order convergent methods of approximate inverse preconditioners for solving linear systems

Two classes of methods for approximate matrix inversion with convergence orders p =3?2^k +1 (Class 1) and p =5?2^k ?1 (Class 2), k ≥1 an integer, are given based on matrix multiplication and matrix addition. These methods perform less number of matrix multiplications compared to the known hyperpower method or p th‐order method for the same orders and can be used to construct approximate inverse preconditioners for solving linear systems. Convergence, error, and stability analyses of the proposed classes of methods are provided. Theoretical results are justified with numerical results obtained by using the proposed methods of orders p =7,13 from Class 1 and the methods with orders p =9,19 from Class 2 to obtain polynomial preconditioners for preconditioning the biconjugate gradient (BICG) method for solving well‐ and ill‐posed problems. From the literature, methods with orders p =8,16 belonging to a family developed by the effective representation of the p th‐order method for orders p =2^k , k is integer k ≥1, and other recently given high‐order convergent methods of orders p =6,7,8,12 for approximate matrix inversion are also used to construct polynomial preconditioners for preconditioning the BICG method to solve the considered problems. Numerical comparisons are given to show the applicability, stability, and computational complexity of the proposed methods by paying attention to the asymptotic convergence rates. It is shown that the BICG method converges very quickly when applied to solve the preconditioned system. Therefore, the cost of constructing these preconditioners is amortized if the preconditioner is to be reused over several systems of same coefficient matrix with different right sides.     

Two new modified Gauss–Seidel methods for linear system with -matrices

In 2002, H. Kotakemori et al. proposed the modified Gauss–Seidel (MGS) method for solving the linear system with the preconditioner [H. Kotakemori, K. Harada, M. Morimoto, H. Niki, A comparison theorem for the iterative method with the preconditioner () J. Comput. Appl. Math. 145 (2002) 373–378]. Since this preconditioner is constructed by only the largest element on each row of the upper triangular part of the coefficient matrix, the preconditioning effect is not observed on the nth row. In the present paper, to deal with this drawback, we propose two new preconditioners. The convergence and comparison theorems of the modified Gauss–Seidel methods with these two preconditioners for solving the linear system are established. The convergence rates of the new proposed preconditioned methods are compared. In addition, numerical experiments are used to show the effectiveness of the new MGS methods.     

Generalization of Strang's Preconditioner with Applications to Toeplitz Least Squares Problems

In this paper, we propose a method to generalize Strang's circulant preconditioner for arbitrary n-by-n matrices A_n. The th column of our circulant preconditioner Sn is equal to the th column of the given matrix A_n. Thus if A_n is a square Toeplitz matrix, then Sn is just the Strang circulant preconditioner. When Sn is not Hermitian, our circulant preconditioner can be defined as . This construction is similar to the forward-backward projection method used in constructing preconditioners for tomographic inversion problems in medical imaging. We show that if the matrix A_n has decaying coefficients away from the main diagonal, then is a good preconditioner for An. Comparisons of our preconditioner with other circulant-based preconditioners are carried out for some 1-D Toeplitz least squares problems: min ∥ b - Ax∥₂. Preliminary numerical results show that our preconditioner performs quite well, in comparison to other circulant preconditioners. Promising test results are also reported for a 2-D deconvolution problem arising in ground-based atmospheric imaging.     

On additive Schwarz preconditioners for sparse grid discretizations

Summary Based on the framework of subspace splitting and the additive Schwarz scheme, we give bounds for the condition number of multilevel preconditioners for sparse grid discretizations of elliptic model problems. For a BXP-like preconditioner we derive an estimate of the optimal orderO(1) and for a HB-like variant we obtain an estimate of the orderO(k ² ·2 ^k/2 ), wherek denotes the number of levels employed. Furthermore, we confirm these results by numerically computed condition numbers.     

A New Iteration and Preconditioning Method for Elliptic PDE-Constrained Optimization Problems

Optimal control problems constrained by a partial differential equation (PDE) arise in various important applications, such as in engineering and natural sciences. Normally the problems are of very large scale, so iterative solution methods must be used. Thereby the choice of an iteration method in conjunction with an efficient preconditioner is essential. In this paper, we consider a new iteration method and a new preconditioning technique for an elliptic PDE-constrained optimal control problem with a distributed control function. Some earlier used iteration methods and preconditioners in the literature are compared, both analytically and numerically with the new iteration method and the preconditioner.     

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.     

An algebraic preconditioning method for M‐matrices: linear versus non‐linear multilevel iteration

In a recent work, the author introduced a robust multilevel incomplete factorization algorithm using spanning trees of matrix graphs (Proceedings of the 1999 International Conference on Preconditioning Techniques for Large Sparse Matrix Problems in Industrial Applications, Hubert H. Humphrey Center, University of Minnesota, 1999, 251–257). Based on this idea linear and non‐linear algebraic multilevel iteration (AMLI) methods are investigated in the present paper. In both cases, the preconditioner is constructed recursively from the coarsest to finer and finer levels. The considered W‐cycles only need diagonal solvers on all levels and additionally evaluate a second‐degree matrix polynomial (linear case), or, perform ν inner GCG‐type iterations (non‐linear case) on every other level. This involves the same type of preconditioner for the corresponding Schur complement. The non‐linear variant has the additional benefit of being free from any method parameters to be estimated. Based on the same type of approximation property similar convergence rates are obtained for linear and non‐linear AMLI, even for a very small number ν of inner iterations, e.g. ν =2,3. The presented methods are robust with respect to anisotropy and discontinuities in the coefficients of the PDEs and can also be applied to unstructured‐grid problems. Copyright © 2002 John Wiley & Sons, Ltd.     

Analyzing the convergence factor of residual inverse iteration

We will establish here a formula for the convergence factor of the method called residual inverse iteration, which is a method for nonlinear eigenvalue problems and a generalization of the well-known inverse iteration. The formula for the convergence factor is explicit and involves quantities associated with the eigenvalue to which the iteration converges, in particular the eigenvalue and eigenvector. Residual inverse iteration allows for some freedom in the choice of a vector w _k and we can use the formula for the convergence factor to analyze how it depends on the choice of w _k . We also use the formula to illustrate the convergence when the shift is close to the eigenvalue. Finally, we explain the slow convergence for double eigenvalues by showing that under generic conditions, the convergence factor is one, unless the eigenvalue is semisimple. If the eigenvalue is semisimple, it turns out that we can expect convergence similar to the simple case.     

Fast Construction of Optimal Circulant Preconditioners for Matrices from the Fast Dense Matrix Method

In this paper, we consider solving non-convolution type integral equations by the preconditioned conjugate gradient method. The fast dense matrix method is a fast multiplication scheme that provides a dense discretization matrix A approximating a given integral equation. The dense matrix A can be constructed in O(n) operations and requires only O(n) storage where n is the size of the matrix. Moreover, the matrix-vector multiplication A xcan be done in O(n log n) operations. Thus if the conjugate gradient method is used to solve the discretized system, the cost per iteration is O(n log n) operations. However, for some integral equations, such as the Fredholm integral equations of the first kind, the system will be ill-conditioned and therefore the convergence rate of the method will be slow. In these cases, preconditioning is required to speed up the convergence rate of the method. A good choice of preconditioner is the optimal circulant preconditioner which is the minimizer of C – A _F in Frobenius norm over all circulant matrices C. It can be obtained by taking arithmetic averages of all the entries of A and therefore the cost of constructing the preconditioner is of O(n ²) operations for general dense matrices. In this paper, we develop an O(n log n) method of constructing the preconditioner for dense matrices A obtained from the fast dense matrix method. Application of these ideas to boundary integral equations from potential theory will be given. These equations are ill-conditioned whereas their optimal circulant preconditioned equations will be well-conditioned. The accuracy of the approximation A, the fast construction of the preconditioner and the fast convergence of the preconditioned systems will be illustrated by numerical examples.     

On parallel solution of linear elasticity problems. Part II: Methods and some computer experiments

This is the second part of a trilogy on parallel solution of the linear elasticity problem. We consider the plain case of the problem with isotropic material, including discontinuous coefficients, and with homogeneous Dirichlet boundary condition. The discretized problem is solved by the preconditioned conjugate gradient (pcg) method. In the first part of the trilogy block‐diagonal preconditioners based on the separate displacement component part of the elasticity equations were analysed. The preconditioning systems were solved by the pcg‐method, i.e. inner iterations were performed. As preconditioner, we used modified incomplete factorization MIC(0), where possibly the element matrices were modified in order to give M‐matrices, i.e. in order to guarantee the existence of the MIC(0) factorization. In the present paper, the second part, full block incomplete factorization preconditioners are presented and analysed. In order to avoid inner/outer iterations we also study a variant of the block‐diagonal method and of the full block method, where the matrices of the inner systems are just replaced by their MIC(0)‐factors. A comparison is made between the various methods with respect to rate of convergence and work per unknown. The fastest methods are implemented by message passing utilizing the MPI system. In the third part of the trilogy, we will focus on the use of higher‐order finite elements. Copyright © 2002 John Wiley & Sons, Ltd.     

Parallel preconditioners for large scale partial difference equation systems

We propose a new preconditioner DASP (discrete approximate spectral preconditioner), based on the existing well-known preconditioners and our computational experience. Parallel preconditioning strategies for large scale partial difference equation systems arising from partial differential equations are investigated. Numerical results are given to show the efficiency and effectiveness of the new preconditioners for both model problems and real applications in petroleum reservoir simulation.