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

A Cascadic Multigrid Algorithm for Semilinear Indefinite Elliptic Problems

We propose a cascadic multigrid algorithm for a semilinear indefinite elliptic problem. We use a standard finite element discretization with piecewise linear finite elements. The arising nonlinear equations are solved by a cascadic organization of Newton's method with frozen derivative on a sequence of nested grids. This gives a simple version of a multigrid method without projections on coarser grids. The cascadic multigrid algorithm starts on a comparatively coarse grid where the number of unknowns is small enough to obtain an approximate solution within sufficiently high precision without substantial computational effort. On each finer grid we perform exactly one Newton step taking the approximate solution from the coarsest grid as initial guess. The linear Newton systems are solved iteratively by a Jacobi-type iteration with special parameters using the approximate solution from the previous grid as initial guess. We prove that for a sufficiently fine initial grid and for a sufficiently good start approximation the algorithm yields an approximate solution within the discretization error on the finest grid and that the method has multigrid complexity with logarithmic multiplier. Received February 1999, revised July 13, 1999     

Fourier transform on sparse grids: Code design and the time dependent Schrödinger equation

The pseudo-spectral method together with a Strang-splitting are well suited for the discretization of the time-dependent Schrödinger equation with smooth potential. The curse of dimensionality limits this approach to low dimensions, if we stick to full grids. Theoretically, sparse grids allow accurate computations in (moderately) higher dimensions, provided that we supply an efficient Fourier transform. Motivated by this application, the design of the Fourier transform on sparse grids in multiple dimensions is described in detail. The focus of this presentation is on issues of flexible implementation and numerical studies of the convergence.     

A Proof of the Consistency of the Finite Difference Technique on Sparse Grids

In this paper, we give a proof of the consistency of the finite difference technique on regular sparse grids [7, 18]. We introduce an extrapolation-type discretization of differential operators on sparse grids based on the idea of the combination technique and we show the consistency of this discretization. The equivalence of the new method with that of [7, 18] is established. Received February 8, 2000; revised June 8, 2000     

An Algebraic Multigrid Method for Higher-order Finite Element Discretizations

In this paper, we will design and analyze a class of new algebraic multigrid methods for algebraic systems arising from the discretization of second order elliptic boundary value problems by high-order finite element methods. For a given sparse stiffness matrix from a quadratic or cubic Lagrangian finite element discretization, an algebraic approach is carefully designed to recover the stiffness matrix associated with the linear finite element disretization on the same underlying (but nevertheless unknown to the user) finite element grid. With any given classical algebraic multigrid solver for linear finite element stiffness matrix, a corresponding algebraic multigrid method can then be designed for the quadratic or higher order finite element stiffness matrix by combining with a standard smoother for the original system. This method is designed under the assumption that the sparse matrix to be solved is associated with a specific higher order, quadratic for example, finite element discretization on a finite element grid but the geometric data for the underlying grid is unknown. The resulting new algebraic multigrid method is shown, by numerical experiments, to be much more efficient than the classical algebraic multigrid method which is directly applied to the high-order finite element matrix. Some theoretical analysis is also provided for the convergence of the new method.     

Semi-Unstructured Grids

We present a novel automatic grid generator for the finite element discretization of partial differential equations in 3D. The grids constructed by this grid generator are composed of a pure tensor product grid in the interior of the domain and an unstructured grid which is only contained in boundary cells. The unstructured component consists of tetrahedra, each of which satisfies a maximal interior angle condition. By suitable constructing the boundary cells, the number of types of boundary subcells is reduced to 12 types. Since this grid generator constructs large structured grids in the interior and small unstructured grids near the boundary, the resulting semi-unstructured grids have similar properties as structured tensor product grids. Some appealing properties of this method are computational efficiency and natural construction of coarse grids for multilevel algorithms. Numerical results and an analysis of the discretization error are presented. Received July 17, 2000; revised October 27, 2000     

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.     

Numerical Integrations and Unit Resolution Multipliers for Domain Decomposition Methods with Nonmatching Grids

In this paper, we are concerned with the non-overlapping domain decomposition method (DDM) with nonmatching grids for three-dimensional problems. The weak continuity of the DDM solution on the interface is imposed by some Lagrange multiplier. We shall first analyze the influence of the numerical integrations over the interface on the (non-conforming) approximate solution. Then we will propose a simple approach to construct multiplier spaces, one of which can be simply spanned by some smooth basis functions with local compact supports, and thus makes the numerical integrations on the interface rather simple and inexpensive. Also it is shown this multiplier space can generate an optimal approximate solution. Numerical results are presented to compare the new method with the point to point method widely used in engineering.     

Multigrid for Discrete Differential Forms on Sparse Grids

Discrete differential forms are a generalization of the common H¹()-conforming Lagrangian elements. For the latter, Galerkin schemes based on sparse grids are well known, and so are fast iterative multilevel solvers for the discrete Galerkin equations. We extend both the sparse grid idea and the design of multilevel methods to arbitrary discrete differential forms. The focus of this presentation will be on issues of efficient implementation and numerical studies of convergence of multigrid solvers.     

On the reference mapping for quadrilateral and hexahedral finite elements on multilevel adaptive grids

We study the properties of the reference mapping for quadrilateral and hexahedral finite elements. We consider multilevel adaptive grids with possibly hanging nodes which are typically generated by adaptive refinement starting from a regular coarse grid. It turns out that for such grids the reference mapping behaves – up to a perturbation depending on the mesh size – like an affine mapping. As an application, we prove optimal estimates of the interpolation error for discontinuous mapped -elements on quadrilateral and hexahedral grids.     

Boundary Element Tearing and Interconnecting Methods

In this paper we introduce the Boundary Element Tearing and Interconnecting (BETI) methods as boundary element counterparts of the well-established Finite Element Tearing and Interconnecting (FETI) methods. In some practical important applications such as far field computations, handling of singularities and moving parts etc., BETI methods have certainly some advantages over their finite element counterparts. This claim is especially true for the sparse versions of the BETI preconditioners resp. methods. Moreover, there is an unified framework for coupling, handling, and analyzing both methods. In particular, the FETI methods can benefit from preconditioning components constructed by boundary element techniques. The first numerical results confirm the efficiency and the robustness predicted by our analysis.     

Multivariate Quadrature on Adaptive Sparse Grids

In this paper, we study the potential of adaptive sparse grids for multivariate numerical quadrature in the moderate or high dimensional case, i. e. for a number of dimensions beyond three and up to several hundreds. There, conventional methods typically suffer from the curse of dimension or are unsatisfactory with respect to accuracy. Our sparse grid approach, based upon a direct higher order discretization on the sparse grid, overcomes this dilemma to some extent, and introduces additional flexibility with respect to both the order of the 1 D quadrature rule applied (in the sense of Smolyak's tensor product decomposition) and the placement of grid points. The presented algorithm is applied to some test problems and compared with other existing methods.     

Data Mining with Sparse Grids

O (h _n ⁻¹ n ^{d −1}) instead of O(h _n ^−d ) grid points and unknowns are involved. Here d denotes the dimension of the feature space and h _n = 2 ⁻ⁿ gives the mesh size. To be precise, we suggest to use the sparse grid combination technique [42] where the classification problem is discretized and solved on a certain sequence of conventional grids with uniform mesh sizes in each coordinate direction. The sparse grid solution is then obtained from the solutions on these different grids by linear combination. In contrast to other sparse grid techniques, the combination method is simpler to use and can be parallelized in a natural and straightforward way. We describe the sparse grid combination technique for the classification problem in terms of the regularization network approach. We then give implementational details and discuss the complexity of the algorithm. It turns out that the method scales only linearly with the number of instances, i.e. the amount of data to be classified. Finally we report on the quality of the classifier built by our new method. Here we consider standard test problems from the UCI repository and problems with huge synthetical data sets in up to 9 dimensions. It turns out that our new method achieves correctness rates which are competitive to that of the best existing methods. Received April 25, 2001     

Sparse Grids, Adaptivity, and Symmetry

Sparse grid methods represent a powerful and efficient technique for the representation and approximation of functions and particularly the solutions of partial differential equations in moderately high space dimensions. To extend the approach to truly high-dimensional problems as they arise in quantum chemistry, an additional property has to be brought into play, the symmetry or antisymmetry of the functions sought there. In the present article, an adaptive sparse grid refinement scheme is developed that takes full advantage of such symmetry properties and for which the amount of work and storage remains strictly proportional to the number of degrees of freedom. To overcome the problems with the approximation of the inherently complex antisymmetric functions, augmented sparse grid spaces are proposed.     

Using integral equations and the immersed interface method to solve immersed boundary problems with stiff forces

We propose a fast, explicit numerical method for computing approximations for the immersed boundary problem in which the boundaries that separate the fluid into two regions are stiff. In the numerical computations of such problems, one frequently has to contend with numerical instability, as the stiff immersed boundaries exert large forces on the local fluid. When the boundary forces are treated explicitly, prohibitively small time-steps may be required to maintain numerical stability. On the other hand, when the boundary forces are treated implicitly, the restriction on the time-step size is reduced, but the solution of a large system of coupled non-linear equations may be required. In this work, we develop an efficient method that combines an integral equation approach with the immersed interface method. The present method treats the boundary forces explicitly. To reduce computational costs, the method uses an operator-splitting approach: large time-steps are used to update the non-stiff advection terms, and smaller substeps are used to advance the stiff boundary. At each substep, an integral equation is computed to yield fluid velocity local to the boundary; those velocity values are then used to update the boundary configuration. Fluid variables are computed over the entire domain, using the immersed interface method, only at the end of the large advection time-steps. Numerical results suggest that the present method compares favorably with an implementation of the immersed interface method that employs an explicit time-stepping and no fractional stepping.     

Fast Fluid Simulations with Sparse Volumes on the GPU

We introduce efficient, large scale fluid simulation on GPU hardware using the fluid‐implicit particle (FLIP) method over a sparse hierarchy of grids represented in NVIDIA^® GVDB Voxels. Our approach handles tens of millions of particles within a virtually unbounded simulation domain. We describe novel techniques for parallel sparse grid hierarchy construction and fast incremental updates on the GPU for moving particles. In addition, our FLIP technique introduces sparse, work efficient parallel data gathering from particle to voxel, and a matrix‐free GPU‐based conjugate gradient solver optimized for sparse grids. Our results show that our method can achieve up to an order of magnitude faster simulations on the GPU as compared to FLIP simulations running on the CPU.     

Solving large sparse linear systems in a grid environment: the GREMLINS code versus the PETSc library

Solving large sparse linear systems is essential in numerous scientific domains. Several algorithms, based on direct or iterative methods, have been developed for parallel architectures. On distributed grids consisting of processors located in distant geographical sites, their performance may be unsatisfactory because they suffer from too many synchronizations and communications. The GREMLINS code has been developed for solving large sparse linear systems on distributed grids. It implements the multisplitting method that consists in splitting the original linear system into several subsystems that can be solved independently. In this paper, the performance of the GREMLINS code obtained with several libraries for solving the linear subsystems is analyzed. Its performance is also compared with that of the widely used PETSc library that enables one to develop portable parallel applications. Numerical experiments have been carried out both on local clusters and on distributed grids.     

Condition Numbers of Approximate Schur Complements in Two- and Three-Dimensional Discretizations on Hierarchically Ordered Grids

We investigate multilevel incomplete factorizations of M-matrices arising from finite difference discretizations. The nonzero patterns are based on special orderings of the grid points. Hence, the Schur complements that result from block elimination of unknowns refer to a sequence of hierarchical grids. Having reached the coarsest grid, Gaussian elimination yields a complete decomposition of the last Schur complement. The main focus of this paper is a generalization of the recursive five-point/nine-point factorization method (which can be applied in two-dimensional problems) to matrices that stem from discretizations on three-dimensional cartesian grids. Moreover, we present a local analysis that considers fundamental grid cells. Our analysis allows to derive sharp bounds for the condition number associated with one factorization level (two-grid estimates). A comparison in case of the Laplace operator with Dirichlet boundary conditions shows: Estimating the relative condition number of the multilevel preconditioner by multiplying corresponding two-grid values gives the asymptotic bound O(h ^−0.347) for the two- respectively O(h ^−4/5) for the three-dimensional model problem. Received October 19, 1998; revised September 27, 1999     

Application of an Adaptive Sparse-Grid Technique to a Model Singular Perturbation Problem

In this paper we show how, under minimal conditions, a combination extrapolation can be introduced for an adaptive sparse grid. We apply this technique for the solution of a two-dimensional model singular perturbation problem, defined on the domain exterior of a circle. Received October 18, 1999     

A Multigrid Method for Nonconforming FE-Discretisations with Application to Non-Matching Grids

Nonconforming finite element discretisations require special care in the construction of the prolongation and restriction in the multigrid process. In this paper, a general scheme is proposed, which guarantees the approximation property. As an example, the technique is applied to the discretisation by non-matching grids (mortar elements). Received: October 15, 1998