Randomized quasi-Monte Carlo sampling for scientific computing

Stanford University, Stanford CA

Investigators

Abstract

This project will improve methods of handling enormous numbers of variables that one must account for in scientific, engineering and commercial computation. In graphical rendering for scientific visualization or for computer games one has to account for many different paths that light could take to form an image. In financial forecasting it is necessary to model future prices changes of one or more asset prices over many future time steps. Models for the flow of pollutants must account for varying permeability of soil in many places. All of these problems yield high dimensional problems where the dimension is the number of underlying variables that have to be accounted for. The standard problem is to average a quantity of interest with respect to random values of all those unknowns. Related problems involve identifying which of those unknowns is most important. This project will develop more computationally efficient ways to solve these problems. The broader impacts include uses in graphics, finance and other scientific and engineering computations. They also include training of doctoral students to solve these methods and presentation of the work to other researchers. The specific methods under study are known as randomized quasi-Monte Carlo (RQMC) sampling. These methods are much more efficient than the more familiar Monte Carlo (MC) sampling which makes random choices of the inputs. Quasi-Monte Carlo (QMC) makes deterministic and very balanced input choices. For smooth enough problems QMC improves the convergence rate of MC sampling. RQMC randomizes the QMC points to retain their balance but allow statistical error estimates by replication. For smooth enough problems RQMC improves the rate attained by QMC. One part of the project develops a median of means strategy to combine independent RQMC replicates. This method is much more accurate than the usual mean of means because it excludes outliers which can then provide yet more improvements in the convergence rate. It requires new theoretical inputs to QMC/RQMC coming from analytic combinatorics including a famous theorem of Hardy and Ramanujan. The project also includes active subspace methods for reducing the effective dimension of high dimensional integrands. Active subspaces are a newly evolving method from the uncertainty quantification (UQ) literature that this project will merge with RQMC. UQ methods are becoming more prominent in engineering where users want better ways to judge the accuracy of their numerical methods. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.