Parallel Adaptive Interpolation Algorithm based on Sparse Grids for Modeling Dynamic Systems with Interval Parameters
Parallel Adaptive Interpolation Algorithm based on Sparse Grids for Modeling Dynamic Systems with Interval Parameters
复制标题
基于稀疏网格的区间参数动态系统并行自适应插值算法
DOI：
10.17587/prin.12.395-403
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
A. Morozov
中科院分区：
文献类型：
--
作者：
A. Morozov
针对区间参数动态系统建模问题，提出了一种基于稀疏网格的自适应插值并行算法。该算法的思想是构造一个分段多项式函数，该函数将问题的解与区间参数的点值的依赖关系内插。该算法的经典版本在完整网格上使用多项式插值，由于存在大量的不确定性，计算成本呈指数增长，使得该算法难以应用。使用稀疏网格可以显著降低计算成本，但在一般情况下，算法的复杂度与区间参数的数量保持指数关系。在这方面，加速算法的问题是相关的。该算法可分为几组独立的子任务：更新网格节点对应的值；加权因子的计算；在新节点上插值值。最后两个集合意味着递归的并行化，因此这里主要使用遍历调用图宽度的技术。在两个分别包含2个和6个区间参数的ODE系统上，使用不同数量的计算核，对该算法的并行实现进行了测试。所得结果证明了所采用方法的有效性。
The paper presents a parallel algorithm for adaptive interpolation based on sparse grids for modeling dynamic systems with interval parameters. The idea of the algorithm is to construct a piecewise polynomial function that interpolates the dependence of the solution to the problem on the point values of the interval parameters. In the classical version of the algorithm, polynomial interpolation on complete grids is used, and with a large number of uncertainties, the algorithm becomes difficult to apply due to the exponential growth of computational costs. The use of sparse grids can significantly reduce the computational costs, but nevertheless the complexity of the algorithm in the general case remains exponential with respect to the number of interval parameters. In this regard, the issue of accelerating the algorithm is relevant. The algorithm can be divided into several sets of independent subtasks: updating the values corresponding to the grid nodes; calculation of weighting factors; interpolation of values at new nodes. The last two sets imply parallelization of recursion, so here the techniques for traversing the width of the call graph are mainly used. The parallel implementation of the algorithm was tested on two ODE systems containing two and six interval parameters, respectively, using a different number of computing cores. The results obtained demonstrate the effectiveness of the approaches used.