In this paper, we consider the linear convectiondiffusion equation in one dimension with periodic boundary conditions, and analyze the stability of fully discrete methods that are defined with local discontinuous Galerkin (LDG) methods in space and several implicitexplicit (IMEX) RungeKutta methods in time. By using the forward temporal differences and backward temporal differences, respectively, we establish two general frameworks of the energymethod based stability analysis. From here, the fully discrete schemes being considered are shown to have monotonicity stability, i.e. the
Natural Boundary Conditions for Smoothing in Geometry Processing
We propose using a different smoothness energy, the Hessian energy, whose natural boundary conditions avoid this bias.In geometry processing, smoothness energies are commonly used to model scattered data interpolation, dense data denoising, and regularization during shape optimization. The squared Laplacian energy is a popular choice of energy and has a corresponding standard implementation: squaring the discrete Laplacian matrix. For compact domains, when values along the boundary are not known in advance, this construction bakes in loworder boundary conditions. This causes the geometric shape of the boundary to strongly bias the solution. For many applications, this is undesirable.Instead, we propose using the squared Frobenius norm of the Hessian as a smoothness energy. Unlike the squared Laplacian energy, this energy’s natural boundary conditions(those that best minimize the energy) correspond to meaningful highorder boundary conditions. These boundary conditions model free boundaries where the shape of the boundary should not bias the solution locally. Our analysis begins in the smooth setting and concludes with discretizations using finitedifferences on 2D grids or mixed fnite elements for triangle meshes. We demonstrate the core behavior of the squared Hessian as a smoothness energy for various tasks.
more »
« less
 NSFPAR ID:
 10079219
 Date Published:
 Journal Name:
 ACM transactions on graphics
 Volume:
 9
 Issue:
 4
 ISSN:
 07300301
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

$L^2$ norm of the numerical solution does not increase in time, under the time step condition$\tau \le \mathcal {F}(h/c, d/c^2)$ , with the convection coefficient$c$ , the diffusion coefficient$d$ , and the mesh size$h$ . The function$\mathcal {F}$ depends on the specific IMEX temporal method, the polynomial degree$k$ of the discrete space, and the mesh regularity parameter. Moreover, the time step condition becomes$\tau \lesssim h/c$ in the convectiondominated regime and it becomes$\tau \lesssim d/c^2$ in the diffusiondominated regime. The result is improved for a first order IMEXLDG method. To complement the theoretical analysis, numerical experiments are further carried out, leading to slightly stricter time step conditions that can be used by practitioners. Uniform stability with respect to the strength of the convection and diffusion effects can especially be relevant to guide the choice of time step sizes in practice, e.g. when the convectiondiffusion equations are convectiondominated in some subregions. 
Given only a finite collection of points sampled from a Riemannian manifold embedded in a Euclidean space, in this paper we propose a new method to numerically solve elliptic and parabolic partial differential equations (PDEs) supplemented with boundary conditions. Since the construction of triangulations on unknown manifolds can be both difficult and expensive, both in terms of computational and data requirements, our goal is to solve these problems without a triangulation. Instead, we rely only on using the sample points to define quadrature formulas on the unknown manifold. Our main tool is the diffusion maps algorithm. We reanalyze this wellknown method in a variational sense for manifolds with boundary. Our main result is that the variational diffusion maps graph Laplacian is a consistent estimator of the Dirichlet energy on the manifold. This improves upon previous results and provides a rigorous justification of the wellknown relationship between diffusion maps and the Neumann eigenvalue problem. Moreover, using semigeodesic coordinates we derive the first uniform asymptotic expansion of the diffusion maps kernel integral operator for manifolds with boundary. This expansion relies on a novel lemma which relates the extrinsic Euclidean distance to the coordinate norm in a normal collar of the boundary. We then use a recently developed method of estimating the distance to boundary function (notice that the boundary location is assumed to be unknown) to construct a consistent estimator for boundary integrals. Finally, by combining these various estimators, we illustrate how to impose Dirichlet and Neumann conditions for some common PDEs based on the Laplacian. Several numerical examples illustrate our theoretical findings.more » « less

We propose a componentbased (CB) parametric model order reduction (pMOR) formulation for parameterized nonlinear elliptic partial differential equations. CBpMOR is designed to deal with largescale problems for which fullorder solves are not affordable in a reasonable time frame or parameters' variations induce topology changes that prevent the application of monolithic pMOR techniques. We rely on the partitionofunity method to devise global approximation spaces from local reduced spaces, and on Galerkin projection to compute the global state estimate. We propose a randomized data compression algorithm based on oversampling for the construction of the components' reduced spaces: the approach exploits random boundary conditions of controlled smoothness on the oversampling boundary. We further propose an adaptive residualbased enrichment algorithm that exploits global reducedorder solves on representative systems to update the local reduced spaces. We prove exponential convergence of the enrichment procedure for linear coercive problems; we further present numerical results for a twodimensional nonlinear diffusion problem to illustrate the many features of our methodology and demonstrate its effectiveness.more » « less

Consider the scattering of a timeharmonic acoustic plane wave by a bounded elastic obstacle which is immersed in a homogeneous acoustic medium. This paper is concerned with an inverse acousticelastic interaction problem, which is to determine the location and shape of the elastic obstacle by using either the phased or phaseless farfield data. By introducing the Helmholtz decomposition, the model problem is reduced to a coupled boundary value problem of the Helmholtz equations. The jump relations are studied for the second derivatives of the singlelayer potential in order to deduce the corresponding boundary integral equations. The wellposedness is discussed for the solution of the coupled boundary integral equations. An efficient and high order Nyströmtype discretization method is proposed for the integral system. A numerical method of nonlinear integral equations is developed for the inverse problem. For the case of phaseless data, we show that the modulus of the farfield pattern is invariant under a translation of the obstacle. To break the translation invariance, an elastic reference ball technique is introduced. We prove that the inverse problem with phaseless farfield pattern has a unique solution under certain conditions. In addition, a numerical method of the reference ball technique based nonlinear integral equations is proposed for the phaseless inverse problem. Numerical experiments are presented to demonstrate the effectiveness and robustness of the proposed methods.more » « less

null (Ed.)In distributed second order optimization, a standard strategy is to average many local estimates, each of which is based on a small sketch or batch of the data. However, the local estimates on each machine are typically biased, relative to the full solution on all of the data, and this can limit the effectiveness of averaging. Here, we introduce a new technique for debiasing the local estimates, which leads to both theoretical and empirical improvements in the convergence rate of distributed second order methods. Our technique has two novel components: (1) modifying standard sketching techniques to obtain what we call a surrogate sketch; and (2) carefully scaling the global regularization parameter for local computations. Our surrogate sketches are based on determinantal point processes, a family of distributions for which the bias of an estimate of the inverse Hessian can be computed exactly. Based on this computation, we show that when the objective being minimized is l2regularized with parameter ! and individual machines are each given a sketch of size m, then to eliminate the bias, local estimates should be computed using a shrunk regularization parameter given by (See PDF), where d(See PDF) is the (See PDF)effective dimension of the Hessian (or, for quadratic problems, the data matrix).more » « less