Two‐level preconditioners for serendipity finite element matrices

In this paper an approach to construct algebraic multilevel preconditioners for serendipity finite element matrices is presented. Two‐level preconditioners constructed in the paper allow to obtain multilevel preconditioners in serendipity case using multilevel preconditioners for linear finite element matrices. Copyright © 2006 John Wiley & Sons, Ltd.     

Multilevel Preconditioners for Mixed Methods for Second Order Elliptic Problems

A new approach for constructing algebraic multilevel preconditioners for mixed finite element methods for second order elliptic problems with tensor coefficients on general geometry is proposed. The linear system arising from the mixed methods is first algebraically condensed to a symmetric, positive definite system for Lagrange multipliers, which corresponds to a linear system generated by standard nonconforming finite element methods. Algebraic multilevel preconditioners for this system are then constructed based on a triangulation of the domain into tetrahedral substructures. Explicit estimates of condition numbers and simple computational schemes are established for the constructed preconditioners. Finally, numerical results for the mixed finite element methods are presented to illustrate the present theory.     

Interior penalty preconditioners for mixed finite element approximations of elliptic problems

It is established that an interior penalty method applied to second-order elliptic problems gives rise to a local operator which is spectrally equivalent to the corresponding nonlocal operator arising from the mixed finite element method. This relation can be utilized in order to construct preconditioners for the discrete mixed system. As an example, a family of additive Schwarz preconditioners for these systems is constructed. Numerical examples which confirm the theoretical results are also presented.

     

Multilevel preconditioners for a quadrature Galerkin solution of a biharmonic problem

Efficient multilevel preconditioners are developed and analyzed for the quadrature finite element Galerkin approximation of the biharmonic Dirichlet problem. The quadrature scheme is formulated using the Bogner–Fox–Schmit rectangular element and the product two‐point Gaussian quadrature. The proposed additive and multiplicative preconditioners are uniformly spectrally equivalent to the operator of the quadrature scheme. The preconditioners are implemented by optimal algorithms, and they are used to accelerate convergence of the preconditioned conjugate gradient method. Numerical results are presented demonstrating efficiency of the preconditioners. © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2006     

Recursive two-levelILU preconditioner for nonsymmetric M-matrices

We develop in this paper some preconditioners for sparse non-symmetric M-matrices, which combine a recursive two-level blockILU factorization with multigrid method, we compare these preconditioners on matrices arising from discretized convection-diffusion equations using upwind finite difference schemes and multigrid orderings, some comparison theorems and experiment results are demonstrated.     

PPIFE Method with Non-Homogeneous Flux Jump Conditions and Its Efficient Numerical Solver for Elliptic Optimal Control Problems with Interfaces

In this paper, we design a partially penalized immersed finite element method for solving elliptic interface problems with non-homogeneous flux jump conditions. The method presented here has the same global degrees of freedom as classic immersed finite element method. The non-homogeneous flux jump conditions can be handled accurately by additional immersed finite element functions. Four numerical examples are provided to demonstrate the optimal convergence rates of the method in $L^{\infty}$, $L^{2}$ and $H^{1}$ norms. Furthermore, the method is combined with post-processing technique to solve elliptic optimal control problems with interfaces. To solve the resulting large-scale system, block diagonal preconditioners are introduced. These preconditioners can lead to fast convergence of the Krylov subspace methods such as GMRES and are independent of the mesh size. Four numerical examples are presented to illustrate the efficiency of the numerical schemes and preconditioners.     

Parallel block preconditioning based on SSOR and MILU

Two kinds of parallel preconditioners for the solution of large sparse linear systems which arise from the 2-D 5-point finite difference discretization of a convection-diffusion equation are introduced. The preconditioners are based on the SSOR or MILU preconditioners and can be implemented on parallel computers with distributed memories. One is the block preconditioner, in which the interface components of the coefficient matrix between blocks are ignored to attain parallelism in the forward-backward substitutions. The other is the modified block preconditioner, in which the block preconditioner is modified by taking the interface components into account. The effect of these preconditioners on the convergence of preconditioned iterative methods and timing results on the parallel computer (Cenju) are presented.     

Preconditioners for nonconforming discretizations

We prove an abstract norm equivalence for a two-level method, which allows us to reduce the construction of preconditioners for nonconforming finite element discretizations to known cases of conforming elements.

     

Preconditioned Iterative Methods for Scattered Data Interpolation

The scattered data interpolation problem in two space dimensions is formulated as a partial differential equation with interpolating side conditions. The system is discretized by the Morley finite element space. The focus of this paper is to study preconditioned iterative methods for the corresponding discrete systems. We introduce block diagonal preconditioners, where a multigrid operator is used for the differential equation part of the system, while we propose an operator constructed from thin plate radial basis functions for the equations corresponding to the interpolation conditions. The effect of the preconditioners are documented by numerical experiments.     

Preconditioners for higher order edge finite element discretizations of Maxwell's equations

In this paper,we are concerned with the fast solvers for higher order edge finite element discretizations of Maxwell's equations.We present the preconditioners for the first family and second family of higher order N′ed′elec element equations,respectively.By combining the stable decompositions of two kinds of edge finite element spaces with the abstract theory of auxiliary space preconditioning,we prove that the corresponding condition numbers of our preconditioners are uniformly bounded on quasi-uniform grids.We also present some numerical experiments to demonstrate the theoretical results.     

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.     

Analysis of substructuring preconditioners for mortar methods in an abstract framework

A class of preconditioners for the linear system arising from the discretization by the mortar method is studied. We focus on the substructuring approach already applied by Achdou et al. [Y. Achdou, Y. Maday, O. Widlund, Substructuring preconditioners for the mortar method in dimension two, SIAM J. Numer. Anal. 36 (1999) 551–580] to the mortar method for the case of order one finite elements. The estimate that we provide relies on abstract assumptions so our result holds for finite elements of any order, as well as for spaces of different kinds, e.g. wavelets.     

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

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

Two-level hierarchically preconditioned conjugate gradient methods for solving linear elasticity finite element equations

In this paper we study and compare some preconditioned conjugate gradient methods for solving large-scale higher-order finite element schemes approximating two- and three-dimensional linear elasticity boundary value problems. The preconditioners discussed in this paper are derived from hierarchical splitting of the finite element space first proposed by O. Axelsson and I. Gustafsson. We especially focus our attention to the implicit construction of preconditioning operators by means of some fixpoint iteration process including multigrid techniques. Many numerical experiments confirm the efficiency of these preconditioners in comparison with classical direct methods most frequently used in practice up to now.     

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     

Continuous preconditioners for the mixed Poisson problem

In this note, we show how to apply preconditioners designed for piecewise linear finite element discretizations of the Poisson problem as preconditioners for the mixed problem. Our preconditioner can be applied both to the original and to the reduced Schur complement problem. Combined with a suitable iterative method, the number of iterations required to solve the preconditioned system will have the same dependency on the mesh size as for the preconditioner applied to the Poisson problem. The presented theory is demonstrated by numerical examples.     

NONNESTED MULTILEVEL PRECONDITIONING METHODS WITH SIMPLE AND IDENTICAL COARSE MESH CORRECTION SPACES

1　ＩｎｔｒｏｄｕｃｔｉｏｎＭｕｌｔｉｌｅｖｅｌｍｅｔｈｏｄｓｈａｖｅｂｅｃｏｍｅｓｏｍｅｏｆｔｈｅｍｏｓｔｐｏｐｕｌａｒｍｅｔｈｏｄｓｆｏｒｓｏｌｖｉｎｇｌａｒｇｅｓｙｓｔｅｍｏｆｌｉｎｅａｒｅｑｕａｔｉｏｎｓｒｅｓｕｌｔｉｎｇｆｒｏｍｔｈｅｆｉｎｉｔｅｅｌｅｍｅｎｔｄｉｓｃｒｅｔｉｚａｔｉｏｎｏｆｐａｒｔｉａｌｄｉｆｆｅｒｅｎｔｉａｌｅｑｕａｔｉｏｎｓ.ＴｈｅｐｉｏｎｅｅｒｗｏｒｋｏｆｍｕｌｔｉｌｅｖｅｌｍｅｔｈｏｄｓｉｓｔｈｅＹｓｅｒｅｎｔａｎｔ’ｓＨｉｅｒａｒｃｈｉｃａｌｂａｓｉｓｍｅｔｈ…     

Circulant preconditioners for a kind of spatial fractional diffusion equations

Numerical Algorithms - In this paper, circulant preconditioners are studied for discretized matrices arising from finite difference schemes for a kind of spatial fractional diffusion equations. The...     

Preconditioning a class of fourth order problems by operator splitting

We develop preconditioners for systems arising from finite element discretizations of parabolic problems which are fourth order in space. We consider boundary conditions which yield a natural splitting of the discretized fourth order operator into two (discrete) linear second order elliptic operators, and exploit this property in designing the preconditioners. The underlying idea is that efficient methods and software to solve second order problems with optimal computational effort are widely available. We propose symmetric and non-symmetric preconditioners, along with theory and numerical experiments. They both document crucial properties of the preconditioners as well as their practical performance. It is important to note that we neither need H ^s -regularity, s > 1, of the continuous problem nor quasi-uniform grids.     

Domain decomposition for multiscale PDEs

We consider additive Schwarz domain decomposition preconditioners for piecewise linear finite element approximations of elliptic PDEs with highly variable coefficients. In contrast to standard analyses, we do not assume that the coefficients can be resolved by a coarse mesh. This situation arises often in practice, for example in the computation of flows in heterogeneous porous media, in both the deterministic and (Monte–Carlo simulated) stochastic cases. We consider preconditioners which combine local solves on general overlapping subdomains together with a global solve on a general coarse space of functions on a coarse grid. We perform a new analysis of the preconditioned matrix, which shows rather explicitly how its condition number depends on the variable coefficient in the PDE as well as on the coarse mesh and overlap parameters. The classical estimates for this preconditioner with linear coarsening guarantee good conditioning only when the coefficient varies mildly inside the coarse grid elements. By contrast, our new results show that, with a good choice of subdomains and coarse space basis functions, the preconditioner can still be robust even for large coefficient variation inside domains, when the classical method fails to be robust. In particular our estimates prove very precisely the previously made empirical observation that the use of low-energy coarse spaces can lead to robust preconditioners. We go on to consider coarse spaces constructed from multiscale finite elements and prove that preconditioners using this type of coarsening lead to robust preconditioners for a variety of binary (i.e., two-scale) media model problems. Moreover numerical experiments show that the new preconditioner has greatly improved performance over standard preconditioners even in the random coefficient case. We show also how the analysis extends in a straightforward way to multiplicative versions of the Schwarz method. We would like to thank Bill McLean for very useful discussions concerning this work. We would also like to thank Maksymilian Dryja for helping us to improve the result in Theorem 4.3.