Efficient and Robust Carath' e odory-Steinitz Pruning of Positive Discrete Measures
math.NA, cs.NA
Submitted: 2025-10-16
Updated: 2026-11-04
Comments: Minor text updates, runtime comparison figure regenerated correcting for scaling constant, inclusion of python API. Fixes of minor technical errors in appendix and supplemental proofs
Code: https://github.com/fbelik/CSPy
License: http://creativecommons.org/licenses/by/4.0/
The gist: In many applications, one seeks to approximate integration against a positive measure of interest by a positive discrete measure: a numerical quadrature rule with positive weights.
Terminology
Abstract
In many applications, one seeks to approximate integration against a positive measure of interest by a positive discrete measure: a numerical quadrature rule with positive weights. One common desired discretization property is moment preservation over a finite dimensional function space, e.g., bounded-degree polynomials. Carathéodory's theorem asserts that if there is any finitely supported quadrature rule with more nodes than the dimension of the given function space, one can form a smaller (and hence more efficient) positive, nested, quadrature rule that preserves the moments of the original rule. We describe an efficient streaming procedure for Carathéodory-Steinitz pruning, a numerical procedure that implements Carathéodory's theorem for this measure compression. The new algorithm makes use of Givens rotations and on-demand storage of arrays to successfully prune very large rules whose storage complexity only depends on the dimension of the function space. This approach improves on a naive implementation of Carathéodory-Steinitz pruning whose runtime and storage complexity are quadratic and linear, respectively, in the size of the original measure. We additionally prove mathematical stability properties of our method with respect to a set of admissible, total-variation perturbations of the original measure. Our method is compared to two alternative approaches with larger storage requirements: non-negative least squares and linear programming, and we demonstrate comparable runtimes, with improved stability and storage robustness. Finally, we demonstrate practical usage of this algorithm to generate quadrature for discontinuous Galerkin finite element simulations on cut-cell meshes.
Sources
- Constructing Positive Interpolatory Cubature Formulas
- Entropy stable reduced order modeling of nonlinear conservation laws using discontinuous Galerkin methods
- Beyond Tchakaloff Quadrature: Positive Functionals, Frames and Widths
- Caratheodory-Tchakaloff Subsampling
- An Entropy Stable High-Order Discontinuous Galerkin Method on Cut Meshes
Related papers
- Do physics-informed neural networks (PINNs) need to be deep? Shallow PINNs using the Levenberg-Marquardt algorithm
- A Neural-preconditioned Poisson Solver for Mixed Dirichlet and Neumann Boundary Conditions
- Advanced Linear Algebra with Applications - Part I (Numerical linear algebra for PDEs, machine learning, and data assimilation)
- Operator learning meets inverse problems: A probabilistic perspective
- Second-order consistency for learning chaotic dynamics via randomized Jacobian matching
- Windowed thinning and query complexity for the bouncy particle and Zigzag samplers