A domain decomposition discretization of parabolic problems

In recent years, domain decomposition methods have attracted much attention due to their successful application to many elliptic and parabolic problems. Domain decomposition methods treat problems based on a domain substructuring, which is attractive for parallel computation, due to the independence among the subdomains. In principle, domain decomposition methods may be applied to the system resulting from a standard discretization of the parabolic problems or, directly, be carried out through a discretization of parabolic problems. In this paper, a direct domain decomposition method is introduced to discretize the parabolic problems. The stability and convergence of this algorithm are analyzed. This work was supported in part by Polish Sciences Foundation under grant 2P03A00524. This work was supported in part by the US Department of Energy under Contracts DE-FG02-92ER25127 and by the Director, Office of Science, Advanced Scientific Computing Research, U.S. Department of Energy under contract DE-AC02-05CH11231.     

Multilevel Schwarz methods for elliptic problems with discontinuous coefficients in three dimensions

Summary. Multilevel Schwarz methods are developed for a conforming finite element approximation of second order elliptic problems. We focus on problems in three dimensions with possibly large jumps in the coefficients across the interface separating the subregions. We establish a condition number estimate for the iterative operator, which is independent of the coefficients, and grows at most as the square of the number of levels. We also characterize a class of distributions of the coefficients, called quasi-monotone, for which the weighted -projection is stable and for which we can use the standard piecewise linear functions as a coarse space. In this case, we obtain optimal methods, i.e. bounds which are independent of the number of levels and subregions. We also design and analyze multilevel methods with new coarse spaces given by simple explicit formulas. We consider nonuniform meshes and conclude by an analysis of multilevel iterative substructuring methods. Received April 6, 1994 / Revised version received December 7, 1994     

A cascadic multigrid algorithm for semilinear elliptic problems

Summary. We propose a cascadic multigrid algorithm for a semilinear elliptic problem. The nonlinear equations arising from linear finite element discretizations are solved by Newton's method. Given an approximate solution on the coarsest grid on each finer grid we perform exactly one Newton step taking the approximate solution from the previous grid as initial guess. The Newton systems are solved iteratively by an appropriate smoothing method. We prove that the algorithm yields an approximate solution within the discretization error on the finest grid provided that the start approximation is sufficiently accurate and that the initial grid size is sufficiently small. Moreover, we show that the method has multigrid complexity. Received February 12, 1998 / Revised version received July 22, 1999 / Published online June 8, 2000     

Convergence rate estimate for a domain decomposition method

Summary We provide a convergence rate analysis for a variant of the domain decomposition method introduced by Gropp and Keyes for solving the algebraic equations that arise from finite element discretization of nonsymmetric and indefinite elliptic problems with Dirichlet boundary conditions in ². We show that the convergence rate of the preconditioned GMRES method is nearly optimal in the sense that the rate of convergence depends only logarithmically on the mesh size and the number of substructures, if the global coarse mesh is fine enough.This author was supported by the National Science Foundation under contract numbers DCR-8521451 and ECS-8957475, by the IBM Corporation, and by the 3M Company, while in residence at Yale UniversityThis author was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy under Contract W-31-109-Eng-38This author was supported by the National Science Foundation under contract number ECS-8957475, by the IBM Corporation, and by the 3M Company     

Multilevel iterative methods for mixed finite element discretizations of elliptic problems

Summary For solving second order elliptic problems discretized on a sequence of nested mixed finite element spaces nearly optimal iterative methods are proposed. The methods are within the general framework of the product (multiplicative) scheme for operators in a Hilbert space, proposed recently by Bramble, Pasciak, Wang, and Xu [5,6,26,27] and make use of certain multilevel decomposition of the corresponding spaces for the flux variable.     

Local refinement techniques for elliptic problems on cell-centered grids

Summary Algebraic multilevel analogues of the BEPS preconditioner designed for solving discrete elliptic problems on grids with local refinement are formulated, and bounds on their relative condition numbers, with respect to the composite-grid matrix, are derived. TheV-cycle and, more generally,v-foldV-cycle multilevel BEPS preconditioners are presented and studied. It is proved that for 2-D problems theV-cycle multilevel BEPS is almost optimal, whereas thev-foldV-cycle algebraic multilevel BEPS is optimal under a mild restriction on the composite cell-centered grid. For thev-fold multilevel BEPS, the variational relation between the finite difference matrix and the corresponding matrix on the next-coarser level is not necessarily required. Since they are purely algebraically derived, thev-fold (v>1) multilevel BEPS preconditioners perform without any restrictionson the shape of subregions, unless the refinement is too fast. For theV-cycle BEPS preconditioner (2-D problem), a variational relation between the matrices on two consecutive grids is required, but there is no restriction on the method of refinement on the shape, or on the size of the subdomains.     

Additive Schwarz methods for the Crouzeix-Raviart mortar finite element for elliptic problems with discontinuous coefficients

In this paper, we propose two variants of the additive Schwarz method for the approximation of second order elliptic boundary value problems with discontinuous coefficients, on nonmatching grids using the lowest order Crouzeix-Raviart element for the discretization in each subdomain. The overall discretization is based on the mortar technique for coupling nonmatching grids. The convergence behavior of the proposed methods is similar to that of their closely related methods for conforming elements. The condition number bound for the preconditioned systems is independent of the jumps of the coefficient, and depend linearly on the ratio between the subdomain size and the mesh size. The performance of the methods is illustrated by some numerical results. This work has been supported by the Alexander von Humboldt Foundation and the special funds for major state basic research projects (973) under 2005CB321701 and the National Science Foundation (NSF) of China (No.10471144) This work has been supported in part by the Bergen Center for Computational Science, University of Bergen     

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.     

Schwarz alternating and iterative refinement methods for mixed formulations of elliptic problems,part I: Algorithms and numerical results

Summary We describe sequential and parallel algorithms based on the Schwarz alternating method for the solution of mixed finite element discretizations of elliptic problems using the Raviart-Thomas finite element spaces. These lead to symmetric indefinite linear systems and the algorithms have some similarities with the traditional block Gauss-Seidel or block Jacobi methods with overlapping blocks. The indefiniteness requires special treatment. The sub-blocks used in the algorithm correspond to problems on a coarse grid and some overlapping subdomains and is based on a similar partition used in an algorithm of Dryja and Widlund for standard elliptic problems. If there is sufficient overlap between the subdomains, the algorithm converges with a rate independent of the mesh size, the number of subdomains and discontinuities of the coefficients. Extensions of the above algorithms to the case of local grid refinement is also described. Convergence theory for these algorithms will be presented in a subsequent paper.This work was supported in part by the National Science Foundation under Grant NSF-CCR-8903003, while the author was a graduate student at New York University, and in part by the Army Research Office under Grant DAAL 03-91-G-0150, while the author was a Visiting Assistant Researcher at UCLA     

Schwarz alternating and iterative refinement methods for mixed formulations of elliptic problems,part II: Convergence theory

Summary In this paper we discuss bounds for the convergence rates of several domain decomposition algorithms to solve symmetric, indefinite linear systems arising from mixed finite element discretizations of elliptic problems. The algorithms include Schwarz methods and iterative refinement methods on locally refined grids. The implementation of Schwarz and iterative refinement algorithms have been discussed in part I. A discussion on the stability of mixed discretizations on locally refined grids is included and quantiative estimates for the convergence rates of some iterative refinement algorithms are also derived.Department of Mathematics, University of Wyoming, Laramie, WY 82071-3036. This work was supported in part by the National Science Foundation under Grant NSF-CCR-8903003, while the author was a graduate student at New York University, and in part by NSF Grant ASC 9003002, while the author was a Visiting, Assistant Researcher at UCLA.     

The cascadic multigrid method for elliptic problems

Summary. The paper deals with certain adaptive multilevel methods at the confluence of nested multigrid methods and iterative methods based on the cascade principle of [10]. From the multigrid point of view, no correction cycles are needed; from the cascade principle view, a basic iteration method without any preconditioner is used at successive refinement levels. For a prescribed error tolerance on the final level, more iterations must be spent on coarser grids in order to allow for less iterations on finer grids. A first candidate of such a cascadic multigrid method was the recently suggested cascadic conjugate gradient method of [9], in short CCG method, whichused the CG method as basic iteration method on each level. In [18] it has been proven, that the CCG method is accurate with optimal complexity for elliptic problems in 2D and quasi-uniform triangulations. The present paper simplifies that theory and extends it to more general basic iteration methods like the traditional multigrid smoothers. Moreover, an adaptive control strategy for the number of iterations on successive refinement levels for possibly highly non-uniform grids is worked out on the basis of a posteriori estimates. Numerical tests confirm the efficiency and robustness of the cascadic multigrid method. Received November 12, 1994 / Revised version received October 12, 1995     

Multilevel methods for mixed finite elements in three dimensions

In this paper we consider second order scalar elliptic boundary value problems posed over three–dimensional domains and their discretization by means of mixed Raviart–Thomas finite elements [18]. This leads to saddle point problems featuring a discrete flux vector field as additional unknown. Following Ewing and Wang [26], the proposed solution procedure is based on splitting the flux into divergence free components and a remainder. It leads to a variational problem involving solenoidal Raviart–Thomas vector fields. A fast iterative solution method for this problem is presented. It exploits the representation of divergence free vector fields as s of the –conforming finite element functions introduced by Nédélec [43]. We show that a nodal multilevel splitting of these finite element spaces gives rise to an optimal preconditioner for the solenoidal variational problem: Duality techniques in quotient spaces and modern algebraic multigrid theory [50, 10, 31] are the main tools for the proof. Received November 4, 1996 / Revised version received February 2, 1998     

A spatial domain decomposition method for parabolic optimal control problems

We present a non-overlapping spatial domain decomposition method for the solution of linear–quadratic parabolic optimal control problems. The spatial domain is decomposed into non-overlapping subdomains. The original parabolic optimal control problem is decomposed into smaller problems posed on space–time cylinder subdomains with auxiliary state and adjoint variables imposed as Dirichlet boundary conditions on the space–time interface boundary. The subdomain problems are coupled through Robin transmission conditions. This leads to a Schur complement equation in which the unknowns are the auxiliary state adjoint variables on the space-time interface boundary. The Schur complement operator is the sum of space–time subdomain Schur complement operators. The application of these subdomain Schur complement operators is equivalent to the solution of an subdomain parabolic optimal control problem. The subdomain Schur complement operators are shown to be invertible and the application of their inverses is equivalent to the solution of a related subdomain parabolic optimal control problem. We introduce a new family of Neumann–Neumann type preconditioners for the Schur complement system including several different coarse grid corrections. We compare the numerical performance of our preconditioners with an alternative approach recently introduced by Benamou.     

Incomplete block-matrix factorization iterative methods for convection-diffusion problems

Standard Galerkin finite element methods or finite difference methods for singular perturbation problems lead to strongly unsymmetric matrices, which furthermore are in general notM-matrices. Accordingly, preconditioned iterative methods such as preconditioned (generalized) conjugate gradient methods, which have turned out to be very successful for symmetric and positive definite problems, can fail to converge or require an excessive number of iterations for singular perturbation problems.This is not so much due to the asymmetry, as it is to the fact that the spectrum can have both eigenvalues with positive and negative real parts, or eigenvalues with arbitrary small positive real parts and nonnegligible imaginary parts. This will be the case for a standard Galerkin method, unless the meshparameterh is chosen excessively small. There exist other discretization methods, however, for which the corresponding bilinear form is coercive, whence its finite element matrix has only eigenvalues with positive real parts; in fact, the real parts are positive uniformly in the singular perturbation parameter.In the present paper we examine the streamline diffusion finite element method in this respect. It is found that incomplete block-matrix factorization methods, both on classical form and on an inverse-free (vectorizable) form, coupled with a general least squares conjugate gradient method, can work exceptionally well on this type of problem. The number of iterations is sometimes significantly smaller than for the corresponding almost symmetric problem where the velocity field is close to zero or the singular perturbation parameter =1.The 2 ^nd author's research was sponsored by Control Data Corporation through its PACER fellowship program.The 3 ^rd author's research was supported by the Netherlands organization for scientific research (NWO).On leave from the Institute of Mathematics, Academy of Science, 1090 Sofia, P.O. Box 373, Bulgaria.     

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.     

Robust iterative methods for elliptic problems with highly varying coefficients in thin substructures

Summary. In this paper we introduce a class of robust multilevel interface solvers for two-dimensional finite element discrete elliptic problems with highly varying coefficients corresponding to geometric decompositions by a tensor product of strongly non-uniform meshes. The global iterations convergence rate is shown to be of the order with respect to the number of degrees of freedom on the single subdomain boundaries, uniformly upon the coarse and fine mesh sizes, jumps in the coefficients and aspect ratios of substructures. As the first approach, we adapt the frequency filtering techniques [28] to construct robust smoothers on the highly non-uniform coarse grid. As an alternative, a multilevel averaging procedure for successive coarse grid correction is proposed and analyzed. The resultant multilevel coarse grid preconditioner is shown to have (in a two level case) the condition number independent of the coarse mesh grading and jumps in the coefficients related to the coarsest refinement level. The proposed technique exhibited high serial and parallel performance in the skin diffusion processes modelling [20] where the high dimensional coarse mesh problem inherits a strong geometrical and coefficients anisotropy. The approach may be also applied to magnetostatics problems as well as in some composite materials simulation. Received December 27, 1994     

A subspace preconditioning algorithm for eigenvector/eigenvalue computation

We consider the problem of computing a modest number of the smallest eigenvalues along with orthogonal bases for the corresponding eigenspaces of a symmetric positive definite operatorA defined on a finite dimensional real Hilbert spaceV. In our applications, the dimension ofV is large and the cost of invertingA is prohibitive. In this paper, we shall develop an effective parallelizable technique for computing these eigenvalues and eigenvectors utilizing subspace iteration and preconditioning forA. Estimates will be provided which show that the preconditioned method converges linearly when used with a uniform preconditioner under the assumption that the approximating subspace is close enough to the span of desired eigenvectors.     

Parallel domain decomposition procedures of improved D-D type for parabolic problems

Two parallel domain decomposition procedures for solving initial-boundary value problems of parabolic partial differential equations are proposed. One is the extended D-D type algorithm, which extends the explicit/implicit conservative Galerkin domain decomposition procedures, given in [5], from a rectangle domain and its decomposition that consisted of a stripe of sub-rectangles into a general domain and its general decomposition with a net-like structure. An almost optimal error estimate, without the factor H^−1/2 given in Dawson-Dupont’s error estimate, is proved. Another is the parallel domain decomposition algorithm of improved D-D type, in which an additional term is introduced to produce an approximation of an optimal error accuracy in L²-norm.     

Finite element methods and their convergence for elliptic and parabolic interface problems

In this paper, we consider the finite element methods for solving second order elliptic and parabolic interface problems in two-dimensional convex polygonal domains. Nearly the same optimal -norm and energy-norm error estimates as for regular problems are obtained when the interfaces are of arbitrary shape but are smooth, though the regularities of the solutions are low on the whole domain. The assumptions on the finite element triangulation are reasonable and practical. Received July 7, 1996 / Revised version received March 3, 1997