Contemporary Computational Mathematics - A Celebration of the 80th Birthday of Ian Sloan

The investigation of the pair correlation statistics of sequences was initially motivated by questions concerning quasi-energy-spectra of quantum systems. However, the subject has been developed far beyond its roots in mathematical physics, and many challenging number-theoretic questions on the distribution of the pair correlations of certain sequences are still open. We give a short introduction into the subject, recall some known results and open problems, and in particular explain the recently established connection between the distribution of pair correlations of sequences on the torus and certain concepts from additive combinatorics. Furthermore, we slightly improve a result recently given by Jean Bourgain in Aistleitner et al. (Isr. J. Math., to appear. Available at https://arxiv.org/abs/1606.03591).

We explore the connection between fractional order partial differential equations in two or more spatial dimensions with boundary integral operators to develop techniques that enable one to efficiently tackle the integral fractional Laplacian. In particular, we develop techniques for the treatment of the dense stiffness matrix including the computation of the entries, the efficient assembly and storage of a sparse approximation and the efficient solution of the resulting equations. The main idea consists of generalising proven techniques for the treatment of boundary integral equations to general fractional orders. Importantly, the approximation does not make any strong assumptions on the shape of the underlying domain and does not rely on any special structure of the matrix that could be exploited by fast transforms. We demonstrate the flexibility and performance of this approach in a couple of two-dimensional numerical examples.

In 2004 the second author of the present paper proved that a point set in [0, 1]d which has star-discrepancy at most ε must necessarily consist of at least c_absdε−1 points. Equivalently, every set of n points in [0, 1]d must have star-discrepancy at least c_absdn−1. The original proof of this result uses methods from Vapnik–Chervonenkis theory and from metric entropy theory. In the present paper we give an elementary combinatorial proof for the same result, which is based on identifying a sub-box of [0, 1]d which has approximately d elements of the point set on its boundary. Furthermore, we show that a point set for which no such box exists is rather irregular, and must necessarily have a large star-discrepancy.

An importance sampling approach for sampling from copula models is introduced. The proposed algorithm improves Monte Carlo estimators when the functional of interest depends mainly on the behaviour of the underlying random vector when at least one of its components is large. Such problems often arise from dependence models in finance and insurance. The importance sampling framework we propose is particularly easy to implement for Archimedean copulas. We also show how the proposal distribution of our algorithm can be optimized by making a connection with stratified sampling. In a case study inspired by a typical insurance application, we obtain variance reduction factors sometimes larger than 1000 in comparison to standard Monte Carlo estimators when both importance sampling and quasi-Monte Carlo methods are used.

Let Ω be an open, simply connected, and bounded region in ℝd $$\mathbb {R}^{d}$$ , d ≥ 2, with a smooth boundary ∂Ω that is homeomorphic to ??d−1 $$\mathbb {S}^{d-1}$$ . Consider solving Δ2u + γu = f over Ω with zero Dirichlet boundary conditions. A Galerkin method based on a polynomial approximation space is proposed, yielding an approximation u _n . With sufficiently smooth problem parameters, the method is shown to be rapidly convergent. For u∈C∞Ω¯ $$u\in C^{\infty }\left ( \overline {\varOmega }\right ) $$ and assuming ∂Ω is a C∞ boundary, the convergence of u−unH2Ω $$\left \Vert u-u_{n}\right \Vert _{H^{2}\left ( \varOmega \right ) }$$ to zero is faster than any power of 1∕n. Numerical examples illustrate experimentally an exponential rate of convergence.

Quasi-Monte Carlo methods are designed for integrands of bounded variation, and this excludes singular integrands. Several methods are known for integrands that become singular on the boundary of the unit cube [0, 1]d or at isolated possibly unknown points within [0, 1]d. Here we consider functions on the square [0, 1]2 that may become singular as the point approaches the diagonal line x₁ = x₂, and we study three quadrature methods. The first method splits the square into two triangles separated by a region around the line of singularity, and applies recently developed triangle QMC rules to the two triangular parts. For functions with a singularity ‘no worse than |x₁ − x₂|−A is’ for 0 < A < 1 that method yields an error of O((log(n)∕n)(1−A)∕2) $$O( (\log (n)/n)^{(1-A)/2})$$ . We also consider methods extending the integrand into a region containing the singularity and show that method will not improve upon using two triangles. Finally, we consider transforming the integrand to have a more QMC-friendly singularity along the boundary of the square. This then leads to error rates of O(n−1+??+A) when combined with some corner-avoiding Halton points or with randomized QMC but it requires some stronger assumptions on the original singular integrand.

We prove that there is no strongly regular graph (SRG) with parameters (460, 153, 32, 60). The proof is based on a recent lower bound on the number of 4-cliques in a SRG and some applications of Euclidean representation of SRGs.

We produce low-discrepancy infinite sequences which can be used to approximate the integral of a smooth periodic function restricted to a smooth convex domain with positive curvature in ℝd $$\mathbb {R}^{d}$$ . The proof depends on simultaneous Diophantine approximation and on appropriate estimates of the decay of the Fourier transform of characteristic functions.

We analyze explicit trial functions defined on the unit sphere ??d $${\mathbb {S}}^d$$ in the Euclidean space ℝd+1 $${\mathbb {R}}^{d+1}$$ , d ≥ 1, that are integrable in the ??p $${\mathbb {L}}_p$$ -sense, p ∈ [1, ∞). These functions depend on two free parameters: one determines the support and one, a critical exponent, controls the behavior near the boundary of the support. Three noteworthy features are: (1) they are simple to implement and capture typical behavior of functions in applications, (2) their integrals with respect to the uniform measure on the sphere are given by explicit formulas and, thus, their numerical values can be computed to arbitrary precision, and (3) their smoothness can be defined a priori, that is to say, they belong to Sobolev spaces ℍs(??d) $${\mathbb {H}}^s({\mathbb {S}}^d)$$ up to a specified index s̄ $$\bar {s}$$ determined by the parameters of the function. Considered are zonal functions g(x) = h(x ⋅p), where p is some fixed pole on ??d $${\mathbb {S}}^d$$ . The function h(t) is of the type [max{t,T}]α $$[ \max \{t,T\} ]^\alpha $$ or a variation of a truncated power function x↦(x)+α $$x \mapsto (x)_+^\alpha $$ (which assumes 0 if x ≤ 0 and is the power xα if x > 0) that reduces to [max{t−T,0}]α $$[ \max \{t-T,0\} ]^\alpha $$ , [max{t2−T2,0}]α $$[ \max \{t^2-T^2,0\} ]^{\alpha }$$ , and [max{T2−t2,0}]α $$[ \max \{T^2-t^2,0\} ]^{\alpha }$$ if α > 0. These types of trial functions have as support the whole sphere, a spherical cap centered at p, a bi-cap centered at the antipodes p, −p, or an equatorial belt. We give inclusion theorems that identify the critical smoothness s̄=s̄(T,α) $$\bar {s} = \bar {s}(T,\alpha )$$ and explicit formulas for the integral over the sphere. We obtain explicit formulas for the coefficients in the Laplace-Fourier expansion of these trial functions and provide the leading order term in the asymptotics for large index of the coefficients.

We consider the minimal discrete and continuous energy problems on the unit sphere ??d $$\mathbb {S}^d$$ in the Euclidean space ℝd+1 $$\mathbb {R}^{d+1}$$ in the presence of an external field due to finitely many localized charge distributions on ??d $$\mathbb {S}^d$$ , where the energy arises from the Riesz potential 1∕rs (r is the Euclidean distance) for the critical Riesz parameter s = d − 2 if d ≥ 3 and the logarithmic potential log(1∕r) $$\log (1/r)$$ if d = 2. Individually, a localized charge distribution is either a point charge or assumed to be rotationally symmetric. The extremal measure solving the continuous external field problem for weak fields is shown to be the uniform measure on the sphere but restricted to the exterior of spherical caps surrounding the localized charge distributions. The radii are determined by the relative strengths of the generating charges. Furthermore, we show that the minimal energy points solving the related discrete external field problem are confined to this support. For d − 2 ≤ s < d, we show that for point sources on the sphere, the equilibrium measure has support in the complement of the union of specified spherical caps about the sources. Numerical examples are provided to illustrate our results.

The aim of this paper is to describe the current state of the numerical analysis and the computational solution of non-standard integro-differential equations of Volterra and Fredholm types that arise in various applications. In order to do so, we first give a brief review of recent results concerning the numerical analysis of standard (ordinary and partial) Volterra and Fredholm integro-differential equations, with the focus being on collocation and (continuous and discontinuous) Galerkin methods. In the second part of the paper we look at the extension of these results to various classes of non-standard integro-differential equations type that arise as mathematical models in applications. We shall see that in addition to numerous open problems in the numerical analysis of such equations, many challenges in the computational solution of non-standard Volterra and Fredholm integro-differential equations are waiting to be addressed.

The task of approximating a function of d variables from its evaluations at a given number of points is ubiquitous in numerical analysis and engineering applications. When d is large, this task is challenged by the so-called curse of dimensionality. As a typical example, standard polynomial spaces, such as those of total degree type, are often uneffective to reach a prescribed accuracy unless a prohibitive number of evaluations is invested. In recent years it has been shown that, for certain relevant applications, there are substantial advantages in using certain sparse polynomial spaces having anisotropic features with respect to the different variables. These applications include in particular the numerical approximation of high-dimensional parametric and stochastic partial differential equations. We start by surveying several results in this direction, with an emphasis on the numerical algorithms that are available for the construction of the approximation, in particular through interpolation or discrete least-squares fitting. All such algorithms rely on the assumption that the set of multi-indices associated with the polynomial space is downward closed. In the present paper we introduce some tools for the study of approximation in multivariate spaces under this assumption, and use them in the derivation of error bounds, sometimes independent of the dimension d, and in the development of adaptive strategies.

Using recent results on subperiodic trigonometric Gaussian quadrature and the construction of subperiodic trigonometric orthogonal bases, we extend Sloan’s notion of hyperinterpolation to trigonometric spaces on subintervals of the period. The result is relevant, for example, to function approximation on spherical or toroidal rectangles.

In many practical situations, the recovery of information about some phenomenon of interest f reduces to performing Fourier deconvolution on indirect measurements g = p ∗ f, corresponding to the Fourier convolution of f with a known kernel (point spread function) p. An iterative procedure is proposed for performing the deconvolution of g = p ∗ f, which generates the partial sums of a Neumann series. However, the standard convergence analysis for the Neumann series is not applicable for such deconvolutions so a proof is given which is based on using Fourier properties in L2.In practice, only discrete measurements {g _m } of g will be available. Consequently, the construction of a discrete approximation {f _m } to f reduces to performing a deconvolution using a discrete version {g _m } = {p _m }∗{f _m } of g = p ∗ f. For p(x) = sech(x)∕π, it is shown computationally, using the discrete version of the proposed iteration, that the resulting accuracy of {f _m } will depend on the form and smoothness of f, the size of the interval truncation, and the level of discretization of the measurements {g _m }. Excellent accuracy for {f _m } is obtained when {g _m } and {p _m } accurately approximate the essential structure in g and p, respectively, the support of p is much smaller than that for g, and the discrete measurements of {g _m } are on a suitably fine grid.

Toeplitz T(a) and Toeplitz plus Hankel operators T(a) + H(b) acting on sequence space lp, 1 < p < ∞, are considered. If a ∈ PC _p is a piecewise continuous lp-multiplier, a complete description of the kernel of the Fredholm operator T(a) is derived. Moreover, the kernels of Fredholm Toeplitz plus Hankel operators T(a) + H(b) the generating functions a and b of which belong to PC _p and satisfy the condition a(t)a(1∕t) = b(t)b(1∕t), t∈?? $$t\in {\mathbb {T}}$$ , are also determined.

We provide probabilistic lower bounds for the star discrepancy of Latin hypercube samples. These bounds are sharp in the sense that they match the recent probabilistic upper bounds for the star discrepancy of Latin hypercube samples proved in Gnewuch and Hebbinghaus (Discrepancy bounds for a class of negatively dependent random points including Latin hypercube samples. Preprint 2016). Together, this result and our work implies that the discrepancy of Latin hypercube samples differs at most by constant factors from the discrepancy of uniformly sampled point sets.

In this review article, we describe some advances in applications of the hyperinterpolation operator introduced by Sloan about two decades ago (J Approx Theory 83:238–254, 1995). In particular, our focus is on reviewing the application of the scalar and vector-valued hyperinterpolation approximations for developing, analyzing and implementing fully-discrete high-order algorithms. Such approximations facilitate efficient simulation of scattering of acoustic, electromagnetic and elastic waves, exterior to connected and disconnected bounded three dimensional domains. The main contributions of this article are: (1) a unified (acoustic, electromagnetic, and elastic) approach for the three important classes of waves; (2) theoretical and numerical comparisons of the hyperinterpolation approximations in these three applications; and (3) new results for a class of unbounded heterogeneous media.

We present an error analysis of higher order Quasi-Monte Carlo (QMC) integration and of randomly shifted QMC lattice rules for parametric operator equations with uncertain input data taking values in Banach spaces. Parametric expansions of these input data in locally supported bases such as splines or wavelets was shown in Gantner et al. (SIAM J Numer Anal 56(1):111–135, 2018) to allow for dimension independent convergence rates of combined QMC-Galerkin approximations. In the present work, we review and refine the results in that reference to the multilevel setting, along the lines of Kuo et al. (Found Comput Math 15(2):441–449, 2015) where randomly shifted lattice rules and globally supported representations were considered, and also the results of Dick et al. (SIAM J Numer Anal 54(4):2541–2568, 2016) in the particular situation of locally supported bases in the parametrization of uncertain input data. In particular, we show that locally supported basis functions allow for multilevel QMC quadrature with product weights, and prove new error vs. work estimates superior to those in these references (albeit at stronger, mixed regularity assumptions on the parametric integrand functions than what was required in the single-level QMC error analysis in the first reference above). Numerical experiments on a model affine-parametric elliptic problem confirm the analysis.

Based on the error analysis of Extended Filon Method (EFM), we present an adaptive Filon method to calculate highly oscillatory integrals. The main idea is to allow interpolation points depend upon underlying frequency in order to minimize the error. Typically, quadrature error need be examined in two regimes. Once frequency is large, asymptotic behaviour dominates and we need to choose interpolation points accordingly, while for small frequencies good choice of interpolation points is similar to classical, non-oscillatory quadrature. In this paper we choose frequency-dependent interpolation points according to a smooth homotopy function and the accuracy is superior to other EFMs. The basic algorithm is presented in the absence of stationary points but we extend it to cater for highly oscillatory integrals with stationary points. The presentation is accompanied by numerical experiments which demonstrate the power of our approach.

This paper discusses progress and future research possibilities in applying MLMC ideas to nested expectations of the form ??[g(??[f(X,Y)|X])] $${\mathbb {E}}[\, g({\mathbb {E}}[\,f(X,Y) | X]) \,]$$ , with an outer expectation with respect to one random variable X, and an inner conditional expectation with respect to a second random variable Y . The difficulty in treating such applications is shown to depend on whether the function g is (1) smooth, (2) continuous and piecewise smooth, or (3) discontinuous.

We produce precise estimates for the Kogbetliantz kernel for the approximation of functions on the sphere. Furthermore, we propose and study a new approximation kernel, which has slightly better properties.

We describe modern variants of Monte Carlo methods for Uncertainty Quantification (UQ) of the Neutron Transport Equation, when it is approximated by the discrete ordinates method with diamond differencing. We focus on the mono-energetic 1D slab geometry problem, with isotropic scattering, where the cross-sections are log-normal correlated random fields of possibly low regularity. The paper includes an outline of novel theoretical results on the convergence of the discrete scheme, in the cases of both spatially variable and random cross-sections. We also describe the theory and practice of algorithms for quantifying the uncertainty of a functional of the scalar flux, using Monte Carlo and quasi-Monte Carlo methods, and their multilevel variants. A hybrid iterative/direct solver for computing each realisation of the functional is also presented. Numerical experiments show the effectiveness of the hybrid solver and the gains that are possible through quasi-Monte Carlo sampling and multilevel variance reduction. For the multilevel quasi-Monte Carlo method, we observe gains in the computational ε-cost of up to two orders of magnitude over the standard Monte Carlo method, and we explain this theoretically. Experiments on problems with up to several thousand stochastic dimensions are included.

Various tensor formats are used for the data-sparse representation of large-scale tensors. Here we investigate how symmetric or antisymmetric tensors can be represented. We mainly investigate the hierarchical format, but also the use of the canonical format is mentioned.

This article develops direct and inverse estimates for certain finite dimensional spaces arising in kernel approximation. Both the direct and inverse estimates are based on approximation spaces spanned by local Lagrange functions which are spatially highly localized. The construction of such functions is computationally efficient and generalizes the construction given in Hangelbroek et al. (Math Comput, 2017, in press) for restricted surface splines on ℝd $${\mathbb {R}}^d$$ . The kernels for which the theory applies includes the Sobolev-Matérn kernels for closed, compact, connected, C∞ Riemannian manifolds.

This paper is devoted to the approximate solution of a hypersingular integral equation on a closed polygonal boundary in ℝ2 $${\mathbb {R}}^2$$ . We propose a fully discrete method with a trial space of trigonometric polynomials, combined with a trapezoidal rule approximation of the integrals. Before discretization the equation is transformed using a nonlinear (mesh grading) parametrization of the boundary curve which has the effect of smoothing out the singularities at the corners and yields fast convergence of the approximate solutions. The convergence results are illustrated with some numerical examples.

We present an iterative Monte Carlo procedure to solve initial value problems for systems of ordinary differential equations depending on a parameter. It is based on a multilevel Monte Carlo algorithm for parametric indefinite integration. As an application, we also obtain a respective method for solving almost linear first order partial differential equations. We also consider deterministic algorithms.We study the convergence and, in the framework of information-based complexity, the minimal errors and show that the developed algorithms are of optimal order (in some limit cases up to logarithmic factors). In this way we extend recent complexity results on parametric ordinary differential equations. Moreover, we obtain the complexity of almost linear first-order partial differential equations, which has not been analyzed before.

High dimensional integrals can be approximated well by quasi-Monte Carlo methods. However, determining the number of function values needed to obtain the desired accuracy is difficult without some upper bound on an appropriate semi-norm of the integrand. This challenge has motivated our recent development of theoretically justified, adaptive cubatures based on digital sequences and lattice nodeset sequences. Our adaptive cubatures are based on error bounds that depend on the discrete Fourier transforms of the integrands. These cubatures are guaranteed for integrands belonging to cones of functions whose true Fourier coefficients decay steadily, a notion that is made mathematically precise. Here we describe these new cubature rules and extend them in two directions. First, we generalize the error criterion to allow both absolute and relative error tolerances. We also demonstrate how to estimate a function of several integrals to a given tolerance. This situation arises in the computation of Sobol’ indices. Second, we describe how to use control variates in adaptive quasi-Monte cubature while appropriately estimating the control variate coefficient.

We propose an upwind hybrid spectral difference method for the steady-state Navier–Stokes equations. The (upwind) hybrid spectral difference method is based on a hybridization as follows: (1) an (upwind) spectral finite difference approximation of the Navier–Stokes equations within cells (the cell finite difference) and (2) an interface finite difference on edges of cells. The interface finite difference approximates continuity of normal stress on cell interfaces. The main advantages of this new approach are three folds: (1) they can be applied to non-uniform grids, retaining the order of convergence, (2) they are stable without using a staggered grid and (3) the schemes have an embedded static condensation property, hence, there is a big reduction in degrees of freedom in resulting discrete systems. The inf-sup condition is proved. Various numerical examples including the driven cavity problem with the Reynolds numbers, 5000–20,000, are presented.

The aim of this paper is to combine classical ideas for the theoretical investigation of the Nyström method for second kind Fredholm integral equations with recent results on polynomial approximation in weighted spaces of continuous functions on bounded and unbounded intervals, where also zeros of polynomials w.r.t. exponential weights are used.

In this paper, we consider an (open) airplane wing, not necessarily symmetric, for which the optimal circulation distribution has to be determined. This latter is the solution of a constraint minimization problem, whose (Cauchy singular integral) Euler-Lagrange equation is known. By following an approach different from a more classical one applied in previous papers, we obtain existence and uniqueness results for the solution of this equation in suitable weighted Sobolev type spaces. Then, for the collocation-quadrature method we propose to solve the equation, we prove stability and convergence and derive error estimates. Some numerical examples, which confirm the previous error estimates, are also presented. These results apply, in particular, to the Euler-Lagrange equation and the numerical method used to solve it in the case of a symmetric wing, which were considered in the above mentioned previous papers.

Taking as background the fact that conservation laws in a single space variable are well-posed in the space of functions of bounded variation, while multidimensional systems enjoy short-time well-posedness in Sobolev spaces Hs, we attempt to resolve the discrepancies between these two theories by exploring what can be said about stability of one-dimensional systems in L2. We summarize some positive results for special cases, and also show by a conterexample that there is no straightforward way to resolve the difficulty.

The inverse problem under consideration is to reconstruct the shape of an impenetrable two-dimensional obstacle with a generalized impedance boundary condition from the far field pattern for scattering of time-harmonic acoustic or E-polarized electromagnetic plane waves. We propose an inverse algorithm that extends the approach suggested by Johansson and Sleeman (IMA J. Appl. Math. 72(1):96–112, 2007) for the case of the inverse problem for a sound-soft or perfectly conducting scatterer. It is based on a system of nonlinear boundary integral equations associated with a single-layer potential approach to solve the forward scattering problem which extends the integral equation method proposed by Cakoni and Kress (Inverse Prob. 29(1):015005, 2013) for a related boundary value problem for the Laplace equation. In addition, we also present an algorithm for reconstructing the impedance function when the shape of the scatterer is known. We present the mathematical foundations of the methods and exhibit their feasibility by numerical examples.

Lattice rules are a powerful and popular form of quasi-Monte Carlo rules that are based on integration lattices. The study of the theory and application of lattice rules is intimately connected with the name Ian H. Sloan. We take the opportunity of Ian’s 80th birthday to give an overview of his wide-ranging and fruitful contributions to this topic.

We consider the approximation of functions of s variables, where s is very large or infinite, that belong to weighted anchored spaces. We study when such functions can be approximated by algorithms designed for functions with only very small number dimtrnc(ε, s) of variables. Here ε is the error demand and we refer to dimtrnc(ε, s) as the ε-truncation dimension. We show that for sufficiently fast decaying product weights and modest error demand (up to about ε ≈ 10−5) the truncation dimension is surprisingly very small.

By the maximum principle the solution of the homogeneous heat equation with homogeneous Dirichlet boundary conditions is nonnegative for positive time if the initial values are nonnegative. In recent work it has been shown that this does not hold for the standard spatially discrete and fully discrete piecewise linear finite element methods. However, for the corresponding semidiscrete and Backward Euler Lumped Mass methods, nonnegativity of initial data is preserved, provided the underlying triangulation is of Delaunay type. In this paper, we study the corresponding problems where the homogeneous Dirichlet boundary conditions are replaced by Neumann and Robin boundary conditions, and show similar results, sometimes requiring more refined technical arguments.

Boundary value problems on the unit sphere arise naturally in geophysics and oceanography when scientists model a physical quantity on large scales. Robust numerical methods play an important role in solving these problems. In this article, we construct numerical solutions to a boundary value problem defined on a spherical sub-domain (with a sufficiently smooth boundary) using radial basis functions (RBFs). The error analysis between the exact solution and the approximation is provided. Numerical experiments are presented to confirm theoretical estimates.

In this paper, for a coupled system of wave equations with Neumann boundary controls, the approximate boundary null controllability, the approximate boundary synchronization and the approximate boundary synchronization by groups are taken into account, respectively. Like in the case with Dirichlet boundary controls, the corresponding conditions of compatibility, and the criteria of Kalman’s type as necessary conditions are obtained. The sufficiency of Kalman’s criteria is further discussed in one dimensional space.

We present a novel approach for support vector machines in reproducing kernel Banach spaces induced by a finite basis. In particular, we show that the support vector classification in the 1-norm reproducing kernel Banach space is mathematically equivalent to the sparse support vector machine. Finally, we develop fixed-point proximity algorithms for finding the solution of the non-smooth minimization problem that describes the sparse support vector machine. Numerical results are presented to demonstrate that the sparse support vector machine outperforms the classical support vector machine for the binary classification of simulation data.

The classical Erdős-Turán theorem established mean convergence of Lagrange interpolants at zeros of orthogonal polynomials. A non-polynomial extension of this was established by Ian Sloan in 1983. Mean convergence of interpolation by entire functions has been investigated by Grozev, Rahman, and Vértesi. In this spirit, we establish an Erdős-Turán theorem for interpolation by entire functions at zeros of the Airy function.

Given β > 0 and δ > 0, the function t−β may be approximated for t in a compact interval [δ, T] by a sum of terms of the form we−at, with parameters w > 0 and a > 0. One such an approximation, studied by Beylkin and Monzón (Appl. Comput. Harmon. Anal. 28:131–149, 2010), is obtained by applying the trapezoidal rule to an integral representation of t−β, after which Prony’s method is applied to reduce the number of terms in the sum with essentially no loss of accuracy. We review this method, and then describe a similar approach based on an alternative integral representation. The main difference is that the new approach achieves much better results before the application of Prony’s method; after applying Prony’s method the performance of both is much the same.

An important question in the theory of approximate integration is to study the conditions on the nodes x_k,n and weights w_k,n that allow an estimate of the form supf∈ℬγ∑kwk,nf(xk,n)−∫??fdμ∗≤cn−γ,n=1,2,⋯, $$\displaystyle \sup _{f\in \mathcal {B}_\gamma }\left |\sum _k w_{k,n}{\,f}(x_{k,n})-\int _{\mathbb {X}} fd\mu ^*\right | \le cn^{-\gamma }, \qquad n=1,2,\cdots , $$ where ?? $$\mathbb {X}$$ is often a manifold with its volume measure μ∗, and ℬγ $$\mathcal {B}_\gamma $$ is the unit ball of a suitably defined smoothness class, parametrized by γ. In this paper, we study this question in the context of a quasi-metric, locally compact, measure space ?? $$\mathbb {X}$$ with a probability measure μ∗. We show that quadrature formulas exact for integrating the so called diffusion polynomials of degree < n satisfy such estimates. Without requiring exactness, such formulas can be obtained as a solutions of some kernel-based optimization problem. We discuss the connection with the question of optimal covering radius. Our results generalize in some sense many recent results in this direction.

We study QPT (quasi-polynomial tractability) in the worst case setting for linear tensor product problems defined over Hilbert spaces. We assume that the domain space is a reproducing kernel Hilbert space so that function values are well defined. We prove QPT for algorithms that use only function values under the three assumptions: 1.the minimal errors for the univariate case decay polynomially fast to zero,2.the largest singular value for the univariate case is simple and3.the eigenfunction corresponding to the largest singular value is a multiple of the function value at some point.The first two assumptions are necessary for QPT. The third assumption is necessary for QPT for some Hilbert spaces.

In a series of papers, in 1993, 1994 and 1996, Ian Sloan together with Harald Niederreiter introduced a modification of lattice rules for non-periodic functions, called “vertex modified lattice rules”, and a particular breed called “optimal vertex modified lattice rules”, see Numerical Integration IV (Birkhäuser 1993) pp. 253–265, J Comput Appl Math 51(1):57–70, 1994, and Comput Math Model 23(8–9):69–77, 1996. These are like standard lattice rules but they distribute the point at the origin to all corners of the unit cube, either by equally distributing the weight and so obtaining a multi-variate variant of the trapezoidal rule, or by choosing weights such that multilinear functions are integrated exactly. In the 1994 paper, Niederreiter and Sloan concentrate explicitly on Fibonacci lattice rules, which are a particular good choice of 2-dimensional lattice rules. Error bounds in this series of papers were given related to the star discrepancy.In this paper we pose the problem in terms of the so-called unanchored Sobolev space, which is a reproducing kernel Hilbert space often studied nowadays in which functions have L₂-integrable mixed first derivatives. It is known constructively that randomly shifted lattice rules, as well as deterministic tent-transformed lattice rules and deterministic fully symmetrized lattice rules can achieve close to O(N−1) convergence in this space, see Sloan et al. (Math Comput 71(240):1609–1640, 2002) and Dick et al. (Numer Math 126(2):259–291, 2014) respectively, where possible logs(N) $$\log ^{s}(N)$$ terms are taken care of by weighted function spaces.We derive a break down of the worst-case error of vertex modified lattice rules in the unanchored Sobolev space in terms of the worst-case error in a Korobov space, a multilinear space and some additional “mixture term”. For the 1-dimensional case this worst-case error is obvious and gives an explicit expression for the trapezoidal rule. In the 2-dimensional case this mixture term also takes on an explicit form for which we derive upper and lower bounds. For this case we prove that there exist lattice rules with a nice worst-case error bound with the additional mixture term of the form N−1log2(N) $$N^{-1}\log ^{2}(N)$$ .

The solution of many practical problems described by mathematical models requires approximation methods that give rise to linear(ized) systems of equations, solving which will determine the desired approximation. This short contribution describes a particularly effective solution approach for a certain class of so-called saddle-point linear systems which arises in different contexts.

Although quadrature methods for solving ill-posed integral equations of the first kind were introduced just after the publication of the classical papers on the regularization by A.N. Tikhonov and D.L. Phillips, there are still no known results on the convergence rate of such discretization. At the same time, some problems appearing in practice, such as Magnetic Particle Imaging (MPI), allow one only a discretization corresponding to a quadrature method. In the present paper we study the convergence rate of quadrature methods under general regularization scheme in the Reproducing Kernel Hilbert Space setting.

We compare the average errors of n-term linear and nonlinear approximations assuming that the coefficients in an orthogonal expansion of the approximated element are scaled i.i.d. random variables. We show that generally the n-term nonlinear approximation can be even exponentially better than the n-term linear approximation. On the other hand, if the scaling parameters decay no faster than polynomially then the average errors of nonlinear approximations do not converge to zero faster than those of linear approximations, as n → +∞. The main motivation and application is the approximation of Gaussian processes. In this particular case, the nonlinear approximation is, roughly, no more than n times better than its linear counterpart.

We survey a QMC approach to integral equations and develop some new applications to risk modeling. In particular, a rigorous error bound derived from Koksma-Hlawka type inequalities is achieved for certain expectations related to the probability of ruin in Markovian models. The method is based on a new concept of isotropic discrepancy and its applications to numerical integration. The theoretical results are complemented by numerical examples and computations.

In this note, we show that if a multidimensional sequence generates Hankel tensors and all the Hankel matrices, generated by this sequence, are positive semi-definite, then this sequence is a multidimensional moment sequence.

A novel resonant Ermakov-NLS system is introduced which admits symmetry reduction to a hybrid Ermakov-Painlevé II system. If the latter is Hamiltonian then combination with a characteristic Ermakov invariant provides an algorithmic integration procedure. The latter involves the isolation of positive solutions of a concomitant integrable Painlevé XXXIV equation. Explicit expressions for a multi-parameter class of wave packet representations for the original Ermakov-NLS system are obtained via the iterated application of a Bäcklund transformation admitted by the canonical Painlevé II equation.

For a point set of n elements in the d-dimensional unit cube and a class of test sets we are interested in the largest volume of a test set which does not contain any point. For all natural numbers n, d and under the assumption of the existence of a δ-cover with cardinality |Γ _δ | we prove that there is a point set, such that the largest volume of such a test set without any point is bounded above by log|Γδ|n+δ $$\frac {\log \vert \varGamma _\delta \vert }{n} + \delta $$ . For axis-parallel boxes on the unit cube this leads to a volume of at most 4dnlog(9nd) $$\frac {4d}{n}\log (\frac {9n}{d})$$ and on the torus to 4dnlog(2n) $$\frac {4d}{n}\log (2n)$$ .

When a matrix has a banded inverse there is a remarkable formula that quickly computes that inverse, using only local information in the original matrix. This local inverse formula holds more generally, for matrices with sparsity patterns that are examples of chordal graphs or perfect eliminators. The formula has a long history going back at least as far as the completion problem for covariance matrices with missing data. Maximum entropy estimates, log-determinants, rank conditions, the Nullity Theorem and wavelets are all closely related, and the formula has found wide applications in machine learning and graphical models. We describe that local inverse and explain how it can be understood as a matrix factorization.

In almost four decades, from the early 1970s until the first decade of this century, Ian Sloan has contributed immensely in the area of integral equation methods for elliptic boundary value problems. A search on MathSciNet with entries “Author=Sloan” and “Title=integral equation” reveals 44 papers. This review article sheds some lights on this historic path.

In this article, a qualocation method is formulated and analyzed for parabolic partial integro-differential equations in one space variable. Using a new Ritz–Volterra type projection, optimal rates of convergence are derived. Based on the second-order backward differentiation formula, a fully discrete scheme is formulated and a convergence analysis is derived. Results of numerical experiments are presented which support the theoretical results.

In this paper, we construct framelets associated with a sequence of quadrature rules on the simplex T2 in ℝ2 $$\mathbb {R}^{2}$$ . We give the framelet transforms—decomposition and reconstruction of the coefficients for framelets of a function on T2. We prove that the reconstruction is exact when the framelets are tight. We give an example of construction of framelets and show that the framelet transforms can be computed as fast as FFT.

The goal of this paper is to review, discuss and extend the current theory on multiscale radial basis functions for solving elliptic partial differential equations. Multiscale radial basis functions provide approximation spaces using different scales and shifts of a compactly supported, positive definite function in an orderly fashion. In this paper, both collocation and Galerkin approximation are described and analysed. To this end, first symmetric and non-symmetric recovery is discussed. Then, error estimates for both schemes are derived, though special emphasis is given to Galerkin approximation, since the current situation here is not as clear as in the case of collocation. We will distinguish between stationary and non-stationary multiscale approximation spaces and multilevel approximation schemes. For Galerkin approximation, we will establish error bounds in the stationary setting based upon Cea’s lemma showing that the approximation spaces are indeed rich enough. Unfortunately, convergence of a simple residual correction algorithm, which is often applied in this context to compute the approximation, can only be shown for a non-stationary multiscale approximation space.

A great deal of work has studied the tractability of approximating (in the L₂-norm) functions belonging to weighted unanchored Sobolev spaces of dominating mixed smoothness of order 1 over the unit d-cube. In this paper, we generalize these results. Let r and s be non-negative integers, with r ≤ s. We consider the approximation of complex-valued functions over the torus ??d=[0,2π]d $$\mathbb {T}^d=[0,2\pi ]^d$$ from weighted spaces HΓs,1(??d) $$H^{s,1}_\varGamma (\mathbb {T}^d)$$ of hybrid smoothness, measuring error in the Hr(??d) $$H^r(\mathbb {T}^d)$$ -norm. Here we have isotropic smoothness of order s, the derivatives of order s having dominating mixed smoothness of order 1. If r = s = 0, then H0,1(??d) $$H^{0,1}(\mathbb {T}^d)$$ is a well-known weighted unachored Sobolev space of dominating smoothness of order 1, whereas we have a generalization for other values of r and s. Besides its independent interest, this problem arises (with r = 1) in Galerkin methods for solving second-order elliptic problems. Suppose that continuous linear information is admissible. We show that this new approximation problem is topologically equivalent to the problem of approximating HΓs−r,1(??d) $$H^{s-r,1}_\varGamma (\mathbb {T}^d)$$ in the L2(??d) $$L_2(\mathbb {T}^d)$$ -norm, the equivalence being independent of d. It then follows that our new problem attains a given level of tractability if and only if approximating HΓs−r,1(??d) $$H^{s-r,1}_\varGamma (\mathbb {T}^d)$$ in the L2(??d) $$L_2(\mathbb {T}^d)$$ -norm has the same level of tractability. We further compare the tractability of our problem to that of L2(??d) $$L_2(\mathbb {T}^d)$$ -approximation for HΓ0,1(??d) $$H^{0,1}_\varGamma (\mathbb {T}^d)$$ . We then analyze the tractability of our problem for various families of weights.

Spherical t-designs on ??d⊂ℝd+1 $$\mathbb {S}^{d}\subset \mathbb {R}^{d+1}$$ provide N nodes for an equal weight numerical integration rule which is exact for all spherical polynomials of degree at most t. This paper considers the generation of efficient, where N is comparable to (1 + t)d∕d, spherical t-designs with good geometric properties as measured by their mesh ratio, the ratio of the covering radius to the packing radius. Results for ??2 $$\mathbb {S}^{2}$$ include computed spherical t-designs for t = 1, …, 180 and symmetric (antipodal) t-designs for degrees up to 325, all with low mesh ratios. These point sets provide excellent points for numerical integration on the sphere. The methods can also be used to computationally explore spherical t-designs for d = 3 and higher.

The nodes of certain minimal cubature rule are real common zeros of a set of orthogonal polynomials of degree n. They often consist of a well distributed set of points and interpolation polynomials based on them have desired convergence behavior. We report what is known and the theory behind by explaining the situation when the domain of integrals is a square.

The original version of Chapter 12 was inadvertently published with incorrect details. The theorems 10, 12 and 13 have been updated.