Search

Wasserstein balls, which contain all probability measures within a pre-specified Wasserstein distance to a reference measure, have recently enjoyed wide popularity in the distributionally robust optimization and machine learning communities to formulate and solve data-driven optimization problems with rigorous statistical guarantees. In this technical note we prove that the Wasserstein ball is weakly compact under mild conditions, and we offer necessary and sufficient conditions for the existence of optimal solutions. We also characterize the sparsity of solutions if the Wasserstein ball is centred at a discrete reference measure. In comparison with the existing literature, which has proved similar results under different conditions, our proofs are self-contained and shorter, yet mathematically rigorous, and our necessary and sufficient conditions for the existence of optimal solutions are easily verifiable in practice.

We give asymptotically converging semidefinite programming hierarchies of outer bounds on bilinear programs of the form $\mathrm{Tr}\big[M(X\otimes Y)\big]$, maximized with respect to semidefinite constraints on $X$ and $Y$. Applied to the problem of quantum error correction this gives hierarchies of efficiently computable outer bounds on the optimal fidelity for any message dimension and error model. The first level of our hierarchies corresponds to the non-signalling assisted fidelity previously studied by [Leung & Matthews, IEEE Trans.~Inf.~Theory 2015], and positive partial transpose constraints can be added and used to give a sufficient criterion for the exact convergence at a given level of the hierarchy. To quantify the worst case convergence speed of our hierarchies, we derive novel quantum de Finetti theorems that allow imposing linear constraints on the approximating state. In particular, we give finite de Finetti theorems for quantum channels, quantifying closeness to the convex hull of product channels as well as closeness to local operations and classical forward communication assisted channels. As a special case this constitutes a finite version of Fuchs-Schack-Scudo's asymptotic de Finetti theorem for quantum channels. Finally, our proof methods also allow us to answer an open question from [Brand��o & Harrow, STOC 2013] by improving the approximation factor of de Finetti theorems with no symmetry from $O(d^{k/2})$ to $\mathrm{poly}(d,k)$, where $d$ denotes local dimension and $k$ the number of copies., 33 pages, New Title, v3

As a tractable approach, regularization is frequently adopted in sparse optimization. This gives rise to regularized optimization, which aims to minimize the ℓ0 norm or its continuous surrogates that characterize the sparsity. From the continuity of surrogates to the discreteness of the ℓ0 norm, the most challenging model is the ℓ0-regularized optimization. There is an impressive body of work on the development of numerical algorithms to overcome this challenge. However, most of the developed methods only ensure that either the (sub)sequence converges to a stationary point from the deterministic optimization perspective or that the distance between each iteration and any given sparse reference point is bounded by an error bound in the sense of probability. In this paper, we develop a Newton-type method for the ℓ0-regularized optimization and prove that the generated sequence converges to a stationary point globally and quadratically under the standard assumptions, theoretically explaining that our method can perform surprisingly well.

The main objective of this paper is to define a logic for reasoning about distributed time-stamped claims. Such a logic is interesting for theoretical reasons, i.e., as a logic per se, but also because it has a number of practical applications, in particular when one needs to reason about a huge amount of pieces of evidence collected from different sources, where some of the pieces of evidence may be contradictory and some sources are considered to be more trustworthy than others. We introduce the Time-Stamped Claim Logic including a sound and complete sequent calculus that allows one to reduce the size of the collected set of evidence and removes inconsistencies, i.e., the logic ensures that the result is consistent with respect to the trust relations considered. In order to show how Time-Stamped Claim Logic can be used in practice, we consider a concrete cyber-attribution case study.

The need for efficient tools is pressing in the era of big data, particularly in streaming data applications. As data streams are ubiquitous, the ability to accurately detect multiple changepoints, without affecting the continuous flow of data, is an important issue. Change detection for categorical data streams is understudied, and existing work commonly introduces fixed control parameters while providing little insight into how they may be chosen. This is ill-suited to the streaming paradigm, motivating the need for an approach that introduces few parameters which may be set without requiring any prior knowledge of the stream. This paper introduces such a method, which can accurately detect changepoints in categorical data streams with fixed storage and computational requirements. The detector relies on the ability to adaptively monitor the category probabilities of a multinomial distribution, where temporal adaptivity is introduced using forgetting factors. A novel adaptive threshold is also developed which can be computed given a desired false positive rate. This method is then compared to sequential and nonsequential change detectors in a large simulation study which verifies the usefulness of our approach. A real data set consisting of nearly 40 million events from a computer network is also investigated.

What computational methods should be used to achieve the most reliable result in computational structure elucidation? A study on the effect of quality and quantity of geometries on computational NMR structure elucidation performance is reported. Semi-empirical, HF and DFT methods were explored, and B3LYP optimized geometries in combination with mPW1PW91 shifts and M06-2X conformer energies was found to be best. The required number of conformers considered has also been investigated, as well as several methods for the reduction of this number. Clear guidelines for the best computational NMR structure elucidation methods for different levels of available computing power are provided.

This paper presents an isogeometric (IGA) solver for steady-state incompressiblemagnetohydrodynamics (MHD). MHD is the study of the behavior of electrically conducting fluidsand can be viewed mathematically as a coupled system: the Navier--Stokes equations (for the fluid)and a reduced form of Maxwell's equations (for the electromagnetic field). A key feature of MHDflow is the potential development of very strong shear, usually in proximity to walls. This resultsin two correlated demands on numerical simulation: the need to represent the geometry and thenear-wall shear accurately. In addition, for both the Navier--Stokes and the Maxwell's equations,appropriate discretizations are required for the problem to be well-posed. IGA analysis is a variant ofthe conventional finite element (FE) method, but utilizing the underlying approximations commonlyused in computer-aided design (CAD) to represent geometry, basis functions, and test functions.As a result, IGA can represent curved shapes such as circles and conic sections exactly using B-splines and nonuniform rational B-splines (NURBS). Furthermore, IGA can obtain much improvedaccuracy in the computed solution, for a given number of degrees of freedom, due to its inherentsmoothness and higher continuity of basis functions when compared with standard FE and finitevolume (FV) methods. To address the issue of well-posedness, a set of stable IGA discretizationsfor the Navier--Stokes and Maxwell's equations is developed and incorporated into the IGA solver.A detailed convergence study is carried out to verify the convergence, accuracy, and performance ofthe IGA scheme for certain benchmark cases.

In this work, we showcase SGTPy, a Python open-source code developed to calculate interfacial properties (interfacial concentration profiles and interfacial or surface tension) for pure fluids and fluid mixtures. SGTPy employs the Square Gradient Theory (SGT) coupled to the Statistical Associating Fluid Theory of Variable Range employing a Mie potential (SAFT-VR-Mie). SGTPy uses standard Python numerical packages (i.e., NumPy, SciPy) and can be used under Jupyter notebooks. Its features are the calculation of phase stability, phase equilibria, interfacial properties, and the optimization of the SGT and SAFT parameters for vapor–liquid, liquid–liquid and vapor–liquid–liquid equilibria for pure fluids and multicomponent mixtures. Phase equilibrium calculations include two-phase and multiphase flash, bubble and dew points, and the tangent plane distance. For the computation of interfacial properties, SGTPy incorporates several options to solve the interfacial concentration, such as the path technique, an auxiliary time function, and orthogonal collocation. Additionally, the SGTPy code allows the inclusion of subroutines from other languages (e.g., Fortran, and C++) through Cython and f2py Python tools, which opens the possibility for future extensions or recycling tested and optimized subroutines from other codes. Supporting Information includes a review of the theoretical expressions required to couple SAFT-VR-Mie equation of state with the SGT. The use and capabilities of SGTPy are illustrated through step by step examples written on Jupyter notebooks for the cases of pure fluids and binary and ternary mixtures in bi- and three- phasic equilibria. The SGTPy code can be downloaded from https://github.com/gustavochm/SGTPy.

We consider the modeling of data generated by a latent continuous-time Markov jump process with a state space of finite but unknown dimensions. Typically in such models, the number of states has to be pre-specified, and Bayesian inference for a fixed number of states has not been studied until recently. In addition, although approaches to address the problem for discrete-time models have been developed, no method has been successfully implemented for the continuous-time case. We focus on reversible jump Markov chain Monte Carlo which allows the trans-dimensional move among different numbers of states in order to perform Bayesian inference for the unknown number of states. Specifically, we propose an efficient split-combine move which can facilitate the exploration of the parameter space, and demonstrate that it can be implemented effectively at scale. Subsequently, we extend this algorithm to the context of model-based clustering, allowing numbers of states and clusters both determined during the analysis. The model formulation, inference methodology, and associated algorithm are illustrated by simulation studies. Finally, we apply this method to real data from a Canadian healthcare system in Quebec. Supplementary Information The online version supplementary material available at 10.1007/s11222-021-10032-8.

We propose high-order well-balanced finite-volume schemes for a broad class of hydrodynamic systems with attractive-repulsive interaction forces and linear and nonlinear damping. Our schemes are suitable for free energies containing convolutions of an interaction potential with the density, which are essential for applications such as the Keller--Segel model, more general Euler--Poisson systems, or dynamic-density functional theory. Our schemes are also equipped with a nonnegative-density reconstruction which allows for vacuum regions during the simulation. We provide several prototypical examples from relevant applications highlighting the benefit of our algorithms and also elucidate some of our analytical results.

We introduce and analyze a parallel sequential Monte Carlo methodology for the numerical solution of optimization problems that involve the minimization of a cost function that consists of the sum of many individual components. The proposed scheme is a stochastic zeroth order optimization algorithm which demands only the capability to evaluate small subsets of components of the cost function. It can be depicted as a bank of samplers that generate particle approximations of several sequences of probability measures. These measures are constructed in such a way that they have associated probability density functions whose global maxima coincide with the global minima of the original cost function. The algorithm selects the best performing sampler and uses it to approximate a global minimum of the cost function. We prove analytically that the resulting estimator converges to a global minimum of the cost function almost surely and provide explicit convergence rates in terms of the number of generated Monte Carlo samples and the dimension of the search space. We show, by way of numerical examples, that the algorithm can tackle cost functions with multiple minima or with broad "flat" regions which are hard to minimize using gradient-based techniques., Comment: Statistics and Computing volume 30, (2020). Published at https://link.springer.com/article/10.1007/s11222-020-09964-4

A new multi-fidelity modelling-based probabilistic optimisation framework for composite structures is presented in this paper. The multi-fidelity formulation developed herein significantly reduces the required computational time, allowing for more design variables to be considered early in the design stage. Multi-fidelity models are created by the use of finite element models, surrogate models and response correction surfaces. The accuracy and computational efficiency of the proposed optimisation methodology are demonstrated in two engineering examples of composite structures: a reliability analysis, and a reliability-based design optimisation. In these two benchmark examples, each random design variable is assigned an expected level of uncertainty. Monte Carlo Simulation (MCS), the First-Order Reliability Method (FORM) and the Second-Order Reliability Method (SORM) are used within the multi-fidelity framework to calculate the probability of failure. The reliability optimisation is a multi-objective problem that finds the optimal front, which provides both the maximum linear buckling load and minimum mass. The results show that multi-fidelity models provide high levels of accuracy while reducing computation time drastically.

Spectral embedding of adjacency or Laplacian matrices of undirected graphs is a common technique for representing a network in a lower dimensional latent space, with optimal theoretical guarantees. The embedding can be used to estimate the community structure of the network, with strong consistency results in the stochastic blockmodel framework. One of the main practical limitations of standard algorithms for community detection from spectral embeddings is that the number of communities and the latent dimension of the embedding must be specified in advance. In this article, a novel Bayesian model for simultaneous and automatic selection of the appropriate dimension of the latent space and the number of blocks is proposed. Extensions to directed and bipartite graphs are discussed. The model is tested on simulated and real world network data, showing promising performance for recovering latent community structure.

We propose a new splitting scheme for general reaction–taxis–diffusion systems in one spatial dimension capable to deal with simultaneous concentrated and diffusive regions as well as travelling waves and merging phenomena. The splitting scheme is based on a mass transport strategy for the cell density coupled with classical finite element approximations for the rest of the system. The built-in mass adaption of the scheme allows for an excellent performance even with respect to dedicated mesh-adapted AMR schemes in original variables.

We prove that a known general approach to improve Shamir’s celebrated secret sharing scheme; i.e., adding an information-theoretic authentication tag to the secret, can make it robust for n parties against any collusion of size $$\delta n$$ , for any constant $$\delta \in (0, 1/2)$$ . Shamir’s original scheme is robust for all $$\delta \in (0,1/3)$$ . Beyond that, we employ the best known list decoding algorithms for Reed-Solomon codes and show that, with high probability, only the correct secret maintains the correct information-theoretic tag if an algebraic manipulation detection (AMD) code is used to tag secrets. This result holds in the so-called “non-rushing” model in which the n shares are submitted simultaneously for reconstruction. We thus obtain a fully explicit and robust secret sharing scheme in this model that is essentially optimal in all parameters including the share size which is $$k(1+o(1)) + O(\kappa )$$ , where k is the secret length and $$\kappa $$ is the security parameter. Like Shamir’s scheme, in this modified scheme any set of more than $$\delta n$$ honest parties can efficiently recover the secret. Using algebraic geometry codes instead of Reed-Solomon codes, the share length can be decreased to a constant (only depending on $$\delta $$ ) while the number of shares n can grow independently. In this case, when n is large enough, the scheme satisfies the “threshold” requirement in an approximate sense; i.e., any set of $$\delta n(1+\rho )$$ honest parties, for arbitrarily small $$\rho > 0$$ , can efficiently reconstruct the secret. From a practical perspective, the main importance of our result is in showing that existing systems employing Shamir-type secret sharing schemes can be made much more robust than previously thought with minimal change, essentially only involving the addition of a short and simple checksum to the original data.

International audience; In this paper we advance the state-of-the-art on the application of second-order propositional modal logic (SOPML) in the representation of individual and group knowledge, as well as temporal and spatial reasoning. The main theoretical contributions of the paper can be summarised as follows. Firstly, we introduce the language of (multi-modal) SOPML and interpret it on a variety of different classes of Kripke frames according to the features of the accessibility relations and of the algebraic structure of the quantification domain of propositions. We provide axiomatisations for some of these classes, and show that SOPML is unaxiomatisable on the remaining classes. Secondly, we introduce novel notions of (bi)simulations and prove that they indeed preserve the interpretation of formulas in (the universal fragment of) SOPML. Then, we apply this formal machinery to study the expressiveness of Second-order Propositional Epistemic Logic (SOPEL) in representing higher-order knowledge, i.e., the knowledge agents have about other agents’ knowledge, as well as graph-theoretic notions (e.g., 3-colorability, Hamiltonian paths, etc.). The final outcome is a rich formalism to represent and reason about relevant concepts in artificial intelligence, while still having a model checking problem that is no more computationally expensive than that of the less expressive quantified boolean logic.

Stencil computations are a key part of many high-performance computing applications, such as image processing, convolutional neural networks, and finite-difference solvers for partial differential equations. Devito is a framework capable of generating highly-optimized code given symbolic equations expressed in Python, specialized in, but not limited to, affine (stencil) codes. The lowering process---from mathematical equations down to C++ code---is performed by the Devito compiler through a series of intermediate representations. Several performance optimizations are introduced, including advanced common sub-expressions elimination, tiling and parallelization. Some of these are obtained through well-established stencil optimizers, integrated in the back-end of the Devito compiler. The architecture of the Devito compiler, as well as the performance optimizations that are applied when generating code, are presented. The effectiveness of such performance optimizations is demonstrated using operators drawn from seismic imaging applications., Submitted to ACM Transactions on Mathematical Software

We derive sharp probability bounds on the tails of a product of symmetric nonnegative random variables using only information about their first two moments. If the covariance matrix of the random variables is known exactly, these bounds can be computed numerically using semidefinite programming. If only an upper bound on the covariance matrix is available, the probability bounds on the right tails can be evaluated analytically. The bounds under precise and imprecise covariance information coincide for all left tails as well as for all right tails corresponding to quantiles that are either sufficiently small or sufficiently large. We also prove that all left probability bounds reduce to the trivial bound 1 if the number of random variables in the product exceeds an explicit threshold. Thus, in the worst case, the weak-sense geometric random walk defined through the running product of the random variables is absorbed at 0 with certainty as soon as time exceeds the given threshold. The techniques devised for constructing Chebyshev bounds for products can also be used to derive Chebyshev bounds for sums, maxima, and minima of nonnegative random variables.

Traditionally most of the work in the field of Inductive Logic Programming (ILP) has addressed the problem of learning Prolog programs. On the other hand, Answer Set Programming is increasingly being used as a powerful language for knowledge representation and reasoning, and is also gaining increasing attention in industry. Consequently, the research activity in ILP has widened to the area of Answer Set Programming, witnessing the proposal of several new learning frameworks that have extended ILP to learning answer set programs. In this paper, we investigate the theoretical properties of these existing frameworks for learning programs under the answer set semantics. Specifically, we present a detailed analysis of the computational complexity of each of these frameworks with respect to the two decision problems of deciding whether a hypothesis is a solution of a learning task and deciding whether a learning task has any solutions. We introduce a new notion of generality of a learning framework, which enables us to define a framework to be more general than another in terms of being able to distinguish one ASP hypothesis solution from a set of incorrect ASP programs. Based on this notion, we formally prove a generality relation over the set of existing frameworks for learning programs under answer set semantics. In particular, we show that our recently proposed framework, Context-dependent Learning from Ordered Answer Sets, is more general than brave induction, induction of stable models, and cautious induction, and maintains the same complexity as cautious induction, which has the highest complexity of these frameworks.

In this paper, we present new upscaled HDG methods for Brinkman equations in the context of high-contrast heterogeneous media. The a priori error estimates are derived in terms of both fine and coarse scale parameters that depend on the high-contrast coefficient weakly. Due to the heterogeneity of the problem, a huge global system will be produced after the numerical discretization of HDG method. Thanks to the upscaled structure of the proposed methods, we are able to reduce the huge global system onto the skeleton of the coarse mesh only while still capturing important fine scale features of this problem. The finite element space over the coarse mesh is irrelevant to the fine scale computation. This feature makes our proposed method very attractive. Several numerical examples are presented to support our theoretical findings.

We introduce a new finite element (FE) discretization framework applicable for covariant split equations. The introduction of additional differential forms (DF) that form pairs with the original ones permits the splitting of the equations into topological momentum and continuity equations and metric-dependent closure equations that apply the Hodge-star operator. Our discretization framework conserves this geometrical structure and provides for all DFs proper FE spaces such that the differential operators (here gradient and divergence) hold in strong form. We introduce lowest possible order discretizations of the split 1D wave equations, in which the discrete momentum and continuity equations follow by trivial projections onto piecewise constant FE spaces, omitting partial integrations. Approximating the Hodge-star by nontrivial Galerkin projections (GP), the two discrete metric equations follow by projections onto either the piecewise constant (GP0) or piecewise linear (GP1) space. Out of the four possible realizations, our framework gives us three schemes with significantly different behavior. The split scheme using twice GP1 is unstable and shares the dispersion relation with the P1–P1 FE scheme that approximates both variables by piecewise linear spaces (P1). The split schemes that apply a mixture of GP1 and GP0 share the dispersion relation with the stable P1–P0 FE scheme that applies piecewise linear and piecewise constant (P0) spaces. However, the split schemes exhibit second order convergence for both quantities of interest. For the split scheme applying twice GP0, we are not aware of a corresponding standard formulation to compare with. Though it does not provide a satisfactory approximation of the dispersion relation as short waves are propagated much too fast, the discovery of the new scheme illustrates the potential of our discretization framework as a toolbox to study and find FE schemes by new combinations of FE spaces.

We show characterisation results for normalisation, head-normalisation, and strong normalisation for λ μ using intersection types. We reach these results for a strict notion of type assignment for λ μ that is the natural restriction of the domain-based system of van Bakel et al. (2011) for λ μ by limiting the type inclusion relation to just intersection elimination. We show that this system respects β μ-equality, by showing both soundness and completeness results. We then define a notion of reduction on derivations that corresponds to cut-elimination, and show that this is strongly normalisable. We use this strong normalisation result to show an approximation result, and through that a characterisation of head-normalisation. Using the approximation result, we show that there is a very strong relation between the system of van Bakel et al. (2011) and ours. We then introduce a notion of type assignment that eliminates ω as an assignable type, and show, using the strong normalisation result for derivation reduction, that all terms typeable in this system are strongly normalisable as well, and show that all strongly normalisable terms are typeable. We conclude by adding type variables to our system, and show that system essentially is that of van Bakel (2010b).

We consider a non-linear filtering problem, whereby the signal obeys the stochastic Navier-Stokes equations and is observed through a linear mapping with additive noise. The setup is relevant to data assimilation for numerical weather prediction and climate modelling, where similar models are used for unknown ocean or wind velocities. We present a particle filtering methodology that uses likelihood informed importance proposals, adaptive tempering, and a small number of appropriate Markov Chain Monte Carlo steps. We provide a detailed design for each of these steps and show in our numerical examples that they are all crucial in terms of achieving good performance and efficiency.

A fast algorithm (linear in the degrees of freedom) for the solution of linear variable-coefficient rational-order fractional integral and differential equations is described. The approach is related to the ultraspherical method for ODEs [S. Olver and A. Townsend, SIAM Rev., 55 (2013), pp. 462--489] and involves constructing two different bases, one for the domain of the operator and one for the range of the operator. The bases are constructed from direct sums of suitably weighted ultraspherical or Jacobi polynomial expansions, for which explicit representations of fractional integrals and derivatives are known, and are carefully chosen so that the resulting operators are banded or almost banded. Geometric convergence is demonstrated for numerous model problems when the variable coefficients and right-hand side are sufficiently smooth.

Testing membership in lattices is of practical relevance, with applications to integer programming, error detection in lattice-based communication, and cryptography. In this work, we initiate a systematic study of local testing for membership in lattices, complementing and building upon the extensive body of work on locally testable codes. In particular, we formally define the notion of local tests for lattices and present the following: 1. We show that in order to achieve low query complexity, it is sufficient to design $1$-sided nonadaptive canonical tests. This result is akin to, and based on, an analogous result for error-correcting codes due to [E. Ben-Sasson, P. Harsha, and S. Raskhodnikova, SIAM J. Comput., 35 (2005), pp. 1--21]. 2. We demonstrate upper and lower bounds on the query complexity of local testing for membership in code formula lattices. We instantiate our results for code formula lattices constructed from Reed--Muller codes to obtain nearly matching upper and lower bounds on the query complexity of testing such lattices. 3. We contrast lattice testing to code testing by showing lower bounds on the query complexity of testing low-dimensional lattices. This illustrates large lower bounds on the query complexity of testing membership in the well-known knapsack lattices. On the other hand, we show that knapsack lattices with bounded coefficients have low-query testers if the inputs are promised to lie in the span of the lattice.

We propose a complete-search algorithm for solving a class of non-convex, possibly infinite-dimensional, optimization problems to global optimality. We assume that the optimization variables are in a bounded subset of a Hilbert space, and we determine worst-case run-time bounds for the algorithm under certain regularity conditions of the cost functional and the constraint set. Because these run-time bounds are independent of the number of optimization variables and, in particular, are valid for optimization problems with infinitely many optimization variables, we prove that the algorithm converges to an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon $$\end{document}ε-suboptimal global solution within finite run-time for any given termination tolerance \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon > 0$$\end{document}ε>0. Finally, we illustrate these results for a problem of calculus of variations.

Accurate estimation of error covariances (both background and observation) is crucial for efficient observation compression approaches in data assimilation of large-scale dynamical problems. We propose a new combination of a covariance tuning algorithm with existing PCA-type data compression approaches, either observation- or information-based, with the aim of reducing the computational cost of real-time updating at each assimilation step. Relying on a local assumption of flow-independent error covariances, dynamical assimilation residuals are used to adjust the covariance in each assimilation window. The estimated covariances then contribute to better specify the principal components of either the observation dynamics or the state-observation sensitivity. The proposed approaches are first validated on a shallow water twin experiment with correlated and non-homogeneous observation error. Proper selection of flow-independent assimilation windows, together with sampling density for background error estimation, and sensitivity of the approaches to the observations error covariance knowledge, are also discussed and illustrated with various numerical tests and results. The method is then applied to a more challenging industrial hydrological model with real-world data and non-linear transformation operator provided by an operational precipitation-flow simulation software.

We here harmonise two significant contributions to the field of wavelet analysis in the past two decades, namely the locally stationary wavelet process and the family of dual-tree complex wavelets. By combining these two components, we furnish a statistical model that can simultaneously access benefits from these two constructions. On the one hand, our model borrows the debiased spectrum and auto-covariance estimator from the locally stationary wavelet model. On the other hand, the enhanced directional selectivity is obtained from the dual-tree complex wavelets over the regular lattice. The resulting model allows for the description and identification of wavelet fields with significantly more directional fidelity than was previously possible. The corresponding estimation theory is established for the new model, and some stationarity detection experiments illustrate its practicality.

Recently, there has been an increasing interest in non-autonomous composition of perturbed hyperbolic systems: composing perturbations of a given hyperbolic map$F$results in statistical behaviour close to that of$F$. We show this fact in the case of piecewise regular expanding maps. In particular, we impose conditions on perturbations of this class of maps that include situations slightly more general than what has been considered so far, and prove that these are stochastically stable in the usual sense. We then prove that the evolution of a given distribution of mass under composition of time-dependent perturbations (arbitrarily—rather than randomly—chosen at each step) close to a given map$F$remains close to the invariant mass distribution of$F$. Moreover, for almost every point, Birkhoff averages along trajectories do not fluctuate wildly. This result complements recent results on memory loss for non-autonomous dynamical systems.

For higher-order (process) languages, characterising contextual equivalence is a long-standing issue. In the setting of a higher-order \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\pi $$\end{document}π-calculus with session types, we develop characteristic bisimilarity, a typed bisimilarity which fully characterises contextual equivalence. To our knowledge, ours is the first characterisation of its kind. Using simple values inhabiting (session) types, our approach distinguishes from untyped methods for characterising contextual equivalence in higher-order processes: we show that observing as inputs only a precise finite set of higher-order values suffices to reason about higher-order session processes. We demonstrate how characteristic bisimilarity can be used to justify optimisations in session protocols with mobile code communication.

Record linkage is the process of identifying and linking records about the same entities from one or more databases. Record linkage can be viewed as a classification problem where the aim is to decide whether a pair of records is a match (i.e. two records refer to the same real-world entity) or a non-match (two records refer to two different entities). Various classification techniques—including supervised, unsupervised, semi-supervised and active learning based—have been employed for record linkage. If ground truth data in the form of known true matches and non-matches are available, the quality of classified links can be evaluated. Due to the generally high class imbalance in record linkage problems, standard accuracy or misclassification rate are not meaningful for assessing the quality of a set of linked records. Instead, precision and recall, as commonly used in information retrieval and machine learning, are used. These are often combined into the popular F-measure, which is the harmonic mean of precision and recall. We show that the F-measure can also be expressed as a weighted sum of precision and recall, with weights which depend on the linkage method being used. This reformulation reveals that the F-measure has a major conceptual weakness: the relative importance assigned to precision and recall should be an aspect of the problem and the researcher or user, but not of the particular linkage method being used. We suggest alternative measures which do not suffer from this fundamental flaw.

We present an algorithm for the optimization of a class of finite-element integration loop nests. This algorithm, which exploits fundamental mathematical properties of finite-element operators, is proven to achieve a locally optimal operation count. In specified circumstances the optimum achieved is global. Extensive numerical experiments demonstrate significant performance improvements over the state of the art in finite-element code generation in almost all cases. This validates the effectiveness of the algorithm presented here and illustrates its limitations.

We study a variant of the capacitated vehicle routing problem (CVRP), which asks for the cost-optimal delivery of a single product to geographically dispersed customers through a fleet of capacity-constrained vehicles. Contrary to the classical CVRP, which assumes that the customer demands are deterministic, we model the demands as a random vector whose distribution is only known to belong to an ambiguity set. We then require the delivery schedule to be feasible with a probability of at least 1 − e, where e characterizes the risk tolerance of the decision maker. We argue that the emerging distributionally robust CVRP can be solved efficiently with standard branch-and-cut algorithms whenever the ambiguity set satisfies a subadditivity condition. We then show that this subadditivity condition holds for a large class of moment ambiguity sets. We derive efficient cut generation schemes for ambiguity sets that specify the support as well as (bounds on) the first and second moments of the customer demands. Our numerical results indicate that the distributionally robust CVRP has favorable scaling properties and can often be solved in runtimes comparable to those of the deterministic CVRP.

We investigate a new sampling scheme aimed at improving the performance of particle filters whenever (a) there is a significant mismatch between the assumed model dynamics and the actual system, or (b) the posterior probability tends to concentrate in relatively small regions of the state space. The proposed scheme pushes some particles toward specific regions where the likelihood is expected to be high, an operation known as nudging in the geophysics literature. We reinterpret nudging in a form applicable to any particle filtering scheme, as it does not involve any changes in the rest of the algorithm. Since the particles are modified, but the importance weights do not account for this modification, the use of nudging leads to additional bias in the resulting estimators. However, we prove analytically that nudged particle filters can still attain asymptotic convergence with the same error rates as conventional particle methods. Simple analysis also yields an alternative interpretation of the nudging operation that explains its robustness to model errors. Finally, we show numerical results that illustrate the improvements that can be attained using the proposed scheme. In particular, we present nonlinear tracking examples with synthetic data and a model inference example using real-world financial data.

In this paper, we demonstrate that many of the computational tools for univariate orthogonal polynomials have analogues for a family of bivariate orthogonal polynomials on the triangle, including Clenshaw's algorithm and sparse differentiation operators. This allows us to derive a practical spectral method for solving linear partial differential equations on triangles with sparse discretizations. We can thereby rapidly solve partial differential equations using polynomials with degrees in the thousands, resulting in sparse discretizations with as many as several million degrees of freedom.

We consider the numerical approximation of theL2–gradient flow of general curvatureenergies∫G(|~κ|) for a curve inRd,d≥2. Here the curve can be either closed, or it can be open andclamped at the end points. These general curvature energies, and the considered boundary conditions,appear in the modelling of the power loss within an optical fibre. We present two alternative finiteelement approximations, both of which admit a discrete gradient flow structure. Apart from beingstable, in addition, one of the methods satisfies an equidistribution property. Numerical resultsdemonstrate the robustness and the accuracy of the proposedmethods.

Inspired by multigrid methods for linear systems of equations, multilevel optimization methods have been proposed to solve structured optimization problems. Multilevel methods make more assumptions regarding the structure of the optimization model, and as a result, they outperform single-level methods, especially for large-scale models. The impressive performance of multilevel optimization methods is an empirical observation, and no theoretical explanation has so far been proposed. In order to address this issue, we study the convergence properties of a multilevel method that is motivated by second-order methods. We take the first step toward establishing how the structure of an optimization problem is related to the convergence rate of multilevel algorithms.

Publication rights licensed to ACM. Sparse tiling is a technique to fuse loops that access common data, thus increasing data locality. Unlike traditional loop fusion or blocking, the loops may have different iteration spaces and access shared datasets through indirect memory accesses, such as A[map[i]]-hence the name “sparse.” One notable example of such loops arises in discontinuous-Galerkin finite element methods, because of the computation of numerical integrals over different domains (e.g., cells, facets). The major challenge with sparse tiling is implementation-not only is it cumbersome to understand and synthesize, but it is also onerous to maintain and generalize, as it requires a complete rewrite of the bulk of the numerical computation. In this article, we propose an approach to extend the applicability of sparse tiling based on raising the level of abstraction. Through a sequence of compiler passes, the mathematical specification of a problem is progressively lowered, and eventually sparse-tiled C for-loops are generated. Besides automation, we advance the state-of-the-art by introducing a revisited, more efficient sparse tiling algorithm; support for distributed-memory parallelism; a range of fine-grained optimizations for increased runtime performance; implementation in a publicly available library, SLOPE; and an in-depth study of the performance impact in Seigen, a real-world elastic wave equation solver for seismological problems, which shows speed-ups up to 1.28× on a platform consisting of 896 Intel Broadwell cores.

Spatial count data models are used to explain and predict the frequency of phenomena such as traffic accidents in geographically distinct entities such as census tracts or road segments. These models are typically estimated using Bayesian Markov chain Monte Carlo (MCMC) simulation methods, which, however, are computationally expensive and do not scale well to large datasets. Variational Bayes (VB), a method from machine learning, addresses the shortcomings of MCMC by casting Bayesian estimation as an optimisation problem instead of a simulation problem. Considering all these advantages of VB, a VB method is derived for posterior inference in negative binomial models with unobserved parameter heterogeneity and spatial dependence. Polya-Gamma augmentation is used to deal with the non-conjugacy of the negative binomial likelihood and an integrated non-factorised specification of the variational distribution is adopted to capture posterior dependencies. The benefits of the proposed approach are demonstrated in a Monte Carlo study and an empirical application on estimating youth pedestrian injury counts in census tracts of New York City. The VB approach is around 45 to 50 times faster than MCMC on a regular eight-core processor in a simulation and an empirical study, while offering similar estimation and predictive accuracy. Conditional on the availability of computational resources, the embarrassingly parallel architecture of the proposed VB method can be exploited to further accelerate its estimation by up to 20 times. (C) 2020 Elsevier B.V. All rights reserved.

© Marco Carbone, Fabrizio Montesi, Carsten Schürmann, and Nobuko Yoshida; licensed under Creative Commons License CC-BY.We propose a Curry-Howard correspondence between a language for programming multiparty sessions and a generalisation of Classical Linear Logic (CLL). In this framework, propositions correspond to the local behaviour of a participant in a multiparty session type, proofs to processes, and proof normalisation to executing communications. Our key contribution is generalising duality, from CLL, to a new notion of n-ary compatibility, called coherence. Building on coherence as a principle of compositionality, we generalise the cut rule of CLL to a new rule for composing many processes communicating in a multiparty session. We prove the soundness of our model by showing the admissibility of our new rule, which entails deadlock-freedom via our correspondence.

We present a parametric finite element approximation of a fluidic membrane, whose evolution is governed by a surface Navier–Stokes equation coupled to bulk Navier–Stokes equations. The elastic properties of the membrane are modelled with the help of curvature energies of Willmore and Helfrich type. Forces stemming from these energies act on the surface fluid, together with a forcing from the bulk fluid. Using ideas from PDE constrained optimization, a weak formulation is derived, which allows for a stable semi-discretization. An important new feature of the present work is that we are able to also deal with spontaneous curvature and an area difference elasticity contribution in the curvature energy. This allows for the modelling of asymmetric membranes, which compared to the symmetric case lead to quite different shapes. This is demonstrated in the numerical computations presented.

Data streams are characterised by a potentially unending sequence of high-frequency observations which are subject to unknown temporal variation. Many modern streaming applications demand the capability to sequentially detect changes as soon as possible after they occur, while continuing to monitor the stream as it evolves. We refer to this problem as continuous monitoring. Sequential algorithms such as CUSUM, EWMA and their more sophisticated variants usually require a pair of parameters to be selected for practical application. However, the choice of parameter values is often based on the anticipated size of the changes and a given choice is unlikely to be optimal for the multiple change sizes which are likely to occur in a streaming data context. To address this critical issue, we introduce a changepoint detection framework based on adaptive forgetting factors that, instead of multiple control parameters, only requires a single parameter to be selected. Simulated results demonstrate that this framework has utility in a continuous monitoring setting. In particular, it reduces the burden of selecting parameters in advance. Moreover, the methodology is demonstrated on real data arising from Foreign Exchange markets.

We analyse a stochastic control problem for the valuation of a natural gas storage facility while taking into account operating characteristics. The underlying natural gas spot price dynamics is assumed to follow a time-inhomogeneous exponential Levy process [4]. This underlying incorporates common features of gas spot prices such as seasonality, mean-reversion and price spikes with seasonal jump intensities. The corresponding HJB equation is the nonlinear PIDE which is solved by an explicit finite difference method for the special case where the model is driven by a time-dependent compound Poisson process. The numerical approach gives us both the value of the storage facility and optimal operating strategy depending on the gas price, current level of gas in the storage and time. The effects of seasonality and seasonal jump intensity are investigated by observing the surfaces of control strategies and contract values.

Spatially distributed collective adaptive systems are an important class of systems that pose significant challenges to modeling due to the size and complexity of their state spaces. This problem is acute when the dynamic behavior of the system must be captured, such as to predict system performance. In this article, we present an abstraction technique that automatically derives a moment-closure approximation of the dynamic behavior of a spatially distributed collective adaptive system from a discrete representation of the entities involved. The moment-closure technique is demonstrated to give accurate estimates of dynamic behavior, although the number of ordinary differential equations generated for the second-order joint moments can grow large in some cases. For these cases, we propose a rigorous model reduction technique and demonstrate its use to substantially reduce the computational effort with only limited impact on the accuracy if the reduction threshold is set appropriately. All techniques reported in this article are implemented in a tool that is freely available for download.

Wireless communication protocols are often used in critical applications, e.g., urban water supply networks or healthcare monitoring within the Internet of Things. It is essential that control software and protocols for such systems are verified to be both robust and reliable. The effects on the hardware caused by environmental conditions and the choice of parameters used by the protocol are among the largest obstacles to robustness and reliability in wireless systems. In this paper we use formal verification to verify that a wireless sensor network synchronization and dissemination protocol is not adversely affected by these factors.

For a finite group G , a positive integer λ , and subsets X , Y of G , write λ G = X Y if the products x y ( x ∈ X , y ∈ Y ), cover G precisely λ times. Such a subset Y is called a code with respect to X , and when λ = 1 it is a perfect code in the Cayley graph Cay ( G , X ). In this paper we present various families of examples of such codes, with X closed under conjugation and Y a subgroup, in symmetric groups, and also in special linear groups S L 2 ( q ) . We also propose conjectures about the existence of some much wider families.

In this paper we explore the construction of arbitrarily tight $$\alpha $$ BB relaxations of $$C^2$$ general non-linear non-convex functions. We illustrate the theoretical challenges of building such relaxations by deriving conditions under which it is possible for an $$ \alpha $$ BB underestimator to provide exact bounds. We subsequently propose a methodology to build $$ \alpha $$ BB underestimators which may be arbitrarily tight (i.e., the maximum separation distance between the original function and its underestimator is arbitrarily close to 0) in some domains that do not include the global solution (defined in the text as “sub-optimal”), assuming exact eigenvalue calculations are possible. This is achieved using a transformation of the original function into a $$\mu $$ -subenergy function and the derivation of $$\alpha $$ BB underestimators for the new function. We prove that this transformation results in a number of desirable bounding properties in certain domains. These theoretical results are validated in computational test cases where approximations of the tightest possible $$\mu $$ -subenergy underestimators, derived using sampling, are compared to similarly derived approximations of the tightest possible classical $$\alpha $$ BB underestimators. Our tests show that $$\mu $$ -subenergy underestimators produce much tighter bounds, and succeed in fathoming nodes which are impossible to fathom using classical $$ \alpha $$ BB.

We present two extensions of theLFconstructive type theory featuring monadiclocks. A lock is a monadic type construct that captures the effect of anexternal call to an oracle. Such calls are the basic tool forplugging-inand gluing together, different metalanguages and proof development environments. Oracles can be invoked either to check that a constraint holds or to provide a witness. The systems are presented in thecanonical styledeveloped by the ‘CMU School.’ The first system,CLLF𝒫, is the canonical version of the systemLLF𝒫, presented earlier by the authors. The second system,CLLF𝒫?, features the possibility of invoking the oracle to obtain also a witness satisfying a given constraint. In order to illustrate the advantages of our new frameworks, we show how to encode logical systems featuring rules that deeply constrain the shape of proofs. The locks mechanisms ofCLLF𝒫andCLLF𝒫?permit to factor out naturally the complexities arising from enforcing these ‘side conditions,’ which severely obscure standardLFencodings. We discuss Girard's Elementary Affine Logic, Fitch–Prawitz set theory, call-by-value λ-calculi and functions, both total and even partial.

Structural analysis of molecular pores can yield important information on their behaviour in solution and in the bulk. We developed pywindow, a python package that allows for the automated analysis of structural features of porous molecular materials, such as molecular cages. Our analysis includes the cavity diameter, number of windows, window diameters and average molecular diameter. Molecular dynamics trajectories of can also be analysed to explore the influence of flexibility. We present the methodology, validation and application of pywindow for the analysis of molecular pores, metal-organic polyhedra and some instances of framework materials. pywindow is freely available from github.com/JelfsMaterialsGroup/pywindow.

This paper investigates the connections between many popular variants of the well-established discontinuous Galerkin method and the recently developed high-order flux reconstruction approach on irregular tensor-product grids. We explore these connections by analysing three nodal versions of tensor-product discontinuous Galerkin spectral element approximations and three types of flux reconstruction schemes for solving systems of conservation laws on irregular tensor-product meshes. We demonstrate that the existing connections established on regular grids are also valid on deformed and curved meshes for both linear and nonlinear problems, provided that the metric terms are accounted for appropriately. We also find that the aliasing issues arising from nonlinearities either due to a deformed/curved elements or due to the nonlinearity of the equations are equivalent and can be addressed using the same strategies both in the discontinuous Galerkin method and in the flux reconstruction approach. In particular, we show that the discontinuous Galerkin and the flux reconstruction approach are equivalent also when using higher-order quadrature rules that are commonly employed in the context of over- or consistent-integration-based dealiasing methods. The connections found in this work help to complete the picture regarding the relations between these two numerical approaches and show the possibility of using over- or consistent-integration in an equivalent manner for both the approaches.