PolytopeWalk: Sparse MCMC Sampling over Polytopes
Benny Sun, Yuansi Chen Β· The Journal of Open Source Software Β· 2025
High dimensional sampling is an important computational tool in statistics, with applications in stochastic simulation, volume computation, and fast randomized algorithms.We present PolytopeWalk, a scalable library designed for sampling from a uniform distribution over polytopes, which are bounded geometric objects formed by linear inequalities.For sampling, we use Markov chain Monte Carlo (MCMC) methods, defined as a family of algorithms for generating approximate samples from a target probability distribution.Six state-of-the-art MCMC algorithms are implemented, including the Dikin, Vaidya, and John Walk.Additionally, we introduce novel sparse constrained formulations of these algorithms, enabling efficient sampling from sparse polytopes of the form π¦ 2 = {π₯ β β π | π΄π₯ = π, π₯ βͺ° π 0}.This implementation maintains sparsity in π΄, ensuring scalability to higher dimensional settings in per-iteration cost.Finally, PolytopeWalk includes implementations of 2 preprocessing algorithms, facial reduction and initialization, thus providing an end-to-end solution.