We revisit evaluation of logical formulas that allow both uninterpreted relations, constrained to be finite, as well as an interpreted vocabulary over an infinite domain. This formalism was denoted embedded finite model theory in the past. It is clear that the expressiveness and evaluating complexity of formulas of this type depend heavily on the infinite structure. If we embed in a wild structure like the integers with additive and multiplicative arithmetic, logic is extremely expressive and formulas are impossible to evaluate. On the other hand, for some well-known decidable structures, the expressiveness and evaluating complexity are similar to the situation without the additional infrastructure. The latter phenomenon was formalized via the notion of “Restricted Quantifier Collapse”: adding quantification over the infinite structure does not add expressiveness. Beyond these two extremes little was known. In this work we show that the possibilities for expressiveness and complexity are much wider. We show that we can get almost any possible complexity of evaluation while staying within a decidable structure. We also show that in some decidable structures, there is a disconnect between expressiveness of the logic and complexity, in that we cannot eliminate quantification over the structure, but this is not due to an ability to embed complex relational computation in the logic. We show failure of collapse for the theory of finite fields and the related theory of pseudo-finite fields, which will involve coding computation in the logic. As a by-product of this, we establish the first lower bounds for the complexity of decision procedures for several decidable theories of fields, including the theory of finite fields. This article includes material in the extended abstract “Embedded Finite Models: Beyond Restricted Quantifier Collapse,” that appeared in the Logic in Computer Science conference (LICS ’23).

In numerical linear algebra, a well-established practice is to choose a norm that exploits the structure of the problem at hand to optimise accuracy or computational complexity. In numerical polynomial algebra, a single norm (attributed to Weyl) dominates the literature. This article initiates the use of $L_p$ norms for numerical algebraic geometry, with an emphasis on $L_{\infty }$. This classical idea yields strong improvements in the analysis of the number of steps performed by numerous iterative algorithms. In particular, we exhibit three algorithms where, despite the complexity of computing $L_{\infty }$-norm, the use of $L_p$-norms substantially reduces computational complexity: a subdivision-based algorithm in real algebraic geometry for computing the homology of semialgebraic sets, a well-known meshing algorithm in computational geometry and the computation of zeros of systems of complex quadratic polynomials (a particular case of Smale’s 17th problem).

In this paper we analyse the limiting conditional distribution (Yaglom limit) for stochastic fluid models (SFMs), a key class of models in the theory of matrix-analytic methods. So far, only transient and stationary analyses of SFMs have been considered in the literature. The limiting conditional distribution gives useful insights into what happens when the process has been evolving for a long time, given that its busy period has not ended yet. We derive expressions for the Yaglom limit in terms of the singularity˜$s^*$ such that the key matrix of the SFM, ${\boldsymbol{\Psi}}(s)$, is finite (exists) for all $s\geq s^*$ and infinite for $s<s^*$. We show the uniqueness of the Yaglom limit and illustrate the application of the theory with simple examples.

A novel mesh deformation technique is developed based on the Delaunay graph mapping method and the inverse distance weighting (IDW) interpolation. The algorithm maintains the advantages of the efficiency of Delaunay graph mapping mesh deformation while it also possesses the ability of better controlling the near surface mesh quality. The Delaunay graph is used to divide the mesh domain into a number of sub-domains. On each sub-domain, the inverse distance weighting interpolation is applied, resulting in a similar efficiency as compared to the fast Delaunay graph mapping method. The paper will show how the near-wall mesh quality is controlled and improved by the new method

Even though there are various fast methods and preconditioning techniques available for the simulation of Poisson problems, little work has been done for solving Poisson's equation by using the Helmholtz decomposition scheme. To bridge this issue, we propose a novel efficient algorithm to solve Poisson's equation in irregular two dimensional domains for electrostatics through a quasi-Helmholtz decomposition technique—the loop-tree basis decomposition. It can handle Dirichlet, Neumann or mixed boundary problems in which the filling media can be homogeneous or inhomogeneous. A novel point of this method is to first find the electric flux efficiently by applying the loop-tree basis functions. Subsequently, the potential is obtained by finding the inverse of the gradient operator. Furthermore, treatments for both Dirichlet and Neumann boundary conditions are addressed. Finally, the validation and efficiency are illustrated by several numerical examples. Through these simulations, it is observed that the computational complexity of our proposed method almost scales as , where N is the triangle patch number of meshes. Consequently, this new algorithm is a feasible fast Poisson solver.

Based on polyhedral splines, some multivariate splines of different orders with given supports over arbitrary topological meshes are developed. Schemes for choosing suitable families of multivariate splines based on pre-given meshes are discussed. Those multivariate splines with inner knots and boundary knots from the related meshes are used to generate rational spline shapes with related control points. Steps for up to C2-surfaces over the meshes are designed. The relationship among the meshes and their knots, the splines and control points is analyzed. To avoid any unexpected discontinuities and get higher smoothness, a heart-repairing technique to adjust inner knots in the multivariate splines is designed.

With the theory above, bivariate C1-quadratic splines over rectangular meshes are developed. Those bivariate splines are used to generate rational C1-quadratic surfaces over the meshes with related control points and weights. The properties of the surfaces are analyzed. The boundary curves and the corner points and tangent planes, and smooth connecting conditions of different patches are presented. The C1–continuous connection schemes between two patches of the surfaces are presented.

This paper analyzes an abstract two-level algorithm for hybridizable discontinuous Galerkin (HDG) methods in a unified fashion. We use an extended version of the Xu-Zikatanov (X-Z) identity to derive a sharp estimate of the convergence rate of the algorithm, and show that the theoretical results also are applied to weak Galerkin (WG) methods. The main features of our analysis are twofold: one is that we only need the minimal regularity of the model problem; the other is that we do not require the triangulations to be quasi-uniform. Numerical experiments are provided to confirm the theoretical results.

We continue our study of intermediate sums over polyhedra, interpolating between integrals and discrete sums, which were introduced by Barvinok [Computing the Ehrhart quasi-polynomial of a rational simplex. Math. Comp. 75 (2006), 1449–1466]. By well-known decompositions, it is sufficient to consider the case of affine cones $s+\mathfrak{c}$ , where $s$ is an arbitrary real vertex and $\mathfrak{c}$ is a rational polyhedral cone. For a given rational subspace  $L$ , we define the intermediate generating functions $S^{L}(s+\mathfrak{c})(\unicode[STIX]{x1D709})$ by integrating an exponential function over all lattice slices of the affine cone  $s+\mathfrak{c}$ parallel to the subspace  $L$ and summing up the integrals. We expose the bidegree structure in parameters $s$ and $\unicode[STIX]{x1D709}$ , which was implicitly used in the algorithms in our papers [Computation of the highest coefficients of weighted Ehrhart quasi-polynomials of rational polyhedra. Found. Comput. Math.12 (2012), 435–469] and [Intermediate sums on polyhedra: computation and real Ehrhart theory. Mathematika59 (2013), 1–22]. The bidegree structure is key to a new proof for the Baldoni–Berline–Vergne approximation theorem for discrete generating functions [Local Euler–Maclaurin expansion of Barvinok valuations and Ehrhart coefficients of rational polytopes. Contemp. Math.452 (2008), 15–33], using the Fourier analysis with respect to the parameter  $s$ and a continuity argument. Our study also enables a forthcoming paper, in which we study intermediate sums over multi-parameter families of polytopes.

We have developed easy to use fast multipole method (FMM) libraries for the Laplace, low-frequency Helmholtz, and Stokes equations in two and three dimensions. The codes are based on a new method for applying translation operators and provide reasonable performance on either single core processors, or small multi-core systems using OpenMP.

In this paper, we investigate the coupling of the Multi-dimensional Optimal Order Detection (MOOD) method and the Arbitrary high order DERivatives (ADER) approach in order to design a new high order accurate, robust and computationally efficient Finite Volume (FV) scheme dedicated to solve nonlinear systems of hyperbolic conservation laws on unstructured triangular and tetrahedral meshes in two and three space dimensions, respectively. The Multi-dimensional Optimal Order Detection (MOOD) method for 2D and 3D geometries has been introduced in a recent series of papers for mixed unstructured meshes. It is an arbitrary high-order accurate Finite Volume scheme in space, using polynomial reconstructions with a posteriori detection and polynomial degree decrementing processes to deal with shock waves and other discontinuities. In the following work, the time discretization is performed with an elegant and efficient one-step ADER procedure. Doing so, we retain the good properties of the MOOD scheme, that is to say the optimal high-order of accuracy is reached on smooth solutions, while spurious oscillations near singularities are prevented. The ADER technique permits not only to reduce the cost of the overall scheme as shown on a set of numerical tests in 2D and 3D, but it also increases the stability of the overall scheme. A systematic comparison between classical unstructured ADER-WENO schemes and the new ADER-MOOD approach has been carried out for high-order schemes in space and time in terms of cost, robustness, accuracy and efficiency. The main finding of this paper is that the combination of ADER with MOOD generally outperforms the one of ADER and WENO either because at given accuracy MOOD is less expensive (memory and/or CPU time), or because it is more accurate for a given grid resolution. A large suite of classical numerical test problems has been solved on unstructured meshes for three challenging multi-dimensional systems of conservation laws: the Euler equations of compressible gas dynamics, the classical equations of ideal magneto-Hydrodynamics (MHD) and finally the relativistic MHD equations (RMHD), which constitutes a particularly challenging nonlinear system of hyperbolic partial differential equation. All tests are run on genuinely unstructured grids composed of simplex elements.

Various works from the literature aimed at accelerating Bayesian inference in inverse problems. Stochastic spectral methods have been recently proposed as surrogate approximations of the forward uncertainty propagation model over the support of the prior distribution. These representations are efficient because they allow affordable simulation of a large number of samples from the posterior distribution. Unfortunately, they do not perform well when the forward model exhibits strong nonlinear behavior with respect to its input.

In this work, we first relate the fast (exponential) L2-convergence of the forward approximation to the fast (exponential) convergence (in terms of Kullback-Leibler divergence) of the approximate posterior. In particular, we prove that in case the prior distribution is uniform, the posterior is at least twice as fast as the convergence rate of the forwardmodel in those norms. The Bayesian inference strategy is developed in the framework of a stochastic spectral projectionmethod. The predicted convergence rates are then demonstrated for simple nonlinear inverse problems of varying smoothness.

We then propose an efficient numerical approach for the Bayesian solution of inverse problems presenting strongly nonlinear or discontinuous systemresponses. This comes with the improvement of the forward model that is adaptively approximated by an iterative generalized Polynomial Chaos-based representation. The numerical approximations and predicted convergence rates of the former approach are compared to the new iterative numericalmethod for nonlinear time-dependent test cases of varying dimension and complexity, which are relevant regarding our hydrodynamics motivations and therefore regarding hyperbolic conservation laws and the apparition of discontinuities in finite time.

Floor field methods are one of the most popular medium-scale navigation concepts in microscopic pedestrian simulators. Recently introduced dynamic floor field methods have significantly increased the realism of such simulations, i.e. agreement of spatio-temporal patterns of pedestrian densities in simulations with real world observations. These methods update floor fields continuously taking other pedestrians into account. This implies that computational times are mainly determined by the calculation of floor fields. In this work, we propose a new computational approach for the construction of dynamic floor fields. The approach is based on the one hand on adaptive grid concepts and on the other hand on a directed calculation of floor fields, i.e. the calculation is restricted to the domain of interest. Combining both techniques the computational complexity can be reduced by a factor of 10 as demonstrated by several realistic scenarios. Thus on-line simulations, a requirement of many applications, are possible for moderate realistic scenarios.

In this paper an explicit finite-difference time-domain scheme for solving the Maxwell’s equations in non-staggered grids is presented. The proposed scheme for solving the Faraday’s and Ampere’s equations in a theoretical manner is aimed to preserve discrete zero-divergence for the electric and magnetic fields. The inherent local conservation laws in Maxwell’s equations are also preserved discretely all the time using the explicit second-order accurate symplectic partitioned Runge-Kutta scheme. The remaining spatial derivative terms in the semi-discretized Faraday’s and Ampere’s equations are then discretized to provide an accurate mathematical dispersion relation equation that governs the numerical angular frequency and the wavenumbers in two space dimensions. To achieve the goal of getting the best dispersive characteristics, we propose a fourth-order accurate space centered scheme which minimizes the difference between the exact and numerical dispersion relation equations. Through the computational exercises, the proposed dual-preserving solver is computationally demonstrated to be efficient for use to predict the long-term accurate Maxwell’s solutions.

Partial similarity of shapes is a challenging problem arising in many important applications in computer vision, shape analysis, and graphics, e.g. When one has to deal with partial information and acquisition artifacts. The problem is especially hard when the underlying shapes are non-rigid and are given up to a deformation. Partial matching is usually approached by computing local descriptors on a pair of shapes and then establishing a point-wise non-bijective correspondence between the two, taking into account possibly different parts. In this paper, we introduce an alternative correspondence-less approach to matching fragments to an entire shape undergoing a non-rigid deformation. We use region-wise local descriptors and optimize over the integration domains on which the integral descriptors of the two parts match. The problem is regularized using the Mumford-Shah functional. We show an efficient discretization based on the Ambrosio-Tortorelli approximation generalized to triangular point clouds and meshes, and present experiments demonstrating the success of the proposed method.

We study intermediate sums, interpolating between integrals and discrete sums, which were introduced by A. Barvinok in [Computing the Ehrhart quasi-polynomial of a rational simplex. Math. Comp. 75 (2006), 1449–1466]. For a given polytope 𝔭 with facets parallel to rational hyperplanes and a rational subspace L, we integrate a given polynomial function h over all lattice slices of the polytope 𝔭 parallel to the subspace L and sum up the integrals. We first develop an algorithmic theory of parametric intermediate generating functions. Then we study the Ehrhart theory of these intermediate sums, that is, the dependence of the result as a function of a dilation of the polytope. We provide an algorithm to compute the resulting Ehrhart quasi-polynomials in the form of explicit step-polynomials. These formulas are naturally valid for real (not just integer) dilations and thus provide a direct approach to real Ehrhart theory.

An adaptive mesh refinement strategy is proposed in this paper for the Immersed Boundary and Immersed Interface methods for two-dimensional elliptic interface problems involving singular sources. The interface is represented by the zero level set of a Lipschitz function ϕ(x,y). Our adaptive mesh refinement is done within a small tube of |ϕ(x,y)|≤δ with finer Cartesian meshes. The discrete linear system of equations is solved by a multigrid solver. The AMR methods could obtain solutions with accuracy that is similar to those on a uniform fine grid by distributing the mesh more economically, therefore, reduce the size of the linear system of the equations. Numerical examples presented show the efficiency of the grid refinement strategy.

The generalized Polynomial Chaos (gPC) method is one of the most widely used numerical methods for solving stochastic differential equations. Recently, attempts have been made to extend the the gPC to solve hyperbolic stochastic partial differential equations (SPDE). The convergence rate of the gPC depends on the regularity of the solution. It is shown that the characteristics technique can be used to derive general conditions for regularity of linear hyperbolic PDE, in a detailed case study of a linear wave equation with a random variable coefficient and random initial and boundary data.

In this paper, a reduced morphological transformation model with spatially dependent composition and elastic modulus is considered. The parareal in time al-gorithm introduced by Lions et al. is developed for longer-time simulation. The fine solver is based on a second-order scheme in reciprocal space, and the coarse solver is based on a multi-model backward Euler scheme, which is fast and less expensive. Numerical simulations concerning the composition with a random noise and a discontinuous curve are performed. Some microstructure characteristics at very low temperature are obtained by a variable temperature technique.

In this paper the numerical solution of the two-dimensional sine-Gordon equation is studied. Split local artificial boundary conditions are obtained by the operator splitting method. Then the original problem is reduced to an initial boundary value problem on a bounded computational domain, which can be solved by the finite difference method. Several numerical examples are provided to demonstrate the effectiveness and accuracy of the proposed method, and some interesting propagation and collision behaviors of the solitary wave solutions are observed.