An overlapping Schwarz method for virtual element discretizations in two dimensions

A new coarse space for domain decomposition methods is presented for nodal elliptic problems in two dimensions. The coarse space is derived from the novel virtual element methods and therefore can accommodate quite irregular polygonal subdomains. It has the advantage with respect to previous studies that no discrete harmonic extensions are required. The virtual element method allows us to handle polygonal meshes and the algorithm can then be used as a preconditioner for linear systems that arise from a discretization with such triangulations. A bound is obtained for the condition number of the preconditioned system by using a two-level overlapping Schwarz algorithm, but the coarse space can also be used for different substructuring methods. This bound is independent of jumps in the coefficient across the interface between the subdomains. Numerical experiments that verify the result are shown, including some with triangular, square, hexagonal and irregular elements and with irregular subdomains obtained by a mesh partitioner.     

Parallel Semi-Implicit Spectral Element Methods for Atmospheric General Circulation Models

Spectral elements combine the accuracy and exponential convergence of conventional spectral methods with the geometric flexibility of finite elements. Additionally, there are several apparent computational advantages to using spectral element methods on microprocessors. In particular, the computations are naturally cache-blocked and derivatives may be computed using nearest neighbor communications. Thus, an explicit spectral element atmospheric model has demonstrated close to linear scaling on a variety of distributed memory computers including the IBM SP and Linux Clusters. Explicit formulations of PDE's arising in geophysical fluid dynamics, such as the primitive equations on the sphere, are time-step limited by the phase speed of gravity waves. Semi-implicit time integration schemes remove the stability restriction but require the solution of an elliptic BVP. By employing a weak formulation of the governing equations, it is possible to obtain a symmetric Helmholtz operator that permits the solution of the implicit problem using conjugate gradients. We find that a block-Jacobi preconditioned conjugate gradient solver accelerates the simulation rate of the semi-implicit relative to the explicit formulation for practical climate resolutions by about a factor of three.     

Optimal left and right additive Schwarz preconditioning for minimal residual methods with Euclidean and energy norms

For the solution of non-symmetric or indefinite linear systems arising from discretizations of elliptic problems, two-level additive Schwarz preconditioners are known to be optimal in the sense that convergence bounds for the preconditioned problem are independent of the mesh and the number of subdomains. These bounds are based on some kind of energy norm. However, in practice, iterative methods which minimize the Euclidean norm of the residual are used, despite the fact that the usual bounds are non-optimal, i.e., the quantities appearing in the bounds may depend on the mesh size; see [X.-C. Cai, J. Zou, Some observations on the l² convergence of the additive Schwarz preconditioned GMRES method, Numer. Linear Algebra Appl. 9 (2002) 379-397]. In this paper, iterative methods are presented which minimize the same energy norm in which the optimal Schwarz bounds are derived, thus maintaining the Schwarz optimality. As a consequence, bounds for the Euclidean norm minimization are also derived, thus providing a theoretical justification for the practical use of Euclidean norm minimization methods preconditioned with additive Schwarz. Both left and right preconditioners are considered, and relations between them are derived. Numerical experiments illustrate the theoretical developments.     

Theoretical analysis of some spectral multigrid methods

We develop a theoretical analysis of a multigrid algorithm applied to spectral element discretization of linear elliptic problems. For a 1-D problem with non-constant coefficients we prove essentially the independence of the two-level convergence factor with respect to both the degree of the polynomial approximation and the number of spectral elements. We also sketch some ideas for the analysis of the 2-D case when only one spectral element is involved.     

Schwarz iterations for the efficient solution of screen problems with boundary elements

This paper investigates two domain decomposition algorithms for the numerical solution of boundary integral equations of the first kind. The schemes are based on theh-type boundary element Galerkin method to which the multiplicative and the additive Schwarz methods are applied. As for twodimensional problems, the rates of convergence of both methods are shown to be independent of the number of unknowns. Numerical results for standard model problems arising from Laplaces' equation with Dirichlet or Neumann boundary conditions in both two and three dimensions are discussed. A multidomain decomposition strategy is indicated by means of a screen problem in three dimensions, so as to obtain satisfactory experimental convergence rates.     

Uniform convergence and Schwarz method for the mortar projection nonconforming and mixed element methods for nonselfadjoint and indefinite problems

In this paper, two mortar versions of the so-called projection nonconforming and the mixed element methods are proposed, respectively, for nonselfadjoint and indefinite second-order elliptic problems. It is proven that the mortar mixed element method is equivalent to the mortar projection nonconforming element method. Based on this equivalence, the existence, uniqueness, and uniform convergence of the solution for mortar mixed element method are shown only under minimal regularity assumption. Meanwhile, the optimal error estimate is obtained under certain regularity assumption. Furthermore, an additive Schwarz preconditioning method is proposed for solving the discrete problem and the nearly optimal convergence rate for the preconditioned GMRES method is proven under minimal regularity assumption. Finally, the practical implementation of the method is adderssed and numerical experiments are presented.     

Normalized explicit finite element approximate inverse preconditioning

Normalized explicit approximate inverse matrix techniques for computing explicitly various families of normalized approximate inverses based on normalized approximate factorization procedures for solving sparse linear systems, which are derived from the finite difference and finite element discretization of partial differential equations are presented. Normalized explicit preconditioned conjugate gradient-type schemes in conjunction with normalized approximate inverse matrix techniques are presented for the efficient solution of linear and non-linear systems. Theoretical estimates on the rate of convergence and computational complexity of the normalized explicit preconditioned conjugate gradient method are also presented. Applications of the proposed methods on characteristic linear and non-linear problems are discussed and numerical results are given.     

Hybrid Multigrid/Schwarz Algorithms for the Spectral Element Method

We study the performance of the multigrid method applied to spectral element (SE) discretizations of the Poisson and Helmholtz equations. Smoothers based on finite element (FE) discretizations, overlapping Schwarz methods, and point-Jacobi are considered in conjunction with conjugate gradient and GMRES acceleration techniques. It is found that Schwarz methods based on restrictions of the originating SE matrices converge faster than FE-based methods and that weighting the Schwarz matrices by the inverse of the diagonal counting matrix is essential to effective Schwarz smoothing. Several of the methods considered achieve convergence rates comparable to those attained by classic multigrid on regular grids.     

Numerical and computational aspects of some block-preconditioners for saddle point systems

Linear systems with two-by-two block matrices are usually preconditioned by block lower- or upper-triangular systems that require an approximation of the related Schur complement. In this work, in the finite element framework, we consider one special such approximation, namely, the element-wise Schur complement. It is sparse and its construction is perfectly parallelizable, making it an appropriate ingredient when building preconditioners for iterative solvers executed on both distributed and shared memory computer architectures. For saddle point matrices with symmetric positive (semi-)definite blocks we show that the Schur complement is spectrally equivalent to the so-constructed approximation and derive spectral equivalence bounds. We also illustrate the quality of the approximation for nonsymmetric problems, where we observe the same good numerical efficiency.Furthermore, we demonstrate the computational and numerical performance of the corresponding preconditioned iterative solution method on a large scale model benchmark problem originating from the elastic glacial isostatic adjustment model discretized using the finite element method.     

Explicit approximate inverse preconditioning techniques

Summary  The numerical treatment and the production of related software for solving large sparse linear systems of algebraic equations, derived mainly from the discretization of partial differential equation, by preconditioning techniques has attracted the attention of many researchers. In this paper we give an overview of explicit approximate inverse matrix techniques for computing explicitly various families of approximate inverses based on Choleski and LU—type approximate factorization procedures for solving sparse linear systems, which are derived from the finite difference, finite element and the domain decomposition discretization of elliptic and parabolic partial differential equations. Composite iterative schemes, using inner-outer schemes in conjunction with Picard and Newton method, based on approximate inverse matrix techniques for solving non-linear boundary value problems, are presented. Additionally, isomorphic iterative methods are introduced for the efficient solution of non-linear systems. Explicit preconditioned conjugate gradient—type schemes in conjunction with approximate inverse matrix techniques are presented for the efficient solution of linear and non-linear system of algebraic equations. Theoretical estimates on the rate of convergence and computational complexity of the explicit preconditioned conjugate gradient method are also presented. Applications of the proposed methods on characteristic linear and non-linear problems are discussed and numerical results are given.     

Convergence analysis of Schwarz methods without overlap for the Helmholtz equation

In this paper, the continuous and discrete optimal transmission conditions for the Schwarz algorithm without overlap for the Helmholtz equation are studied. Since such transmission conditions lead to non-local operators, they are approximated through two different approaches. The first approach, called optimized, consists of an approximation of the optimal continuous transmission conditions with partial differential operators, which are then optimized for efficiency. The second approach, called approximated, is based on pure algebraic operations performed on the optimal discrete transmission conditions. After demonstrating the optimal convergence properties of the Schwarz algorithm new numerical investigations are performed on a wide range of unstructured meshes and arbitrary mesh partitioning with cross points. Numerical results illustrate for the first time the effectiveness, robustness and comparative performance of the optimized and approximated Schwarz methods on a model problem and on industrial problems.     

Exact boundary controllability of the second-order Maxwell system: Theory and numerical simulation

The exact controllability of the second order time-dependent Maxwell equations for the electric field is addressed through the Hilbert Uniqueness Method. A two-grid preconditioned conjugate gradient algorithm is employed to inverse the H.U.M. operator and to construct the numerical control. The underlying initial value problems are discretized by Lagrange finite elements and an implicit Newmark scheme. Two-dimensional numerical experiments illustrate the performance of the method.     

Domain Decomposition Algorithms for Two Dimensional Linear Schrödinger Equation

This paper deals with two domain decomposition methods for two dimensional linear Schrödinger equation, the Schwarz waveform relaxation method and the domain decomposition in space method. After presenting the classical algorithms, we propose a new algorithm for the Schrödinger equation with constant potential and a preconditioned algorithm for the general Schrödinger equation. These algorithms are then studied numerically. The numerical experiments show that the new algorithms can improve the convergence rate and reduce the computation time. Besides of the traditional Robin transmission condition, we also propose to use a newly constructed absorbing condition as the transmission condition.     

求解Maxwell线性元鞍点系统的基于HX预条件子的Uzawa算法

首先对含跳系数的H~1型和H(curl)型椭圆问题的线性有限元方程,分别设计了基于AMG预条件子和基于节点辅助空间预条件子(HX预条件子)的PCG法.数值实验表明,算法的迭代次数基本不依赖于系数跳幅和离散网格"尺寸".然后以此为基础,对Maxwell方程组鞍点问题的第一类N(e)d(e)lec线性棱元离散系统设计并分析了一种基于HX预条件子的Uzawa算法.当系数光滑时,理论上证明了算法的收敛率与网格规模无关.数值实验表明,新算法对跳系数情形也是高效和稳定的.     

A parallel polynomial Jacobi–Davidson approach for dissipative acoustic eigenvalue problems

We consider a rational algebraic large sparse eigenvalue problem arising in the discretization of the finite element method for the dissipative acoustic model in the pressure formulation. The presence of nonlinearity due to the frequency-dependent impedance poses a challenge in developing an efficient numerical algorithm for solving such eigenvalue problems. In this article, we reformulate the rational eigenvalue problem as a cubic eigenvalue problem and then solve the resulting cubic eigenvalue problem by a parallel restricted additive Schwarz preconditioned Jacobi–Davidson algorithm (ASPJD). To validate the ASPJD-based eigensolver, we numerically demonstrate the optimal convergence rate of our discretization scheme and show that ASPJD converges successfully to all target eigenvalues. The extraneous root introduced by the problem reformulation does not cause any observed side effect that produces an undesirable oscillatory convergence behavior. By performing intensive numerical experiments, we identify an efficient correction-equation solver, an effective algorithmic parameter setting, and an optimal mesh partitioning. Furthermore, the numerical results suggest that the ASPJD-based eigensolver with an optimal mesh partitioning results in superlinear scalability on a distributed and parallel computing cluster scaling up to 192 processors.     

Domain decomposition algorithms for spectral methods

In this paper we review some multiple-domain decomposition algorithrns for spectral methods. The alternating Schwarz algorithm and a flux preserving domain decomposition algorithm are considered. For both of them, some theoretical convergence results are given. These domain decomposition algorithms allow the use of iterative procedures for block matrices that can be efficiently implemented on parallel processors. Several numerical experiences based on the Chebyshev collocation method are carried out. A comparison of the performances of the two algorithms on several test problems is presented.     

Numerical assessment of a class of uniformly stable mixed spectral elements for the Navier-Stokes equations

In 1999, Bernardi and Maday analyzed a new class of mixed spectral elements for the Stokes and the Navier-Stokes equations [Bernardi C, Maday Y. Uniform Inf-Sup condition for the spectral discretization of the Stokes problem. Math Models Meth Appl Sci 1999;3:395-414] where they proved some interesting results like the uniform Inf-Sup condition. The main advantage we see is that applying the Uzawa algorithm to the discrete Stokes system yields a well-conditioned problem on the pressure. Then, the mass matrix preconditioned Conjugate Gradient method PCG used to compute the pressure converges in a number of iterations that is independent of the polynomial degree approximation. This paper presents the “numerical proofs” of the theoretical predictions on the stability and the accuracy of these spectral methods in mono-domain and multi-domain configurations.     

Single and multidomain Chebyshev collocation methods for the Korteweg-de Vries equation

We propose spectral Chebyshev collocation algorithms for the approximation of the initial and boundary value problem for the Korteweg-de Vries equation. Both single and multidomain approaches are discussed. Different methods for the treatment of the boundary conditions are considered. The numerical analysis of the eigenvalues' behaviour of the spectral differentiation operators involved in the approximation suggests appropriate finite difference methods for time-marching. Several numerical experiments have been performed, which prove spectral convergence and stability of the proposed schemes.     

Parallel Newton-Krylov-Schwarz algorithms for the three-dimensional Poisson-Boltzmann equation in numerical simulation of colloidal particle interactions

We investigate fully parallel Newton-Krylov-Schwarz (NKS) algorithms for solving the large sparse nonlinear systems of equations arising from the finite element discretization of the three-dimensional Poisson-Boltzmann equation (PBE), which is often used to describe the colloidal phenomena of an electric double layer around charged objects in colloidal and interfacial science. The NKS algorithm employs an inexact Newton method with backtracking (INB) as the nonlinear solver in conjunction with a Krylov subspace method as the linear solver for the corresponding Jacobian system. An overlapping Schwarz method as a preconditioner to accelerate the convergence of the linear solver. Two test cases including two isolated charged particles and two colloidal particles in a cylindrical pore are used as benchmark problems to validate the correctness of our parallel NKS-based PBE solver. In addition, a truly three-dimensional case, which models the interaction between two charged spherical particles within a rough charged micro-capillary, is simulated to demonstrate the applicability of our PBE solver to handle a problem with complex geometry. Finally, based on the result obtained from a PC cluster of parallel machines, we show numerically that NKS is quite suitable for the numerical simulation of interaction between colloidal particles, since NKS is robust in the sense that INB is able to converge within a small number of iterations regardless of the geometry, the mesh size, the number of processors. With help of an additive preconditioned Krylov subspace method NKS achieves parallel efficiency of 71% or better on up to a hundred processors for a 3D problem with 5 million unknowns.     

h-p Spectral Element Method for Elliptic Problems on Non-smooth Domains Using Parallel Computers

We propose a new h-p spectral element method to solve elliptic boundary value problems with mixed Neumann and Dirichlet boundary conditions on non-smooth domains. The method is shown to be exponentially accurate and asymptotically faster than the standard h-p finite element method. The spectral element functions are fully non-conforming for pure Dirichlet problems and conforming only at the vertices of the elements for mixed problems, and hence, the dimension of the resulting Schur complement matrix is quite small. The method is a least-squares collocation method and the resulting normal equations are solved using preconditioned conjugate gradient method with an almost optimal preconditioner. The algorithm is suitable for a distributed memory parallel computer. The numerical results of a number of model problems are presented, which confirm the theoretical estimates.