Some schwarz methods for integral equations on surfaces-h and p versions

Abstact We present new results from 11, 7, 12 on various Schwarz methods for the h and p versions of the boundary element methods applied to prototype first kind integral equations on surfaces. When those integral equations (weakly/hypersingular) are solved numerically by the Galerkin boundary element method, the resulting matrices become ill-conditioned. Hence, for an efficient solution procedure appropriate preconditioners are necessary to reduce the numbers of CG-iterations. In the p version where accuracy of the Galerkin solution is achieved by increasing the polynomial degree the use of suitable Schwarz preconditioners (presented in the paper) leads to only polylogarithmically growing condition numbers. For the h version where accuracy is achieved by reducing the mesh size we present a multi-level additive Schwarz method which is competitive with the multigrid method. Communicated by: U. Langer Dedicated to George C. Hsiao on the occasion of his 70th birthday.     

Multigrid Methods for the Stokes Equations using Distributive Gauss–Seidel Relaxations based on the Least Squares Commutator

A distributive Gauss–Seidel relaxation based on the least squares commutator is devised for the saddle-point systems arising from the discretized Stokes equations. Based on that, an efficient multigrid method is developed for finite element discretizations of the Stokes equations on both structured grids and unstructured grids. On rectangular grids, an auxiliary space multigrid method using one multigrid cycle for the Marker and Cell scheme as auxiliary space correction and least squares commutator distributive Gauss–Seidel relaxation as a smoother is shown to be very efficient and outperforms the popular block preconditioned Krylov subspace methods.     

On the numerical modeling of convection-diffusion problems by finite element multigrid preconditioning methods

During the last decades, multigrid methods have been extensively used in order to solve large scale linear systems derived from the discretization of partial differential equations using the finite difference method. The effectiveness of the multigrid method can be also exploited by using the finite element method. Finite Element Approximate Inverses in conjunction with Richardon’s iterative method could be used as smoothers in the multigrid method. Thus, a new class of smoothers based on approximate inverses can be derived. Effectiveness of explicit approximate inverses relies in the fact that they are close approximants to the inverse of the coefficient matrix and are fast to compute in parallel. Furthermore, the proposed class of finite element approximate inverses in conjunction with the explicit preconditioned Richardson method yield improved results against the classic smoothers such as Jacobi method. Moreover, a dynamic relaxation scheme is proposed based on the Dynamic Over/Under Relaxation (DOUR) algorithm. Furthermore, results for multigrid preconditioned Krylov subspace methods, such as GMRES(res), IDR(s) and BiCGSTAB based on approximate inverse smoothing and a dynamic relaxation technique are presented for the steady-state convection-diffusion equation.     

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.     

Composite Finite Elements for Elliptic Boundary Value Problems with Discontinuous Coefficients

In this paper, we will introduce composite finite elements for solving elliptic boundary value problems with discontinuous coefficients. The focus is on problems where the geometry of the interfaces between the smooth regions of the coefficients is very complicated. On the other hand, efficient numerical methods such as, e.g., multigrid methods, wavelets, extrapolation, are based on a multi-scale discretization of the problem. In standard finite element methods, the grids have to resolve the structure of the discontinuous coefficients. Thus, straightforward coarse scale discretizations of problems with complicated coefficient jumps are not obvious. In this paper, we define composite finite elements for problems with discontinuous coefficients. These finite elements allow the coarsening of finite element spaces independently of the structure of the discontinuous coefficients. Thus, the multigrid method can be applied to solve the linear system on the fine scale. We focus on the construction of the composite finite elements and the efficient, hierarchical realization of the intergrid transfer operators. Finally, we present some numerical results for the multigrid method based on the composite finite elements (CFE–MG).     

Spectral element multigrid. I. Formulation and numerical results

A variational spectral element multigrid algorithm is proposed, and results are presented for a one-dimensional Poisson equation on a finite interval. The key features of the proposed algorithm are as follows: the nested spaces and associated hierarchical bases are intra-element, resulting in simple data structures and rapid tensor-product sum-factorization evaluations; smoothing is effected by readily constructed and efficiently inverted (diagonal) Jacobi preconditioners; the technique is readily parallelized within the context of a medium-grained paradigm; and the (work-deflated) multigrid convergence rate is bounded from above well below unity, and is only a weak function of the number of spectral elementsK, the (large) order of the polynomial approximation,N, and the number of multigrid levels,J. Preliminary tests indicate that these convergence properties persist in higher space dimensions.     

求解半线性椭圆型方程组的并行算法

本文结合区域分裂技术、多重网格方法、加速Ｓｃｈｗａｒｚ收敛方法、高低解方法、非线性Ｊａｃｏｂｉ迭代方法和Ｎｅｗｔｏｎ线性化迭代方法,设计了三种求解半线性椭圆型方程（组）的并行算法：并行Ｎｅｗｔｏｎ多重网格算法、并行非线性多重网格算法和并行加速Ｓｃｈｗａｒｚ收敛算法。数值试验说明这三种算法的并行计算是可行的。     

An efficient algebraic multigrid preconditioner for a fast multipole boundary element method

Fast boundary element methods still need good preconditioning techniques for an almost optimal complexity. An algebraic multigrid method is presented for the single layer potential using the fast multipole method. The coarsening is based on the cluster structure of the fast multipole method. The effort for the construction of the nearfield part of the coarse grid matrices and for an application of the multigrid preconditioner is of the same almost optimal order as the fast multipole method itself.     

Parallel Domain Decomposition Methods with Mixed Order Discretization for Fully Implicit Solution of Tracer Transport Problems on the Cubed-Sphere

In this paper, a fully implicit finite volume Eulerian scheme and a corresponding scalable parallel solver are developed for some tracer transport problems on the cubed-sphere. To efficiently solve the large sparse linear system at each time step on parallel computers, we introduce a Schwarz preconditioned Krylov subspace method using two discretizations. More precisely speaking, the higher order method is used for the residual calculation and the lower order method is used for the construction of the preconditioner. The matrices from the two discretizations have similar sparsity pattern and eigenvalue distributions, but the matrix from the lower order method is a lot sparser, as a result, excellent scalability results (in total computing time and the number of iterations) are obtained. Even though Schwarz preconditioner is originally designed for elliptic problems, our experiments indicate clearly that the method scales well for this class of purely hyperbolic problems. In addition, we show numerically that the proposed method is highly scalable in terms of both strong and weak scalabilities on a supercomputer with thousands of processors.     

Robust Multigrid Methods for Nearly Incompressible Elasticity

We consider multigrid methods for problems in linear elasticity which are robust with respect to the Poisson ratio. Therefore, we consider mixed approximations involving the displacement vector and the pressure, where the pressure is approximated by discontinuous functions. Then, the pressure can be eliminated by static condensation. The method is based on a saddle point smoother which was introduced for the Stokes problem and which is transferred to the elasticity system. The performance and the robustness of the multigrid method are demonstrated on several examples with different discretizations in 2D and 3D. Furthermore, we compare the multigrid method for the saddle point formulation and for the condensed positive definite system. Received February 5, 1999; revised October 5, 1999     

Schwarz algorithms for the Raviart-Thomas mixed method

A multiplicative and an additive versions of the Schwarz method are developed for the bidimensional Raviart-Thomas mixed finite element. The algorithm and the convergence analysis are based on the equivalence between Raviart-Thomas mixed methods and certain nonconfirming methods.     

Algebraic Multigrid Based on Computational Molecules, 1: Scalar Elliptic Problems

We consider the problem of splitting a symmetric positive definite (SPD) stiffness matrix A arising from finite element discretization into a sum of edge matrices thereby assuming that A is given as the sum of symmetric positive semidefinite (SPSD) element matrices. We give necessary and sufficient conditions for the existence of an exact splitting into SPSD edge matrices and address the problem of best positive (nonnegative) approximation. Based on this disassembling process we present a new concept of ``strong' and ``weak' connections (edges), which provides a basis for selecting the coarse-grid nodes in algebraic multigrid methods. Furthermore, we examine the utilization of computational molecules (small collections of edge matrices) for deriving interpolation rules. The reproduction of edge matrices on coarse levels offers the opportunity to combine classical coarsening algorithms with effective (energy minimizing) interpolation principles yielding a flexible and robust new variant of AMG.     

Coupled algebraic multigrid methods for the Oseen problem

We provide a concept combining techniques known from geometric multigrid methods for saddle point problems (such as smoothing iterations of Braess- or Vanka-type) and from algebraic multigrid (AMG) methods for scalar problems (such as the construction of coarse levels) to a coupled algebraic multigrid solver. Coupled here is meant in contrast to methods, where pressure and velocity equations are iteratively decoupled (pressure correction methods) and standard AMG is used for the solution of the resulting scalar problems. To prove the efficiency of our solver experimentally, it is applied to finite element discretizations of real life industrial problems.     

A multilevel hybrid Newton–Krylov–Schwarz method for the Bidomain model of electrocardiology

A multilevel hybrid Newton–Krylov–Schwarz (NKS) method is constructed and studied numerically for implicit time discretizations of the Bidomain reaction–diffusion system in three dimensions. This model describes the bioelectrical activity of the heart by coupling two degenerate parabolic equations with a stiff system of ordinary differential equations. The NKS Bidomain solver employs an outer inexact Newton iteration to solve the nonlinear finite element system originating at each time step of the implicit discretization. The Jacobian update during the Newton iteration is solved by a Krylov method employing a multilevel hybrid overlapping Schwarz preconditioner, additive within the levels and multiplicative among the levels. Several parallel tests on Linux clusters are performed, showing that the convergence of the method is independent of the number of subdomains (scalability), the discretization parameters and the number of levels (optimality).     

Optimized Schwarz method without overlap for the gravitational potential equation on cluster of graphics processing unit

Many engineering and scientific problems need to solve boundary value problems for partial differential equations or systems of them. For most cases, to obtain the solution with desired precision and in acceptable time, the only practical way is to harness the power of parallel processing. In this paper, we present some effective applications of parallel processing based on hybrid CPU/GPU domain decomposition method. Within the family of domain decomposition methods, the so-called optimized Schwarz methods have proven to have good convergence behaviour compared to classical Schwarz methods. The price for this feature is the need to transfer more physical information between subdomain interfaces. For solving large systems of linear algebraic equations resulting from the finite element discretization of the subproblem for each subdomain, Krylov method is often a good choice. Since the overall efficiency of such methods depends on effective calculation of sparse matrix–vector product, approaches that use graphics processing unit (GPU) instead of central processing unit (CPU) for such task look very promising. In this paper, we discuss effective implementation of algebraic operations for iterative Krylov methods on GPU. In order to ensure good performance for the non-overlapping Schwarz method, we propose to use optimized conditions obtained by a stochastic technique based on the covariance matrix adaptation evolution strategy. The performance, robustness, and accuracy of the proposed approach are demonstrated for the solution of the gravitational potential equation for the data acquired from the geological survey of Chicxulub crater.     

Computing Interpolation Weights in AMG Based on Multilevel Schur Complements

This paper presents a particular construction of neighborhood matrices to be used in the computation of the interpolation weights in AMG (algebraic multigrid). The method utilizes the existence of simple interpolation matrices (piecewise constant for example) on a hierarchy of coarse spaces (grids). Then one constructs by algebraic means graded away coarse spaces for any given fine-grid neighborhood. Next, the corresponding stiffness matrix is computed on this graded away mesh, and the actual neighborhood matrix is obtained by computing the multilevel Schur complement of this matrix where degrees of freedom outside the neighborhood have to be eliminated. The paper presents algorithmic details, provides model complexity analysis as well as some comparative tests of the quality of the resulting interpolation based on the multilevel Schur complements versus element interpolation based on the true element matrices.     

Interior point multigrid methods for topology optimization

In this paper, a new multigrid interior point approach to topology optimization problems in the context of the homogenization method is presented. The key observation is that nonlinear interior point methods lead to linear-quadratic subproblems with structures that can be favourably exploited within multigrid methods. Primal as well as primal-dual formulations are discussed. The multigrid approach is based on the transformed smoother paradigm. Numerical results for an example problem are presented. Received February 15, 1999     

A comparison of some standard elliptic solvers: CM-5 vs. Cray C-90

The implementations of the domain decomposition, SOR, multigrid and conjugate gradient method on CM-5 and Cray C-90 are described for the Laplace's equation on the unit square and L-shaped region. Domain decomposition method uses the Schwarz alternating method. In each domain we take the one-dimensional FFT to convert the problem into the tridiagonal systems which are solved by the scientific libraries installed in the CM-5 and the Cray C-90. On the CM-5 the V-cycle multigrid with symmetric smoothings on P-1 finite element spaces is run with red/black Gauss-Seidel relaxation. Multigrid with natural order Gauss-Seidel relaxation is used on the Cray C-90. While natural order SOR is used in the Cray C-90, R/B SOR is performed on the CM-5. Multigrid is the fastest method on the CM-5 and three methods except SOR give similar performances on Cray C-90.This research was partially supported by the National Science Foundation under Grant No. CDA-9024618.     

A real-time multigrid finite hexahedra method for elasticity simulation using CUDA

We present a multigrid approach for simulating elastic deformable objects in real time on recent NVIDIA GPU architectures. To accurately simulate large deformations we consider the co-rotated strain formulation. Our method is based on a finite element discretization of the deformable object using hexahedra. It draws upon recent work on multigrid schemes for the efficient numerical solution of partial differential equations on such discretizations. Due to the regular shape of the numerical stencil induced by the hexahedral regime, and since we use matrix-free formulations of all multigrid steps, computations and data layout can be restructured to avoid execution divergence of parallel running threads and to enable coalescing of memory accesses into single memory transactions. This enables to effectively exploit the GPU’s parallel processing units and high memory bandwidth via the CUDA parallel programming API. We demonstrate performance gains of up to a factor of 27 and 4 compared to a highly optimized CPU implementation on a single CPU core and 8 CPU cores, respectively. For hexahedral models consisting of as many as 269,000 elements our approach achieves physics-based simulation at 11 time steps per second.     

High-order FEM domain decomposition models for high-frequency wave propagation in heterogeneous media

Large scale scientific computing models, requiring iterative algebraic solvers, are needed to simulate high-frequency wave propagation because large degrees of freedom are needed to avoid the Helmholtz computer model pollution effects. In this work, we investigate the use of multiple additive Schwarz type domain decomposition (DD) approximations to efficiently simulate two- and three-dimensional high-frequency wave propagation with high-order FEM. We compare our DD based results with those obtained using a standard geometric multigrid approach for up to 1,000 and $300$ wavelength models in two- and three-dimensions, respectively.