Domain decomposition methods are a set of widely used tools for parallelization of partial differential equation solvers. Convergence is well studied for elliptic equations, but in the case of parabolic equations there are hardly any results for general Lipschitz domains in two or more dimensions. The aim of this work is therefore to construct a new framework for analyzing nonoverlapping domain decomposition methods for the heat equation in a space-time Lipschitz cylinder. The framework is based on a variational formulation, inspired by recent studies of space-time finite elements using Sobolev spaces with fractional time regularity. In this framework, the time-dependent Steklov--Poincar\'e operators are introduced and their essential properties are proven. We then derive the interface interpretations of the Dirichlet--Neumann, Neumann--Neumann and Robin--Robin methods and show that these methods are well defined. Finally, we prove convergence of the Robin--Robin method and introduce a modified method with stronger convergence properties.
We propose and analyze a space-time virtual element method for the discretization of the heat equation in a space-time cylinder, based on a standard Petrov-Galerkin formulation. Local discrete functions are solutions to a heat equation problem with polynomial data. Global virtual element spaces are nonconforming in space, so that the analysis and the design of the method are independent of the spatial dimension. The information between time slabs is transmitted by means of upwind terms involving polynomial projections of the discrete functions. We prove well posedness and optimal error estimates for the scheme, and validate them with several numerical tests.
Construction of error-correcting codes achieving a designated minimum distance parameter is a central problem in coding theory. In this work, we study a very simple construction of binary linear codes that correct a given number of errors $K$. Moreover, we design a simple, nearly optimal syndrome decoder for the code as well. The running time of the decoder is only logarithmic in the block length of the code, and nearly linear in the number of errors $K$. This decoder can be applied to exact for-all sparse recovery over any field, improving upon previous results with the same number of measurements. Furthermore, computation of the syndrome from a received word can be done in nearly linear time in the block length. We also demonstrate an application of these techniques in non-adaptive group testing, and construct simple explicit measurement schemes with $O(K^2 \log^2 N)$ tests and $O(K^3 \log^2 N)$ recovery time for identifying up to $K$ defectives in a population of size $N$.
In this paper, we present a new and effective simulation-based approach to conduct both finite- and large-sample inference for high-dimensional linear regression models. This approach is developed under the so-called repro samples framework, in which we conduct statistical inference by creating and studying the behavior of artificial samples that are obtained by mimicking the sampling mechanism of the data. We obtain confidence sets for (a) the true model corresponding to the nonzero coefficients, (b) a single or any collection of regression coefficients, and (c) both the model and regression coefficients jointly. We also extend our approaches to drawing inferences on functions of the regression coefficients. The proposed approach fills in two major gaps in the high-dimensional regression literature: (1) lack of effective approaches to address model selection uncertainty and provide valid inference for the underlying true model; (2) lack of effective inference approaches that guarantee finite-sample performances. We provide both finite-sample and asymptotic results to theoretically guarantee the performances of the proposed methods. In addition, our numerical results demonstrate that the proposed methods are valid and achieve better coverage with smaller confidence sets than the existing state-of-art approaches, such as debiasing and bootstrap approaches.
It is well-known that the Fourier-Galerkin spectral method has been a popular approach for the numerical approximation of the deterministic Boltzmann equation with spectral accuracy rigorously proved. In this paper, we will show that such a spectral convergence of the Fourier-Galerkin spectral method also holds for the Boltzmann equation with uncertainties arising from both collision kernel and initial condition. Our proof is based on newly-established spaces and norms that are carefully designed and take the velocity variable and random variables with their high regularities into account altogether. For future studies, this theoretical result will provide a solid foundation for further showing the convergence of the full-discretized system where both the velocity and random variables are discretized simultaneously.
This paper presents the first systematic study on the fundamental problem of seeking optimal cell average decomposition (OCAD), which arises from constructing efficient high-order bound-preserving (BP) numerical methods within Zhang--Shu framework. Since proposed in 2010, Zhang--Shu framework has attracted extensive attention and been applied to developing many high-order BP discontinuous Galerkin and finite volume schemes for various hyperbolic equations. An essential ingredient in the framework is the decomposition of the cell averages of the numerical solution into a convex combination of the solution values at certain quadrature points. The classic CAD originally proposed by Zhang and Shu has been widely used in the past decade. However, the feasible CADs are not unique, and different CAD would affect the theoretical BP CFL condition and thus the computational costs. Zhang and Shu only checked, for the 1D $\mathbb P^2$ and $\mathbb P^3$ spaces, that their classic CAD based on the Gauss--Lobatto quadrature is optimal in the sense of achieving the mildest BP CFL conditions. In this paper, we establish the general theory for studying the OCAD problem on Cartesian meshes in 1D and 2D. We rigorously prove that the classic CAD is optimal for general 1D $\mathbb P^k$ spaces and general 2D $\mathbb Q^k$ spaces of arbitrary $k$. For the widely used 2D $\mathbb P^k$ spaces, the classic CAD is not optimal, and we establish the general approach to find out the genuine OCAD and propose a more practical quasi-optimal CAD, both of which provide much milder BP CFL conditions than the classic CAD. As a result, our OCAD and quasi-optimal CAD notably improve the efficiency of high-order BP schemes for a large class of hyperbolic or convection-dominated equations, at little cost of only a slight and local modification to the implementation code.
Polynomials are common algebraic structures, which are often used to approximate functions including probability distributions. This paper proposes to directly define polynomial distributions in order to describe stochastic properties of systems rather than to assume polynomials for only approximating known or empirically estimated distributions. Polynomial distributions offer a great modeling flexibility, and often, also mathematical tractability. However, unlike canonical distributions, polynomial functions may have non-negative values in the interval of support for some parameter values, the number of their parameters is usually much larger than for canonical distributions, and the interval of support must be finite. In particular, polynomial distributions are defined here assuming three forms of polynomial function. The transformation of polynomial distributions and fitting a histogram to a polynomial distribution are considered. The key properties of polynomial distributions are derived in closed-form. A piecewise polynomial distribution construction is devised to ensure that it is non-negative over the support interval. Finally, the problems of estimating parameters of polynomial distributions and generating polynomially distributed samples are also studied.
Electricity prices in liberalized markets are determined by the supply and demand for electric power, which are in turn driven by various external influences that vary strongly in time. In perfect competition, the merit order principle describes that dispatchable power plants enter the market in the order of their marginal costs to meet the residual load, i.e. the difference of load and renewable generation. Many market models implement this principle to predict electricity prices but typically require certain assumptions and simplifications. In this article, we present an explainable machine learning model for the prices on the German day-ahead market, which substantially outperforms a benchmark model based on the merit order principle. Our model is designed for the ex-post analysis of prices and thus builds on various external features. Using Shapley Additive exPlanation (SHAP) values, we can disentangle the role of the different features and quantify their importance from empiric data. Load, wind and solar generation are most important, as expected, but wind power appears to affect prices stronger than solar power does. Fuel prices also rank highly and show nontrivial dependencies, including strong interactions with other features revealed by a SHAP interaction analysis. Large generation ramps are correlated with high prices, again with strong feature interactions, due to the limited flexibility of nuclear and lignite plants. Our results further contribute to model development by providing quantitative insights directly from data.
The goal of the group testing problem is to identify a set of defective items within a larger set of items, using suitably-designed tests whose outcomes indicate whether any defective item is present. In this paper, we study how the number of tests can be significantly decreased by leveraging the structural dependencies between the items, i.e., by incorporating prior information. To do so, we pursue two different perspectives: (i) As a generalization of the uniform combinatorial prior, we consider the case that the defective set is uniform over a \emph{subset} of all possible sets of a given size, and study how this impacts the information-theoretic limits on the number of tests for approximate recovery; (ii) As a generalization of the i.i.d.~prior, we introduce a new class of priors based on the Ising model, where the associated graph represents interactions between items. We show that this naturally leads to an Integer Quadratic Program decoder, which can be converted to an Integer Linear Program and/or relaxed to a non-integer variant for improved computational complexity, while maintaining strong empirical recovery performance.
Charge dynamics play essential role in many practical applications such as semiconductors, electrochemical devices and transmembrane ion channels. A Maxwell-Amp\`{e}re Nernst-Planck (MANP) model that describes charge dynamics via concentrations and the electric displacement is able to take effects beyond mean-field approximations into account. To obtain physically faithful numerical solutions, we develop a structure-preserving numerical method for the MANP model whose solution has several physical properties of importance. By the Slotboom transform with entropic-mean approximations, a positivity preserving scheme with Scharfetter-Gummel fluxes is derived for the generalized Nernst-Planck equations. To deal with the curl-free constraint, the dielectric displacement from the Maxwell-Amp\`{e}re equation is further updated with a local relaxation algorithm of linear computational complexity. We prove that the proposed numerical method unconditionally preserves the mass conservation and the solution positivity at the discrete level, and satisfies the discrete energy dissipation law with a time-step restriction. Numerical experiments verify that our numerical method has expected accuracy and structure-preserving properties. Applications to ion transport with large convection, arising from boundary-layer electric field and Born solvation interactions, further demonstrate that the MANP formulation with the proposed numerical scheme has attractive performance and can effectively describe charge dynamics with large convection of high numerical cell P\'{e}clet numbers.
In geostatistical problems with massive sample size, Gaussian processes (GP) can be approximated using sparse directed acyclic graphs to achieve scalable $O(n)$ computational complexity. In these models, data at each location are typically assumed conditionally dependent on a small set of parents which usually include a subset of the nearest neighbors. These methodologies often exhibit excellent empirical performance, but the lack of theoretical validation leads to unclear guidance in specifying the underlying graphical model and may result in sensitivity to graph choice. We address these issues by introducing radial neighbors Gaussian processes and corresponding theoretical guarantees. We propose to approximate GPs using a sparse directed acyclic graph in which a directed edge connects every location to all of its neighbors within a predetermined radius. Using our novel construction, we show that one can accurately approximate a Gaussian process in Wasserstein-2 distance, with an error rate determined by the approximation radius, the spatial covariance function, and the spatial dispersion of samples. Our method is also insensitive to specific graphical model choice. We offer further empirical validation of our approach via applications on simulated and real world data showing state-of-the-art performance in posterior inference of spatial random effects.