Block monotone iterative methods for numerical solutions of nonlinear elliptic equations

Summary. Two block monotone iterative schemes for a nonlinear algebraic system, which is a finite difference approximation of a nonlinear elliptic boundary-value problem, are presented and are shown to converge monotonically either from above or from below to a solution of the system. This monotone convergence result yields a computational algorithm for numerical solutions as well as an existence-comparison theorem of the system, including a sufficient condition for the uniqueness of the solution. An advantage of the block iterative schemes is that the Thomas algorithm can be used to compute numerical solutions of the sequence of iterations in the same fashion as for one-dimensional problems. The block iterative schemes are compared with the point monotone iterative schemes of Picard, Jacobi and Gauss-Seidel, and various theoretical comparison results among these monotone iterative schemes are given. These comparison results demonstrate that the sequence of iterations from the block iterative schemes converges faster than the corresponding sequence given by the point iterative schemes. Application of the iterative schemes is given to a logistic model problem in ecology and numerical ressults for a test problem with known analytical solution are given. Received August 1, 1993 / Revised version received November 7, 1994     

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     

Convergence of block two-stage iterative methods for symmetric positive definite systems

Summary. We study the convergence of two-stage iterative methods for solving symmetric positive definite (spd) systems. The main tool we used to derive the iterative methods and to analyze their convergence is the diagonally compensated reduction (cf. [1]). Received December 11, 1997 / Revised version received March 25, 1999 / Published online May 30, 2001     

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 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     

Existence and uniqueness of splittings for stationary iterative methods with applications to alternating methods

Summary. Given a nonsingular matrix , and a matrix of the same order, under certain very mild conditions, there is a unique splitting , such that . Moreover, all properties of the splitting are derived directly from the iteration matrix . These results do not hold when the matrix is singular. In this case, given a matrix and a splitting such that , there are infinitely many other splittings corresponding to the same matrices and , and different splittings can have different properties. For instance, when is nonnegative, some of these splittings can be regular splittings, while others can be only weak splittings. Analogous results hold in the symmetric positive semidefinite case. Given a singular matrix , not for all iteration matrices there is a splitting corresponding to them. Necessary and sufficient conditions for the existence of such splittings are examined. As an illustration of the theory developed, the convergence of certain alternating iterations is analyzed. Different cases where the matrix is monotone, singular, and positive (semi)definite are studied. Received September 5, 1995 / Revised version received April 3, 1996     

Adaptive finite element methods for elliptic equations with non-smooth coefficients

Summary. We consider a second-order elliptic equation with discontinuous or anisotropic coefficients in a bounded two- or three dimensional domain, and its finite-element discretization. The aim of this paper is to prove some a priori and a posteriori error estimates in an appropriate norm, which are independent of the variation of the coefficients. Received February 5, 1999 / Published online March 16, 2000     

The finite element approximation of a coupled reaction-diffusion problem with non-Lipschitz nonlinearities

Summary. A coupled semilinear elliptic problem modelling an irreversible, isothermal chemical reaction is introduced, and discretised using the usual piecewise linear Galerkin finite element approximation. An interesting feature of the problem is that a reaction order of less than one gives rise to a "dead core" region. Initially, one reactant is assumed to be acting as a catalyst and is kept constant. It is shown that error bounds previously obtained for a scheme involving numerical integration can be improved upon by considering a quadratic regularisation of the nonlinear term. This technique is then applied to the full coupled problem, and optimal and error bounds are proved in the absence of quadrature. For a scheme involving numerical integration, bounds similar to those obtained for the catalyst problem are shown to hold. Received May 25, 1993 / Revised version received July 5, 1994     

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     

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     

Nonlinear Galerkin methods and mixed finite elements: two-grid algorithms for the Navier-Stokes equations

Summary. A nonlinear Galerkin method using mixed finite elements is presented for the two-dimensional incompressible Navier-Stokes equations. The scheme is based on two finite element spaces and for the approximation of the velocity, defined respectively on one coarse grid with grid size and one fine grid with grid size and one finite element space for the approximation of the pressure. Nonlinearity and time dependence are both treated on the coarse space. We prove that the difference between the new nonlinear Galerkin method and the standard Galerkin solution is of the order of $H^2$, both in velocity ( and pressure norm). We also discuss a penalized version of our algorithm which enjoys similar properties. Received October 5, 1993 / Revised version received November 29, 1993     

A second order finite difference error indicator for adaptive transonic flow computations

Summary. An adaptive finite element method for the calculation of transonic potential flows was developed. An error indicator based on first order finite differences of gradients is introduced as a local error estimator. It measures second order distributional derivatives. Estimates involving this error estimator, a residual and the error are given. The error estimator can be used as a criterion for mesh refinement. We also give some computational results. Received September 16, 1993 / Revised version received June 7, 1994     

Minimal decompositions and iterative methods

Summary. The aim of this paper is to prove some Babuška–Brezzi type conditions which are involved in the mortar spectral element discretization of the Stokes problem, for several cases of nonconforming domain decompositions. ID=" <E5>Dedicated to Olof B. Widlund on the occasion of his 60th birthday</E5>     

Domain decomposition iterative procedures for solving scalar waves in the frequency domain

The propagation of dispersive waves can be modeled relevantly in the frequency domain. A wave problem in the frequency domain is difficult to solve numerically. In addition to having a complex–valued solution, the problem is neither Hermitian symmetric nor coercive in a wide range of applications in Geophysics or Quantum–Mechanics. In this paper, we consider a parallel domain decomposition iterative procedure for solving the problem by finite differences or conforming finite element methods. The analysis includes the decomposition of the domain into either the individual elements or larger subdomains ( of finite elements). To accelerate the speed of convergence, we introduce relaxation parameters on the subdomain interfaces and an artificial damping iteration. The convergence rate of the resulting algorithm turns out to be independent on the mesh size and the wave number. Numerical results carried out on an nCUBE2 parallel computer are presented to show the effectiveness of the method. Received October 30, 1995 / Revised version received January 10, 1997     

Finite difference preconditioning cubic spline collocation method of elliptic equations

Summary. We discuss a finite difference preconditioner for the interpolatory cubic spline collocation method for a uniformly elliptic operator defined by in (the unit square) with homogeneous Dirichlet boundary conditions. Using the generalized field of values arguments, we discuss the eigenvalues of the preconditioned matrix where is the matrix of the collocation discretization operator corresponding to , and is the matrix of the finite difference operator corresponding to the uniformly elliptic operator given by in with homogeneous Dirichlet boundary conditions. Finally we mention a bound of -singular values of for a general elliptic operator in . Received December 11, 1995 / Revised version received June 20, 1996     

An adaptive Chebyshev iterative method\newline for nonsymmetric linear systems based on modified moments

Summary. Large, sparse nonsymmetric systems of linear equations with a matrix whose eigenvalues lie in the right half plane may be solved by an iterative method based on Chebyshev polynomials for an interval in the complex plane. Knowledge of the convex hull of the spectrum of the matrix is required in order to choose parameters upon which the iteration depends. Adaptive Chebyshev algorithms, in which these parameters are determined by using eigenvalue estimates computed by the power method or modifications thereof, have been described by Manteuffel [18]. This paper presents an adaptive Chebyshev iterative method, in which eigenvalue estimates are computed from modified moments determined during the iterations. The computation of eigenvalue estimates from modified moments requires less computer storage than when eigenvalue estimates are computed by a power method and yields faster convergence for many problems. Received May 13, 1992/Revised version received May 13, 1993     

The maximum angle condition in the finite element method for monotone problems with applications in magnetostatics

Summary. The finite element method for an elliptic equation with discontinuous coefficients (obtained for the magnetic potential from Maxwell's equations) is analyzed in the union of closed domains the boundaries of which form a system of three circles with the same centre. As the middle domain is very narrow the triangulations obeying the maximum angle condition are considered. In the case of piecewise linear trial functions the maximum rate of convergence in the norm of the space is proved under the following conditions: 1. the exact solution is piecewise of class ; 2. the family of subtriangulations of the narrow subdomain satisfies the maximum angle condition expressed by relation (38). The paper extends the results of [24]. Received March 8, 1993 / Revised version received November 28, 1994     

Convergence of finite volume schemes for semilinear convection diffusion equations

The topic of this work is the discretization of semilinear elliptic problems in two space dimensions by the cell centered finite volume method. Dirichlet boundary conditions are considered here. A discrete Poincaré inequality is used, and estimates on the approximate solutions are proven. The convergence of the scheme without any assumption on the regularity of the exact solution is proven using some compactness results which are shown to hold for the approximate solutions. Received January 16, 1998 / Revised version received June 19, 1998     

Monotone iterative methods for finite difference system of reaction-diffusion equations

Summary This paper presents an existence-comparison theorem and an iterative method for a nonlinear finite difference system which corresponds to a class of semilinear parabolic and elliptic boundary-value problems. The basic idea of the iterative method for the computation of numerical solutions is the monotone approach which involves the notion of upper and lower solutions and the construction of monotone sequences from a suitable linear discrete system. Using upper and lower solutions as two distinct initial iterations, two monotone sequences from a suitable linear system are constructed. It is shown that these two sequences converge monotonically from above and below, respectively, to a unique solution of the nonlinear discrete equations. This formulation leads to a well-posed problem for the nonlinear discrete system. Applications are given to several models arising from physical, chemical and biological systems. Numerical results are given to some of these models including a discussion on the rate of convergence of the monotone sequences.     

Fully discrete finite element approaches for time-dependent Maxwell's equations

A fully discrete finite element method is used to approximate the electric field equation derived from time-dependent Maxwell's equations in three dimensional polyhedral domains. Optimal energy-norm error estimates are achieved for general Lipschitz polyhedral domains. Optimal -norm error estimates are obtained for convex polyhedral domains. Received February 3, 1997 / Revised version received February 27, 1998