A semi-circulant preconditioner for the convection-diffusion equation

In this paper we define and analyze a semi-circulant preconditioner for the convection-diffusion equation. We derive analytical formulas for the eigenvalues and the eigenvectors of the preconditioned system of equations. We show that for mesh Péclet numbers less than 2, the rate of convergence depends only on the mesh Péclet number and the direction of the convective field and not on the spatial grid ratio or the number of unknowns. Received February 20, 1997 / Revised version received November 19, 1997     

A chordal preconditioner for large-scale optimization

We propose an automatic preconditioning scheme for large sparse numerical optimization. The strategy is based on an examination of the sparsity pattern of the Hessian matrix: using a graph-theoretic heuristic, a block-diagonal approximation to the Hessian matrix is induced. The blocks are submatrices of the Hessian matrix; furthermore, each block is chordal. That is, under a positive definiteness assumption, the Cholesky factorization can be applied to each block without creating any new nonzeros (fill). Therefore the preconditioner is space efficient. We conduct a number of numerical experiments to determine the effectiveness of the preconditioner in the context of a linear conjugate-gradient algorithm for optimization.     

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.

     

A splitting preconditioner for saddle point problems

For large sparse systems of linear equations iterative techniques are attractive. In this paper, we study a splitting method for an important class of symmetric and indefinite system. Theoretical analyses show that this method converges to the unique solution of the system of linear equations for all t>0 (t is the parameter). Moreover, all the eigenvalues of the iteration matrix are real and nonnegative and the spectral radius of the iteration matrix is decreasing with respect to the parameter t. Besides, a preconditioning strategy based on the splitting of the symmetric and indefinite coefficient matrices is proposed. The eigensolution of the preconditioned matrix is described and an upper bound of the degree of the minimal polynomials for the preconditioned matrix is obtained. Numerical experiments of a model Stokes problem and a least‐squares problem with linear constraints presented to illustrate the effectiveness of the method. Copyright © 2011 John Wiley & Sons, Ltd.     

A wirebasket preconditioner for the mortar boundary element method

We present and analyze a preconditioner of the additive Schwarz type for the mortar boundary element method. As a basic splitting, on each subdomain we separate the degrees of freedom related to its boundary from the inner degrees of freedom. The corresponding wirebasket-type space decomposition is stable up to logarithmic terms. For the blocks that correspond to the inner degrees of freedom standard preconditioners for the hypersingular integral operator on open boundaries can be used. For the boundary and interface parts as well as the Lagrangian multiplier space, simple diagonal preconditioners are optimal. Our technique applies to quasi-uniform and non-uniform meshes of shape-regular elements. Numerical experiments on triangular and quadrilateral meshes confirm theoretical bounds for condition and MINRES iteration numbers.     

A preconditioner for the FETI-DP method for mortar-type Crouzeix-Raviart element discretization

In this paper, we consider mortar-type Crouzeix-Raviart element discretizations for second order elliptic problems with discontinuous coefficients. A preconditioner for the FETI-DP method is proposed. We prove that the condition number of the preconditioned operator is bounded by (1 + log(H/h))², where H and h are mesh sizes. Finally, numerical tests are presented to verify the theoretical results.     

A domain decomposition preconditioner for hermite collocation problems

We propose a preconditioning method for linear systems of equations arising from piecewise Hermite bicubic collocation applied to two‐dimensional elliptic PDEs with mixed boundary conditions. We construct an efficient, parallel preconditioner for the GMRES method. The main contribution of the article is a novel interface preconditioner derived in the framework of substructuring and employing a local Hermite collocation discretization for the interface subproblems based on a hybrid fine‐coarse mesh. Interface equations based on this mesh depend only weakly on unknowns associated with subdomains. The effectiveness of the proposed method is highlighted by numerical experiments that cover a variety of problems. © 2003 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 19: 135–151, 2003     

A two-level additive Schwarz preconditioner for the stationary Stokes equations

We consider the stationary Stokes equations on a polygonal domain whose boundary has more than one component, i.e., flow with obstacles. A two-level additive Schwarz preconditioner is developed for the divergence-free nonconforming P1 finite element. The condition number of the preconditioned system is shown to be bounded independent of mesh sizes and the number of subdomains in the case of generous overlap.This work was supported in part by the National Science Foundation under Grant Nos. DMS-92-09332 and DMS-94-96275.     

A multigrid preconditioner for an adaptive Black-Scholes solver

This paper is concerned with the efficient solution of the linear systems of equations that arise from an adaptive space-implicit time discretisation of the Black-Scholes equation. These nonsymmetric systems are very large and sparse, so an iterative method will usually be the method of choice. However, such a method may require a large number of iterations to converge, particularly when the timestep used is large (which is often the case towards the end of a simulation which uses adaptive timestepping). An appropriate preconditioner is therefore desirable. In this paper we show that a very simple multigrid algorithm with standard components works well as a preconditioner for these problems. We analyse the eigenvalue spectrum of the multigrid iteration matrix for uniform grid problems and illustrate the method’s efficiency in practice by considering the results of numerical experiments on both uniform grids and those which use adaptivity in space.     

A new wavelet preconditioner for finite difference operators

This paper is devoted to the construction of a new multilevel preconditioner for operators discretized using finite differences. It uses the basic ingredients of a multiscale construction of the inverse of a variable coefficient elliptic differential operator derived by Tchamitchian [19]. It can be implemented fast and can therefore be easily incorporated in finite difference solvers for elliptic PDEs. Theoretical results, as well as numerical tests and implementation technical details are presented. This work has been partially supported by TMR Research Network Contract FMRX-CT98-0184.AMS subject classification 00A69, 65T60, 65Y99, 15A12     

A hierarchical basis preconditioner for the biharmonic equation on the sphere

^** Email: jan.maes{at}cs.kuleuven.be In this paper, we propose a natural way to extend a bivariatePowell–Sabin (PS) B-spline basis on a planar polygonaldomain to a PS B-spline basis defined on a subset of the unitsphere in [graphic: see PDF] . The spherical basis inherits many properties of the bivariatebasis such as local support, the partition of unity propertyand stability. This allows us to construct a C¹ continuous hierarchicalbasis on the sphere that is suitable for preconditioning fourth-orderelliptic problems on the sphere. We show that the stiffnessmatrix relative to this hierarchical basis has a logarithmicallygrowing condition number, which is a suboptimal result comparedto standard multigrid methods. Nevertheless, this is a hugeimprovement over solving the discretized system without preconditioning,and its extreme simplicity contributes to its attractiveness.Furthermore, we briefly describe a way to stabilize the hierarchicalbasis with the aid of the lifting scheme. This yields a waveletbasis on the sphere for which we find a uniformly well-conditionedand (quasi-) sparse stiffness matrix.     

A reduced Hessian method for constrained optimization

Reduced Hessian methods have been shown to be successful for equality constrained problems. However there are few results on reduced Hessian methods for general constrained problems. In this paper we propose a method for general constrained problems, based on Byrd and Schnabel's basis-independent algorithm. It can be regarded as a smooth extension of the standard reduced Hessian Method.Research supported in part by NSF, AFORS and ONR through NSF grant DMS-8920550.     

A two-level additive Schwarz preconditioner for nonconforming plate elements

Summary. A two-level additive Schwarz preconditioner is developed for the systems resulting from the discretizations of the plate bending problem by the Morley finite element, the Fraeijs de Veubeke finite element, the Zienkiewicz finite element and the Adini finite element. The condition numbers of the preconditioned systems are shown to be bounded independent of mesh sizes and the number of subdomains in the case of a generous overlap. Received February 1, 1994 / Revised version received October 24, 1994     

A conforming auxiliary space preconditioner for the mass conserving stress-yielding method

We are studying the efficient solution of the system of linear equations stemming from the mass conserving stress-yielding (MCS) discretization of the Stokes equations. We perform static condensation to arrive at a system for the pressure and velocity unknowns. An auxiliary space preconditioner for the positive definite velocity block makes use of efficient and scalable solvers for conforming Finite Element spaces of low order and is analyzed with emphasis placed on robustness in the polynomial degree of the discretization. Numerical experiments demonstrate the potential of this approach and the efficiency of the implementation.     

Sweeping preconditioner for the Helmholtz equation: Hierarchical matrix representation

The paper introduces the sweeping preconditioner, which is highly efficient for iterative solutions of the variable‐coefficient Helmholtz equation including very‐high‐frequency problems. The first central idea of this novel approach is to construct an approximate factorization of the discretized Helmholtz equation by sweeping the domain layer by layer, starting from an absorbing layer or boundary condition. Given this specific order of factorization, the second central idea is to represent the intermediate matrices in the hierarchical matrix framework. In two dimensions, both the construction and the application of the preconditioners are of linear complexity. The generalized minimal residual method (GMRES) solver with the resulting preconditioner converges in an amazingly small number of iterations, which is essentially independent of the number of unknowns. This approach is also extended to the three‐dimensional case with some success. Numerical results are provided in both two and three dimensions to demonstrate the efficiency of this new approach. © 2011 Wiley Periodicals, Inc.     

A nearly optimal preconditioner for the Navier–Stokes equations

We present a preconditioner for the linearized Navier–Stokes equations which is based on the combination of a fast transform approximation of an advection diffusion problem together with the recently introduced ‘BFBT^T’ preconditioner of Elman (SIAM Journal of Scientific Computing, 1999; 20 :1299–1316). The resulting preconditioner when combined with an appropriate Krylov subspace iteration method yields the solution in a number of iterations which appears to be independent of the Reynolds number provided a mesh Péclet number restriction holds, and depends only mildly on the mesh size. The preconditioner is particularly appropriate for problems involving a primary flow direction. Copyright © 2001 John Wiley & Sons, Ltd.     

A least-squares preconditioner for radial basis functions collocation methods

Although meshless radial basis function (RBF) methods applied to partial differential equations (PDEs) are not only simple to implement and enjoy exponential convergence rates as compared to standard mesh-based schemes, the system of equations required to find the expansion coefficients are typically badly conditioned and expensive using the global Gaussian elimination (G-GE) method requiring flops. We present a simple preconditioning scheme that is based upon constructing least-squares approximate cardinal basis functions (ACBFs) from linear combinations of the RBF-PDE matrix elements. The ACBFs transforms a badly conditioned linear system into one that is very well conditioned, allowing us to solve for the expansion coefficients iteratively so we can reconstruct the unknown solution everywhere on the domain. Our preconditioner requires flops to set up, and storage locations where m is a user define parameter of order of 10. For the 2D MQ-RBF with the shape parameter , the number of iterations required for convergence is of order of 10 for large values of N, making this a very attractive approach computationally. As the shape parameter increases, our preconditioner will eventually be affected by the ill conditioning and round-off errors, and thus becomes less effective. We tested our preconditioners on increasingly larger c and N. A more stable construction scheme is available with a higher set up cost.     

A new relaxed HSS preconditioner for saddle point problems

We present a preconditioner for saddle point problems. The proposed preconditioner is extracted from a stationary iterative method which is convergent under a mild condition. Some properties of the preconditioner as well as the eigenvalues distribution of the preconditioned matrix are presented. The preconditioned system is solved by a Krylov subspace method like restarted GMRES. Finally, some numerical experiments on test problems arisen from finite element discretization of the Stokes problem are given to show the effectiveness of the preconditioner.