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     

Asynchronous two-stage iterative methods

Summary. Parallel block two-stage iterative methods for the solution of linear systems of algebraic equations are studied. Convergence is shown for monotone matrices and for -matrices. Two different asynchronous versions of these methods are considered and their convergence investigated. Received September 7, 1993 / Revised version received April 21, 1994     

On multisplitting methods for band matrices

Summary. We present new theoretical results on two classes of multisplitting methods for solving linear systems iteratively. These classes are based on overlapping blocks of the underlying coefficient matrix which is assumed to be a band matrix. We show that under suitable conditions the spectral radius of the iteration matrix does not depend on the weights of the method even if these weights are allowed to be negative. For a certain class of splittings we prove an optimality result for with respect to the weights provided that is an M–matrix. This result is based on the fact that the multisplitting method can be represented by a single splitting which in our situation surprisingly turns out to be a regular splitting. Furthermore we show by numerical examples that weighting factors may considerably improve the convergence. Received July 18, 1994 / Revised version received November 20, 1995     

An algorithm for coarsening unstructured meshes

Summary. We develop and analyze a procedure for creating a hierarchical basis of continuous piecewise linear polynomials on an arbitrary, unstructured, nonuniform triangular mesh. Using these hierarchical basis functions, we are able to define and analyze corresponding iterative methods for solving the linear systems arising from finite element discretizations of elliptic partial differential equations. We show that such iterative methods perform as well as those developed for the usual case of structured, locally refined meshes. In particular, we show that the generalized condition numbers for such iterative methods are of order , where is the number of hierarchical basis levels. Received December 5, 1994     

The convergence rate of the minimal residual method for the Stokes problem

Summary. Discretisation of the classical Stokes problem gives rise to symmetric indefinite matrices with eigenvalues which, in a precise way, are not symmetric about the origin, but which do depend on a mesh size parameter. Convergence estimates for the Conjugate Residual or Minimum Residual iterative solution of such systems are given by best minimax polynomial approximations on an inclusion set for the eigenvalues. In this paper, an analytic convergence estimate for such problems is given in terms of an asymptotically small mesh size parameter. Received November 16, 1993 / Revised version received August 2, 1994     

Multilevel additive and multiplicative methods for orthogonal spline collocation problems

Summary. Multilevel preconditioners are proposed for the iterative solution of the discrete problems which arise when orthogonal spline collocation with piecewise Hermite bicubics is applied to the Dirichlet boundary value problem for a self-adjoint elliptic partial differential equation on a rectangle. Additive and multiplicative preconditioners are defined respectively as sums and products of independent operators on a sequence of nested subspaces of the fine partition approximation space. A general theory of additive and multiplicative Schwarz methods is used to prove that the preconditioners are spectrally equivalent to the collocation discretization of the Laplacian with the spectral constants independent of the fine partition stepsize and the number of levels. The preconditioned conjugate gradient and preconditioned Orthomin methods are considered for the solution of collocation problems. An implementation of the methods is discussed and the results of numerical experiments are presented. Received March 1, 1994 / Revised version received January 23, 1996     

Accelerated monotone iterative methods for finite difference equations of reaction-diffusion

This paper is concerned with numerical methods for a finite difference system of reaction-diffusion-convection equation under nonlinear boundary condition. Various monotone iterative methods are presented, and each of these methods leads to an existence-comparison theorem as well as a computational algorithm for numerical solutions. The monotone property of the iterations gives improved upper and lower bounds of the solution in each iteration, and the rate of convergence of the iterations is either quadratic or nearly quadratic depending on the property of the nonlinear function. Application is given to a model problem from chemical engineering, and some numerical results, including a test problem with known analytical solution, are presented to illustrate the various rates of convergence of the iterations. Received November 2, 1995 / Revised version received February 10, 1997     

On hybrid iterative methods for nonsymmetric systems of linear equations

Summary. Hybrid methods for the solution of systems of linear equations consist of a first phase where some information about the associated coefficient matrix is acquired, and a second phase in which a polynomial iteration designed with respect to this information is used. Most of the hybrid algorithms proposed recently for the solution of nonsymmetric systems rely on the direct use of eigenvalue estimates constructed by the Arnoldi process in Phase I. We will show the limitations of this approach and propose an alternative, also based on the Arnoldi process, which approximates the field of values of the coefficient matrix and of its inverse in the Krylov subspace. We also report on numerical experiments comparing the resulting new method with other hybrid algorithms. Received May 27, 1993 / Revised version received November 14, 1994     

Overlapping Schwarz methods on unstructured meshes using non-matching coarse grids

Summary. We consider two level overlapping Schwarz domain decomposition methods for solving the finite element problems that arise from discretizations of elliptic problems on general unstructured meshes in two and three dimensions. Standard finite element interpolation from the coarse to the fine grid may be used. Our theory requires no assumption on the substructures that constitute the whole domain, so the substructures can be of arbitrary shape and of different size. The global coarse mesh is allowed to be non-nested to the fine grid on which the discrete problem is to be solved, and neither the coarse mesh nor the fine mesh need be quasi-uniform. In addition, the domains defined by the fine and coarse grid need not be identical. The one important constraint is that the closure of the coarse grid must cover any portion of the fine grid boundary for which Neumann boundary conditions are given. In this general setting, our algorithms have the same optimal convergence rate as the usual two level overlapping domain decomposition methods on structured meshes. The condition number of the preconditioned system depends only on the (possibly small) overlap of the substructures and the size of the coarse grid, but is independent of the sizes of the subdomains. Received March 23, 1994 / Revised version received June 2, 1995     

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     

On the use of rational iterations and domain decomposition methods for the Helmholtz problem

An iterative algorithm for the numerical solution of the Helmholtz problem is considered. It is difficult to solve the problem numerically, in particular, when the imaginary part of the wave number is zero or small. We develop a parallel iterative algorithm based on a rational iteration and a nonoverlapping domain decomposition method for such a non-Hermitian, non-coercive problem. Algorithm parameters (artificial damping and relaxation) are introduced to accelerate the convergence speed of the iteration. Convergence analysis and effective strategies for finding efficient algorithm parameters are presented. Numerical results carried out on an nCUBE2 are given to show the efficiency of the algorithm. To reduce the boundary reflection, we employ a hybrid absorbing boundary condition (ABC) which combines the first-order ABC and the physical $Q$ ABC. Computational results comparing the hybrid ABC with non-hybrid ones are presented. Received May 19, 1994 / Revised version received March 25, 1997     

On the convergence of line iterative methods for cyclically reduced non-symmetrizable linear systems

Summary. We derive analytic bounds on the convergence factors associated with block relaxation methods for solving the discrete two-dimensional convection-diffusion equation. The analysis applies to the reduced systems derived when one step of block Gaussian elimination is performed on red-black ordered two-cyclic discretizations. We consider the case where centered finite difference discretization is used and one cell Reynolds number is less than one in absolute value and the other is greater than one. It is shown that line ordered relaxation exhibits very fast rates of convergence. Received March 3, 1992/Revised version received July 2, 1993     

How bad are Hankel matrices?

Summary. Considered are Hankel, Vandermonde, and Krylov basis matrices. It is proved that for any real positive definite Hankel matrix of order , its spectral condition number is bounded from below by . Also proved is that the spectral condition number of a Krylov basis matrix is bounded from below by . For , a Vandermonde matrix with arbitrary but pairwise distinct nodes , we show that ; if either or for all , then . Received January 24, 1993/Revised version received July 19, 1993     

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     

The algebraic torus theorem

A structure theorem is proved for a finitely generated group with a finitely generated virtually polycyclic codimension one subgroup. Oblatum 12-II-1999 & 18-XI-1999?Published online: 21 February 2000     

On nonlinear generalized conjugate gradient methods

Summary. The Generalized Conjugate Gradient method (see [1]) is an iterative method for nonsymmetric linear systems. We obtain generalizations of this method for nonlinear systems with nonsymmetric Jacobians. We prove global convergence results. Received April 29, 1992 / Revised version received November 18, 1993     

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     

Efficient methods using high accuracy approximate inertial manifolds

Summary. We extend the idea of the post-processing Galerkin method, in the context of dissipative evolution equations, to the nonlinear Galerkin, the filtered Galerkin, and the filtered nonlinear Galerkin methods. In general, the post-processing algorithm takes advantage of the fact that the error committed in the lower modes of the nonlinear Galerkin method (and Galerkin method), for approximating smooth, bounded solutions, is much smaller than the total error of the method. In each case, an improvement in accuracy is obtained by post-processing these more accurate lower modes with an appropriately chosen, highly accurate, approximate inertial manifold (AIM). We present numerical experiments that support the theoretical improvements in accuracy. Both the theory and computations are presented in the framework of a two dimensional reaction-diffusion system with polynomial nonlinearity. However, the algorithm is very general and can be implemented for other dissipative evolution systems. The computations clearly show the post-processed filtered Galerkin method to be the most efficient method. Received September 10, 1998 / Revised version received April 26, 1999 / Published online July 12, 2000     

Block and asynchronous two-stage methods for mildly nonlinear systems

Block parallel iterative methods for the solution of mildly nonlinear systems of equations of the form are studied. Two-stage methods, where the solution of each block is approximated by an inner iteration, are treated. Both synchronous and asynchronous versions are analyzed, and both pointwise and blockwise convergence theorems provided. The case where there are overlapping blocks is also considered. The analysis of the asynchronous method when applied to linear systems includes cases not treated before in the literature. Received June 5, 1997 / Revised version received December 29, 1997     

Convergence of algebraic multigrid based on smoothed aggregation

Summary. We prove an abstract convergence estimate for the Algebraic Multigrid Method with prolongator defined by a disaggregation followed by a smoothing. The method input is the problem matrix and a matrix of the zero energy modes of the same problem but with natural boundary conditions. The construction is described in the case of a general elliptic system. The condition number bound increases only as a polynomial of the number of levels, and requires only a uniform weak approximation property for the aggregation operators. This property can be a-priori verified computationally once the aggregates are known. For illustration, it is also verified here for a uniformly elliptic diffusion equations discretized by linear conforming quasiuniform finite elements. Only very weak and natural assumptions on the hierarchy of aggregates are needed. Received March 1, 1998 / Revised version received January 28, 2000 / Published online: December 19, 2000