论文标题
高维数值集成的高效且快速的稀疏网格算法
An efficient and fast sparse grid algorithm for high-dimensional numerical integration
论文作者
论文摘要
本文关注的是开发一种有效的数值算法，用于快速实现稀疏网格方法，以计算给定函数的$ d $维数积分。新算法，称为MDI-SG（{\ em多级维度迭代稀疏网格}）方法，实现基于尺寸迭代/还原过程的稀疏网格方法，它不需要存储集成点，不需要在每个集成点上独立地评估函数的函数函数，就不能在函数上进行函数的函数，从而可以在函数上进行评估，从而可以在函数上进行评估。群集，沿坐标方向迭代。从数值上看，与指数级稀疏网格方法的指数顺序$ o（n（\ log n）^{d-1} $相比，提出的MDI-SG方法的计算复杂性（在CPU时间）是多项式订单$ O（ND^3）$或更高的，对于标准稀疏网格方法，其中$ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $。结果，所提出的MDI-SG方法有效地规避了由标准的稀疏网格方法遭受的高维数值整合的诅咒。
This paper is concerned with developing an efficient numerical algorithm for fast implementation of the sparse grid method for computing the $d$-dimensional integral of a given function. The new algorithm, called the MDI-SG ({\em multilevel dimension iteration sparse grid}) method, implements the sparse grid method based on a dimension iteration/reduction procedure, it does not need to store the integration points, neither does it compute the function values independently at each integration point, instead, it re-uses the computation for function evaluations as much as possible by performing the function evaluations at all integration points in a cluster and iteratively along coordinate directions. It is shown numerically that the computational complexity (in terms of CPU time) of the proposed MDI-SG method is of polynomial order $O(Nd^3 )$ or better, compared to the exponential order $O(N(\log N)^{d-1})$ for the standard sparse grid method, where $N$ denotes the maximum number of integration points in each coordinate direction. As a result, the proposed MDI-SG method effectively circumvents the curse of dimensionality suffered by the standard sparse grid method for high-dimensional numerical integration.
