Randomized quasi-Monte Carlo sampling for scientific computing

这个项目将改进处理科学、工程和商业计算中必须考虑的大量变量的方法。在科学可视化或电脑游戏的图形渲染中，人们必须考虑光形成图像的许多不同路径。在财务预测中，有必要对一种或多种资产价格在未来许多时间步长的未来价格变化进行建模。污染物流动的模型必须考虑到许多地方土壤渗透性的变化。所有这些问题都会产生高维问题，其中维数是必须考虑的潜在变量的数量。标准问题是对所有这些未知数的随机值求一个兴趣量的平均值。相关的问题包括确定哪些未知因素是最重要的。这个项目将开发出更高效的计算方法来解决这些问题。更广泛的影响包括图形、金融和其他科学和工程计算的应用。它们还包括培训博士生解决这些方法，并向其他研究人员展示工作。所研究的具体方法被称为随机准蒙特卡罗（RQMC）抽样。这些方法比我们更熟悉的蒙特卡罗（MC）抽样方法更有效，后者对输入进行随机选择。准蒙特卡罗（QMC）可以做出确定性的、非常平衡的输入选择。对于足够光滑的问题，QMC提高了MC采样的收敛速度。RQMC随机化QMC点以保持其平衡，但允许通过复制进行统计误差估计。对于足够光滑的问题，RQMC提高了QMC的达到率。项目的一部分开发了一个中位数策略来组合独立的RQMC复制。这种方法比通常的均值要准确得多，因为它排除了可以进一步提高收敛速度的异常值。它需要来自解析组合学的新的QMC/RQMC理论输入，包括哈代和拉马努金的著名定理。该项目还包括主动子空间方法，用于降低高维积分的有效维数。活动子空间是在不确定性量化（UQ）文献中发展起来的一种新方法，本项目将与RQMC相结合。UQ方法在工程中变得越来越突出，因为用户需要更好的方法来判断其数值方法的准确性。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.