QMCPy: A Python package for randomized low-discrepancy sequences, quasi-Monte Carlo, and fast kernel methods
For computational scientists and engineers, QMCPy provides a practical, reproducible platform for high-dimensional integration and kernel methods, but it is an incremental software contribution rather than a novel algorithm.
QMCPy is an open-source Python library unifying randomized low-discrepancy sequences, quasi-Monte Carlo methods, and fast kernel computations, achieving O(n log n) complexity for matrix operations via FFTs and FWHTs. Numerical experiments demonstrate accuracy and efficiency across test integrands and dimensions.
Low-discrepancy (LD) sequences are widely used as efficient experimental designs for high-dimensional numerical integration and function approximation. This article presents QMCPy, an open-source Python library that provides a unified framework for randomized LD sequences, quasi-Monte Carlo (QMC) methods, and fast kernel-based computations. We systematically describe the supported rank-$1$ lattices, digital nets (including higher-order constructions), and Halton point sets, together with randomization techniques such as random shifts, linear matrix scrambling (LMS), nested uniform scrambling (NUS), digital shifts, and digital permutations. We emphasize practical implementation issues such as extensible sequence generation, Gray code ordering, and efficient digital operations. Beyond integration, QMCPy supports fast kernel methods in reproducing kernel Hilbert spaces (RKHSs) by pairing LD point sets with shift-invariant (SI) and digitally shift-invariant (DSI) kernels, including higher-order variants, which yields structured Gram matrices. In particular, the resulting Gram matrices have circulant or recursive symmetric block Toeplitz (RSBT) structure, allowing the costs of matrix-vector products and linear solves to be reduced from $\mathcal{O}(n^2)- \mathcal{O}(n^3)$ to $\mathcal{O}(n \log n)$ by using fast Fourier transforms (FFTs) and fast Walsh-Hadamard transforms (FWHTs). We derive a new computable form of an order-$4$ DSI kernel, develop efficient eigenvalue and transform-update algorithms, and present numerical experiments that demonstrate the accuracy, convergence rates, and computational efficiency of the implemented methods across a range of test integrands and dimensions. These capabilities in QMCPy provide a practical, reproducible platform for applying randomized QMC and kernel-based techniques in computational science and engineering.