Some multilevel methods on graded meshes

We consider Yserentant's hierarchical basis method and multilevel diagonal scaling method on a class of refined meshes used in the numerical approximation of boundary value problems on polygonal domains in the presence of singularities. We show, as in the uniform case, that the stiffness matrix of the first method has a condition number bounded by (ln(1/h))², where h is the meshsize of the triangulation. For the second method, we show that the condition number of the iteration operator is bounded by ln(1/h), which is worse than in the uniform case but better than the hierarchical basis method. As usual, we deduce that the condition number of the BPX iteration operator is bounded by ln(1/h). Finally, graded meshes fulfilling the general conditions are presented and numerical tests are given which confirm the theoretical bounds.     

Preconditioners for pseudodifferential equations on the sphere with radial basis functions

In a previous paper a preconditioning strategy based on overlapping domain decomposition was applied to the Galerkin approximation of elliptic partial differential equations on the sphere. In this paper the methods are extended to more general pseudodifferential equations on the sphere, using as before spherical radial basis functions for the approximation space, and again preconditioning the ill-conditioned linear systems of the Galerkin approximation by the additive Schwarz method. Numerical results are presented for the case of hypersingular and weakly singular integral operators on the sphere \mathbbS²{\mathbb{S}^2} .     

The Petrov–Galerkin method for second kind integral equations II: multiwavelet schemes

This paper continues the theme of the recent work [Z. Chen and Y. Xu, The Petrov–Galerkin and iterated Petrov–Galerkin methods for second kind integral equations, SIAM J. Numer. Anal., to appear] and further develops the Petrov–Galerkin method for Fredholm integral equations of the second kind. Specifically, we study wavelet Petrov–Galerkin schemes based on discontinuous orthogonal multiwavelets and prove that the condition number of the coefficient matrix for the linear system obtained from the wavelet Petrov–Galerkin scheme is bounded. In addition, we propose a truncation strategy which forms a basis for fast wavelet algorithms and analyze the order of convergence and computational complexity of these algorithms. This revised version was published online in June 2006 with corrections to the Cover Date.     

Repeated Red-Black ordering: a new approach

Hereafter, we describe and analyze, from both a theoretical and a numerical point of view, an iterative method for efficiently solving symmetric elliptic problems with possibly discontinuous coefficients. In the following, we use the Preconditioned Conjugate Gradient method to solve the symmetric positive definite linear systems which arise from the finite element discretization of the problems. We focus our interest on sparse and efficient preconditioners. In order to define the preconditioners, we perform two steps: first we reorder the unknowns and then we carry out a (modified) incomplete factorization of the original matrix. We study numerically and theoretically two preconditioners, the second preconditioner corresponding to the one investigated by Brand and Heinemann [2]. We prove convergence results about the Poisson equation with either Dirichlet or periodic boundary conditions. For a meshsizeh, Brand proved that the condition number of the preconditioned system is bounded byO(h ^–1/2) for Dirichlet boundary conditions. By slightly modifying the preconditioning process, we prove that the condition number is bounded byO(h ^–1/3).     

A non-uniform basis order for the discontinuous Galerkin method of the acoustic and elastic wave equations

Here, we solve the time-dependent acoustic and elastic wave equations using the discontinuous Galerkin method for spatial discretization and the low-storage Runge-Kutta and Crank-Nicolson methods for time integration. The aim of the present paper is to study how to choose the order of polynomial basis functions for each element in the computational mesh to obtain a predetermined relative error. In this work, the formula 2p+1≈κhk, which connects the polynomial basis order p, mesh parameter h, wave number k, and free parameter κ, is studied. The aim is to obtain a simple selection method for the order of the basis functions so that a relatively constant error level of the solution can be achieved. The method is examined using numerical experiments. The results of the experiments indicate that this method is a promising approach for approximating the degree of the basis functions for an arbitrarily sized element. However, in certain model problems we show the failure of the proposed selection scheme. In such a case, the method provides an initial basis for a more general p-adaptive discontinuous Galerkin method.     

A preconditioner for the FETI-DP method for mortar-type Crouzeix-Raviart element discretization

In this paper, we consider mortar-type Crouzeix-Raviart element discretizations for second order elliptic problems with discontinuous coefficients. A preconditioner for the FETI-DP method is proposed. We prove that the condition number of the preconditioned operator is bounded by (1 + log(H/h))², where H and h are mesh sizes. Finally, numerical tests are presented to verify the theoretical results.     

Simulation of the interaction of light with 3-D metallic nanostructures using a proper orthogonal decomposition-Galerkin reduced-order discontinuous Galerkin time-domain method

In this artice, we report on a reduced-order model (ROM) based on the proper orthogonal decomposition (POD) technique for the system of 3-D time-domain Maxwell's equations coupled to a Drude dispersion model, which is employed to describe the interaction of light with nanometer scale metallic structures. By using the singular value decomposition (SVD) method, the POD basis vectors are extracted offline from the snapshots produced by a high order discontinuous Galerkin time-domain (DGTD) solver. With a Galerkin projection and a second order leap-frog (LF₂) time discretization, a discrete ROM is constructed. The stability condition of the ROM is then analyzed. In particular, when the boundary is a perfect electric conductor condition, the global energy of the ROM is bounded, which is consistent with the characteristics of global energy in the DGTD method. It is shown that the ROM based on Galerkin projection can maintain the stability characteristics of the original high dimensional model. Numerical experiments are presented to verify the accuracy, demonstrate the capabilities of the POD-based ROM and assess its efficiency for 3-D nanophotonic problems.     

Prewavelet analysis of the heat equation

Summary. We consider the heat equation in a smooth domain of R with Dirichlet and Neumann boundary conditions. It is solved by using its integral formulation with double-layer potentials, where the unknown , the jump of the solution through the boundary, belongs to an anisotropic Sobolev space. We approximate by the Galerkin method and use a prewavelet basis on , which characterizes the anisotropic space. The use of prewavelets allows to compress the stiffness matrix from to when N is the size of the matrix, and the condition number of the compressed matrix is uniformly bounded as the initial one in the prewavelet basis. Finally we show that the compressed scheme converges as fast as the Galerkin one, even for the Dirichlet problem which does not admit a coercive variational formulation. Received April 16, 1999 / Published online August 2, 2000     

Vanishing viscosity limit for a coupled Navier-Stokes/Allen-Cahn system

In this paper, we study the vanishing viscosity limit for a coupled Navier-Stokes/Allen-Cahn system in a bounded domain. We first show the local existence of smooth solutions of the Euler/Allen-Cahn equations by modified Galerkin method. Then using the boundary layer function to deal with the mismatch of the boundary conditions between Navier-Stokes and Euler equations, and assuming that the energy dissipation for Navier-Stokes equation in the boundary layer goes to zero as the viscosity tends to zero, we prove that the solutions of the Navier-Stokes/Allen-Cahn system converge to that of the Euler/Allen-Cahn system in a proper small time interval. In addition, for strong solutions of the Navier-Stokes/Allen-Cahn system in 2D, the convergence rate is cν1/2.     

An efficient linear solver for the hybridized discontinuous Galerkin method

Discretizing partial differential equations by an implicit solving technique ultimately leads to a linear system of equations that has to be solved. The number of globally coupled unknowns is especially large for discontinuous Galerkin (DG) methods. It can be reduced by using hybridized discontinuous Galerkin (HDG) methods, but still efficient linear solvers are needed. It has been shown that, if hierarchical basis functions are used, a hierarchical scale separation (HSS) ansatz can be an efficient solver. In this work, we couple the HDG method with an HSS solver to solve a scalar nonlinear problem. It is validated by comparing the results with results obtained by GMRES with ILU(3) preconditioning as linear solver. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Construction of a high order fluid-structure interaction solver

Accuracy is critical if we are to trust simulation predictions. In settings such as fluid-structure interaction, it is all the more important to obtain reliable results to understand, for example, the impact of pathologies on blood flows in the cardiovascular system. In this paper, we propose a computational strategy for simulating fluid structure interaction using high order methods in space and time.First, we present the mathematical and computational core framework, Life, underlying our multi-physics solvers. Life is a versatile library allowing for 1D, 2D and 3D partial differential solves using h/p type Galerkin methods. Then, we briefly describe the handling of high order geometry and the structure solver. Next we outline the high-order space-time approximation of the incompressible Navier-Stokes equations and comment on the algebraic system and the preconditioning strategy. Finally, we present the high-order Arbitrary Lagrangian Eulerian (ALE) framework in which we solve the fluid-structure interaction problem as well as some initial results.     

Stability analysis and a priori error estimate of explicit Runge-Kutta discontinuous Galerkin methods for correlated random walk with density-dependent turning rates

In this paper,we analyze the explicit Runge-Kutta discontinuous Galerkin(RKDG)methods for the semilinear hyperbolic system of a correlated random walk model describing movement of animals and cells in biology.The RKDG methods use a third order explicit total-variation-diminishing Runge-Kutta(TVDRK3)time discretization and upwinding numerical fluxes.By using the energy method,under a standard CourantFriedrichs-Lewy(CFL)condition,we obtain L2stability for general solutions and a priori error estimates when the solutions are smooth enough.The theoretical results are proved for piecewise polynomials with any degree k 1.Finally,since the solutions to this system are non-negative,we discuss a positivity-preserving limiter to preserve positivity without compromising accuracy.Numerical results are provided to demonstrate these RKDG methods.     

Discrete boundary element methods on general meshes in 3D

Abstract. This paper is concerned with the stability and convergence of fully discrete Galerkin methods for boundary integral equations on bounded piecewise smooth surfaces in . Our theory covers equations with very general operators, provided the associated weak form is bounded and elliptic on , for some . In contrast to other studies on this topic, we do not assume our meshes to be quasiuniform, and therefore the analysis admits locally refined meshes. To achieve such generality, standard inverse estimates for the quasiuniform case are replaced by appropriate generalised estimates which hold even in the locally refined case. Since the approximation of singular integrals on or near the diagonal of the Galerkin matrix has been well-analysed previously, this paper deals only with errors in the integration of the nearly singular and smooth Galerkin integrals which comprise the dominant part of the matrix. Our results show how accurate the quadrature rules must be in order that the resulting discrete Galerkin method enjoys the same stability properties and convergence rates as the true Galerkin method. Although this study considers only continuous piecewise linear basis functions on triangles, our approach is not restricted in principle to this case. As an example, the theory is applied here to conventional “triangle-based” quadrature rules which are commonly used in practice. A subsequent paper [14] introduces a new and much more efficient “node-based” approach and analyses it using the results of the present paper. Received December 10, 1997 / Revised version received May 26, 1999 / Published online April 20, 2000 –? Springer-Verlag 2000     

A generalization of de Boor’s stability result and symmetric preconditioning

We provide a symmetric preconditioning method based on weighted divided differences which can be applied in order to solve certain ill-conditioned scattered-data interpolation problems in a stable way; more precisely, our method applies to cases where the ill-conditioning comes from the fact that the basis function is slowly growing, and the number of interpolation points is large. Concerning the theoretical background, an a priori unbounded operator on ?₂(?) is preconditioned so as to get a bounded and coercive operator. The method has another and probably even more interesting interpretation in terms of constructing certain Riesz bases of appropriate closed subspaces ofL ₂(?). In extending Mallat’s multiresolution analysis to the scattered data case, we construct nested sequences of spaces giving rise to orthogonal decompositions of functions inL ₂(?); in this way the idea of wavelet decompositions is (theoretically) carried over to scattered-data methods.     

An augmented mixed finite element method for 3D linear elasticity problems

In this paper we introduce and analyze a new augmented mixed finite element method for linear elasticity problems in 3D. Our approach is an extension of a technique developed recently for plane elasticity, which is based on the introduction of consistent terms of Galerkin least-squares type. We consider non-homogeneous and homogeneous Dirichlet boundary conditions and prove that the resulting augmented variational formulations lead to strongly coercive bilinear forms. In this way, the associated Galerkin schemes become well posed for arbitrary choices of the corresponding finite element subspaces. In particular, Raviart-Thomas spaces of order 0 for the stress tensor, continuous piecewise linear elements for the displacement, and piecewise constants for the rotation can be utilized. Moreover, we show that in this case the number of unknowns behaves approximately as 9.5 times the number of elements (tetrahedrons) of the triangulation, which is cheaper, by a factor of 3, than the classical PEERS in 3D. Several numerical results illustrating the good performance of the augmented schemes are provided.     

Condition number of the stiffness matrix arising in POD Galerkin schemes for dynamical systems

Proper orthogonal decomposition (POD) provides a method for deriving low order models of non‐linear dynamical systems, where a so‐called POD basis is computed by a singular value decomposition and these basis functions are used in a Galerkin ansatz for the non‐linear dynamics. In this paper we prove estimates for the condition number of the stiffness matrices arising in the POD Galerkin discretization. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Stochastic Galerkin techniques for random ordinary differential equations

Over the last decade the stochastic Galerkin method has become an established method to solve differential equations involving uncertain parameters. It is based on the generalized Wiener expansion of square integrable random variables. Although there exist very sophisticated variants of the stochastic Galerkin method (wavelet basis, multi-element approach) convergence for random ordinary differential equations has rarely been considered analytically. In this work we develop an asymptotic upper boundary for the L ₂-error of the stochastic Galerkin method. Furthermore, we prove convergence of a local application of the stochastic Galerkin method and confirm convergence of the multi-element approach within this context.     

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     

The method of boundary integral equations for a mixed scattering problem

In this paper we consider the scattering of an electromagnetic time-harmonic plane wave by an infinite cylinder having an open arc and a bounded domain in R² as cross section. To this end, we solve a scattering problem for the Helmholtz equation in R² where the scattering object is a combination of a crack Γ and a bounded obstacle D, and we have Dirichlet-impedance type boundary condition on Γ and Dirichlet boundary condition on ∂D (∂D∈C²). Applying potential theory, the problem can be reformulated as a boundary integral system. We establish the existence and uniqueness of a solution to the system by using the Fredholm theory.     

A hierarchical basis preconditioner for the biharmonic equation on the sphere

^** Email: jan.maes{at}cs.kuleuven.be In this paper, we propose a natural way to extend a bivariatePowell–Sabin (PS) B-spline basis on a planar polygonaldomain to a PS B-spline basis defined on a subset of the unitsphere in [graphic: see PDF] . The spherical basis inherits many properties of the bivariatebasis such as local support, the partition of unity propertyand stability. This allows us to construct a C¹ continuous hierarchicalbasis on the sphere that is suitable for preconditioning fourth-orderelliptic problems on the sphere. We show that the stiffnessmatrix relative to this hierarchical basis has a logarithmicallygrowing condition number, which is a suboptimal result comparedto standard multigrid methods. Nevertheless, this is a hugeimprovement over solving the discretized system without preconditioning,and its extreme simplicity contributes to its attractiveness.Furthermore, we briefly describe a way to stabilize the hierarchicalbasis with the aid of the lifting scheme. This yields a waveletbasis on the sphere for which we find a uniformly well-conditionedand (quasi-) sparse stiffness matrix.