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     

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     

Modified ILU as a smoother

Summary. We study a variant of ILU, viz. with , as a smoother in multi-grid methods. The -decomposition is characterized by the fact that the rest matrix is not zero on the diagonal but instead of that satisfies . The use of as a smoother is recommended because of the observed robustness when it is applied to singular perturbation problems. However, until now, a proof of robustness has only been given for one model anisotropic equation by Wittum. In this paper, we show that the -decomposition of an M-matrix exists and yields a regular splitting. For symmetric M-matrices and symmetric decomposition ``patterns' we prove that the eigenvalues of the -smoother are in \footnote{After this paper was submitted, the author learned of a report of Notay (\cite{239.5}) where related results are discussed}, whereas the rest matrix is at most a modest factor larger than the rest matrix of the unmodified ILU-decomposition. With these properties, robustness can now be shown when the rest matrix of the unmodified decomposition is ``small enough'. Our results generalize Wittum's results for the model problem. Received August 16, 1992 / Revised version received September 7, 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     

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     

Error estimate for a stabilised domain decomposition method with nonmatching grids

Summary. In this paper, we analyse a stabilisation technique for the so-called three-field formulation for nonoverlapping domain decomposition methods. The stabilisation is based on boundary bubble functions in each subdomain which are then eliminated by static condensation. The discretisation grids in the subdomains can be chosen independently as well as the grid for the final interface problem. We present the analysis of the method and we construct a set of bubble functions which guarantees the optimal rate of convergence. Received May 12, 1998 / Revised version received November 21, 2000 / Published online June 7, 2001     

Convergence rate of some domain decomposition methods for overlapping and nonoverlapping subdomains

Summary. Three iterative domain decomposition methods are considered: simultaneous updates on all subdomains (Additive Schwarz Method), flow directed sweeps and double sweeps. By using some techniques of formal language theory we obtain a unique criterion of convergence for the three methods. The convergence rate is a function of the criterion and depends on the algorithm. Received October 24, 1994 / Revised version received November 27, 1995     

Wavelet adaptive method for second order elliptic problems: boundary conditions and domain decomposition

Summary. Wavelet methods allow to combine high order accuracy, multilevel preconditioning techniques and adaptive approximation, in order to solve efficiently elliptic operator equations. One of the main difficulty in this context is the efficient treatment of non-homogeneous boundary conditions. In this paper, we propose a strategy that allows to append such conditions in the setting of space refinement (i.e. adaptive) discretizations of second order problems. Our method is based on the use of compatible multiscale decompositions for both the domain and its boundary, and on the possibility of characterizing various function spaces from the numerical properties of these decompositions. In particular, this allows the construction of a lifting operator which is stable for a certain range of smoothness classes, and preserves the compression of the solution in the wavelet basis. An explicit construction of the wavelet bases and the lifting is proposed on fairly general domains, based on conforming domain decomposition techniques. Received November 2, 1998 / Published online April 20, 2000     

A two-level domain decomposition method for the iterative solution of high frequency exterior Helmholtz problems

Summary. We present a Lagrange multiplier based two-level domain decomposition method for solving iteratively large-scale systems of equations arising from the finite element discretization of high-frequency exterior Helmholtz problems. The proposed method is essentially an extension of the regularized FETI (Finite Element Tearing and Interconnecting) method to indefinite problems. Its two key ingredients are the regularization of each subdomain matrix by a complex interface lumped mass matrix, and the preconditioning of the interface problem by an auxiliary coarse problem constructed to enforce at each iteration the orthogonality of the residual to a set of carefully chosen planar waves. We show numerically that the proposed method is scalable with respect to the mesh size, the subdomain size, and the wavenumber. We report performance results for a submarine application that highlight the efficiency of the proposed method for the solution of high frequency acoustic scattering problems discretized by finite elements. Received March 17, 1998 / Revised version received June 7, 1999 / Published online January 27, 2000     

Balancing domain decomposition for nonconforming plate elements

Summary. In this paper the balancing domain decomposition method is extended to nonconforming plate elements. The condition number of the preconditioned system is shown to be bounded by , where H measures the diameters of the subdomains, h is the mesh size of the triangulation, and the constant C is independent of H, h and the number of subdomains. Received August 14, 1997     

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 condition number of the Schur complement in domain decomposition

Summary. It is shown that for elliptic boundary value problems of order 2m the condition number of the Schur complement matrix that appears in nonoverlapping domain decomposition methods is of order , where d measures the diameters of the subdomains and h is the mesh size of the triangulation. The result holds for both conforming and nonconforming finite elements. Received: January 15, 1998     

Nonconforming finite elements and the cascadic multi-grid method

Summary. We derive sufficient conditions under which the cascadic multi-grid method applied to nonconforming finite element discretizations yields an optimal solver. Key ingredients are optimal error estimates of such discretizations, which we therefore study in detail. We derive a new, efficient modified Morley finite element method. Optimal cascadic multi-grid methods are obtained for problems of second, and using a new smoother, of fourth order as well as for the Stokes problem. Received February 12, 1998 / Revised version received January 9, 2001 / Published online September 19, 2001     

Adaptive filtering

Summary. In this paper, the adaptive filtering method is introduced and analysed. This method leads to robust algorithms for the solution of systems of linear equations which arise from the discretisation of partial differential equations with strongly varying coefficients. These iterative algorithms are based on the tangential frequency filtering decompositions (TFFD). During the iteration with a preliminary preconditioner, the adaptive test vector method calculates new test vectors for the TFFD. The adaptive test vector iterative method allows the combination of the tangential frequency decomposition and other iterative methods such as multi-grid. The connection with the TFFD improves the robustness of these iterative methods with respect to varying coefficients. Interface problems as well as problems with stochastically distributed properties are considered. Realistic numerical experiments confirm the efficiency of the presented algorithms. Received June 26, 1996 / Revised version received October 7, 1996     

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     

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     

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     

Nonstandard coarse spaces and Schwarz methods for elliptic problems with discontinuous coefficients using non-conforming elements

Summary. Two-level domain decomposition methods are developed for a simple nonconforming approximation of second order elliptic problems. A bound is established for the condition number of these iterative methods, that grows only logarithmically with the number of degrees of freedom in each subregion. This bound holds for two and three dimensions and is independent of jumps in the value of the coefficients and number of subregions. We introduce face coarse spaces, and isomorphisms to map between conforming and nonconforming spaces. ReceivedMarch 1, 1995 / Revised version received January 16, 1996     

A preconditioner for the h-p version of the finite element method in two dimensions

Summary. A preconditioner, based on a two-level mesh and a two-level orthogonalization, is proposed for the - version of the finite element method for two dimensional elliptic problems in polygonal domains. Its implementation is in parallel on the subdomain level for the linear or bilinear (nodal) modes, and in parallel on the element level for the high order (side and internal) modes. The condition number of the preconditioned linear system is of order , where is the diameter of the -th subdomain, and are the diameter of elements and the maximum polynomial degree used in the subdomain. This result reduces to well-known results for the -version (i.e. ) and the -version (i.e. ) as the special cases of the - version. Received August 15, 1995 / Revised version received November 13, 1995     

Multilevel diagonal scaling preconditioners for boundary element equations on locally refined meshes

Summary. We study a multilevel preconditioner for the Galerkin boundary element matrix arising from a symmetric positive-definite bilinear form. The associated energy norm is assumed to be equivalent to a Sobolev norm of positive, possibly fractional, order m on a bounded (open or closed) surface of dimension d, with . We consider piecewise linear approximation on triangular elements. Successive levels of the mesh are created by selectively subdividing elements within local refinement zones. Hanging nodes may be created and the global mesh ratio can grow exponentially with the number of levels. The coarse-grid correction consists of an exact solve, and the correction on each finer grid amounts to a simple diagonal scaling involving only those degrees of freedom whose associated nodal basis functions overlap the refinement zone. Under appropriate assumptions on the choice of refinement zones, the condition number of the preconditioned system is shown to be bounded by a constant independent of the number of degrees of freedom, the number of levels and the global mesh ratio. In addition to applying to Galerkin discretisation of hypersingular boundary integral equations, the theory covers finite element methods for positive-definite, self-adjoint elliptic problems with Dirichlet boundary conditions. Received October 5, 2001 / Revised version received December 5, 2001 / Published online April 17, 2002 The support of this work through Visiting Fellowship grant GR/N21970 from the Engineering and Physical Sciences Research Council of Great Britain is gratefully acknowledged. The second author was also supported by the Australian Research Council