Let $G=(V,E,w)$ be a finite, connected graph with weighted edges. We are interested in the problem of finding a subset $W \subset V$ of vertices and weights $a_w$ such that $$ \frac1|V|\sum_v ∈V^f(v) ∼\sum_w ∈Wa_w f(w)$$ for functions $f:V \rightarrow \mathbb{R}$ that are `smooth' with respect to the geometry of the graph. The main application are problems where $f$ is known to somehow depend on the underlying graph but is expensive to evaluate on even a single vertex. We prove an inequality showing that the integration problem can be rewritten as a geometric problem (`the optimal packing of heat balls'). We discuss how one would construct approximate solutions of the heat ball packing problem; numerical examples demonstrate the efficiency of the method.

Mar 20 2018

math.NA arXiv:1803.06985v1

In this paper, we propose a unified framework, the Hessian discretisation method (HDM), which is based on four discrete elements (called altogether a Hessian discretisation) and a few intrinsic indicators of accuracy, independent of the considered model. An error estimate is obtained, using only these intrinsic indicators, when the HDM framework is applied to linear fourth order problems. It is shown that HDM encompasses a large number of numerical methods for fourth order elliptic problems: finite element method (conforming and non-conforming) as well as finite volume method. Finally, we use the HDM to design a novel method, based on conforming $\mathbb{P}_1$ finite element space and gradient recovery operators. Results of numerical experiments are presented for this novel scheme.

Mar 20 2018

math.NA arXiv:1803.06980v1

We propose, analyze and test a fully discrete, efficient second-order algorithm for computing flow ensembles average of viscous, incompressible, and time-dependent magnetohydrodynamic (MHD) flows under uncertainties in initial conditions. The scheme is decoupled and based on Elsässer variable formulation. The algorithm uses the breakthrough idea of Jiang and Layton, 2014 to approximate the ensemble average of $J$ realizations. That is, at each time step, each of the $J$ realization shares the same coefficient matrix for different right-hand side matrices. Thus, storage requirements and computational time are reduced by building preconditioners once per time step and reuse them. We prove stability and optimal convergence with respect to the time step restriction. On some manufactured solutions, numerical experiments are given to verify the predicted convergence rates of our analysis. Finally, we test the scheme on a benchmark channel flow over a step and it performs well.

Mar 20 2018

math.NA arXiv:1803.06925v1

We consider ultraweak variational formulations for (parametrized) linear first order transport equations in time and/or space. Computationally feasible pairs of optimally stable trial and test spaces are presented, starting with a suitable test space and defining an optimal trial space by the application of the adjoint operator. As a result, the inf-sup constant is one in the continuous as well as in the discrete case and the computational realization is therefore easy. In particular, regarding the latter, we avoid a stabilization loop within the greedy algorithm when constructing reduced models within the framework of reduced basis methods. Several numerical experiments demonstrate the good performance of the new method.

Mar 20 2018

math.NA arXiv:1803.06902v1

Like the continous shearlet transform and their relatives, discrete transformations based on the interplay between several filterbanks with anisotropic dilations provide a high potential to recover directed features in two and more dimensions. Due to simplicity, most of the directional systems constructed so far were using prediction--correction methods based on interpolatory subdivision schemes. In this paper, we give a simple but effective construction for QMF (quadrature mirror filter) filterbanks which are the discrete object between orthogonal wavelet analysis. We also characterize when the filterbank gives rise to the existence of refinable functions and hence wavelets and give a generalized shearlet construction for arbitrary dimensions and arbitrary scalings for which the filterbank construction ensures the existence of an orthogonal wavelet analysis.

Two-dimensional Kelvin-Helmholtz instability problems are popular examples for assessing discretizations or turbulence models for incompressible flows. Unfortunately, the results in the literature differ considerably. This paper presents computational studies of a Kelvin-Helmholtz instability problem with high order divergence-free finite element methods. Reference results in several quantities of interest are obtained for three different Reynolds numbers up to the beginning of the final vortex pairing. A mesh-independent prediction of the final pairing is not achieved due to the sensitivity of the considered problem with respect to small perturbations. A theoretical explanation of this sensitivity to small perturbations is provided based on the theory of self-organization of 2d turbulence. Possible sources of perturbations that arise in almost any numerical simulation are discussed.

Mar 20 2018

math.NA arXiv:1803.06846v1

We propose an efficient variant of a primal Discontinuous Galerkin method with interior penalty for the second order elliptic equations on very general meshes (polytopes with eventually curved boundaries). Efficiency, especially when higher order polynomials are used, is achieved by static condensation, i.e. a local elimination of certain degrees of freedom element by element. This alters the original method in a way that preserves the optimal error estimates. Numerical experiments confirm that the solutions produced by the new method are indeed very close to that produced by the classical one.

Mar 20 2018

math.NA arXiv:1803.06833v1

A novel approach for non-intrusive uncertainty propagation is proposed. Our approach overcomes the limitation of many traditional methods, such as generalised polynomial chaos methods, which may lack sufficient accuracy when the quantity of interest depends discontinuously on the input parameters. As a remedy we propose an adaptive sampling algorithm based on minimum spanning trees combined with a domain decomposition method based on support vector machines. The minimum spanning tree determines new sample locations based on both the probability density of the input parameters and the gradient in the quantity of interest. The support vector machine efficiently decomposes the random space in multiple elements, avoiding the appearance of Gibbs phenomena near discontinuities. On each element, local approximations are constructed by means of least orthogonal interpolation, in order to produce stable interpolation on the unstructured sample set. The resulting minimum spanning tree multi-element method does not require initial knowledge of the behaviour of the quantity of interest and automatically detects whether discontinuities are present. We present several numerical examples that demonstrate accuracy, efficiency and generality of the method.

We construct new spin singular integral equations for solving scattering problems for Maxwell's equations, both against perfect conductors and in media with piecewise constant permittivity, permeability and conductivity, improving and extending earlier formulations by the author. These differ in a fundamental way from classical integral equations, which use double layer potential operators, and have the advantage of having a better condition number, in particular in Fredholm sense and on Lipschitz regular interfaces, and do not suffer from spurious resonances. The construction of the integral equations builds on the observation that the double layer potential factorises into a boundary value problem and an ansatz. We modify the ansatz, inspired by a non-selfadjoint local elliptic boundary condition for Dirac equations.

Mar 20 2018

math.NA arXiv:1803.06639v1

Recovering some prominent high-order approaches such as the discontinuous Galerkin (DG) or the spectral difference (SD) methods, the flux reconstruction (FR) approach has been adopted by many individuals in the research community and is now commonly used to solve problems on unstructured grids over complex geometries. This approach relies on the use of correction functions to obtain a differential form for the discrete problem. A class of correction functions, named energy stable flux reconstruction (ESFR) functions, has been proven stable for the linear advection problem. This proof has then been extended for the diffusion equation using the local discontinuous Galerkin (LDG) scheme to compute the numerical fluxes. Although the LDG scheme is commonly used, many prefer the interior penalty (IP), as well as the Bassi and Rebay II (BR2) schemes. Similarly to the LDG proof, this article provides a stability analysis for the IP and the BR2 numerical fluxes. In fact, we obtain a theoretical condition on the penalty term to ensure stability. This result is then verified through numerical simulations. To complete this study, a von Neumann analysis is conducted to provide a combination of parameters producing the maximal time step while converging at the correct order. All things considered, this article has for purpose to provide the community with a stability condition while using the IP and the BR2 schemes.

Mar 20 2018

math.NA arXiv:1803.06635v1

We develop a stabilized cut discontinuous Galerkin framework for the numerical solution of el- liptic boundary value and interface problems on complicated domains. The domain of interest is embedded in a structured, unfitted background mesh in R d , so that the boundary or interface can cut through it in an arbitrary fashion. The method is based on an unfitted variant of the classical symmetric interior penalty method using piecewise discontinuous polynomials defined on the back- ground mesh. Instead of the cell agglomeration technique commonly used in previously introduced unfitted discontinuous Galerkin methods, we employ and extend ghost penalty techniques from recently developed continuous cut finite element methods, which allows for a minimal extension of existing fitted discontinuous Galerkin software to handle unfitted geometries. Identifying four abstract assumptions on the ghost penalty, we derive geometrically robust a priori error and con- dition number estimates for the Poisson boundary value problem which hold irrespective of the particular cut configuration. Possible realizations of suitable ghost penalties are discussed. We also demonstrate how the framework can be elegantly applied to discretize high contrast interface problems. The theoretical results are illustrated by a number of numerical experiments for various approximation orders and for two and three-dimensional test problems.

Mar 20 2018

math.NA arXiv:1803.06576v1

We introduce a novel type of approximation spaces for functions with values in a nonlinear manifold. The discrete functions are constructed by piecewise polynomial interpolation in a Euclidean embedding space, and then projecting pointwise onto the manifold. We show optimal interpolation error bounds with respect to Lebesgue and Sobolev norms. Additionally, we show similar bounds for the test functions, i.e., variations of discrete functions. Combining these results with a nonlinear Céa lemma, we prove optimal $L^2$ and $H^1$ discretization error bounds for harmonic maps from a planar domain into a smooth manifold. All these error bounds are also verified numerically.

Based on an explicit equivalent continuous optimization problem, we propose a simple continuous iterative algorithm for Max Cut, which converges to a local optimum in finite steps. The inner subproblem is solved analytically and thus no optimization solver is called. Preliminary results on G-set demonstrate the performance. In particular, the ratio between the best cut values achieved by the simple algorithm without any local breakout techniques and the best known ones is of at least $0.986$.