论文标题
高维数值集成的快速多级维度迭代算法
A fast multilevel dimension iteration algorithm for high dimensional numerical integration
论文作者
论文摘要
在本文中，我们建议并研究用于计算基于张量产品近似值的任意$ d $维积分的快速多级维度迭代（MDI）算法。它从指数顺序$ o（n^d）$降低了张量产品方法的计算复杂性（根据CPU时间）降低到多项式订单{\ color {black color {black} $ o（d^3n^2）$} $（d^3n^2）$}，其中$ n $ n $位于每个坐标方向上的二次点数。结果，所提出的MDI算法有效地避免了张量乘积方法对高维数值整合的尺寸的诅咒。所提出的MDI算法的主要思想是在群集中的所有集成点和沿每个坐标方向迭代中计算功能评估，因此在每次迭代中都可以重复使用用于功能评估的大量计算。这个想法也适用于任何正交规则的集成点具有类似晶格的结构。
In this paper, we propose and study a fast multilevel dimension iteration (MDI) algorithm for computing arbitrary $d$-dimensional integrals based on tensor product approximations. It reduces the computational complexity (in terms of the CPU time) of a tensor product method from the exponential order $O(N^d)$ to the polynomial order {\color{black} $O(d^3N^2)$ or better}, where $N$ stands for the number of quadrature points in each coordinate direction. As a result, the proposed MDI algorithm effectively circumvents the curse of the dimensionality of tensor product methods for high dimensional numerical integration. The main idea of the proposed MDI algorithm is to compute the function evaluations at all integration points in the cluster and iteratively along each coordinate direction, so lots of computations for function evaluations can be reused in each iteration. This idea is also applicable to any quadrature rule whose integration points have a lattice-like structure.
