DOI: 10.17587/prin.12.395-403

Parallel Adaptive Interpolation Algorithm based on Sparse Grids for Modeling Dynamic Systems with Interval Parameters

A. Yu. Morozov, morozov@infway.ru, Federal Research Center Computer Science and Control of Russian Academy of Sciences, Moscow, Moscow Aviation Institute

Corresponding author: Morozov Alexander Yu., Researcher¹, Senior Lecturer²,
¹Federal Research Center "Computer Science and Control" of Russian Academy of Sciences, Moscow,
²Moscow Aviation Institute, E-mail: morozov@infway.ru

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.

Keywords: parallelization, OpenMP, adaptive interpolation algorithm, adaptive sparse grids, multidimensional interpolation, interval systems of ordinary differential equations, large dimensions

pp. 395–403

For citation:
Morozov A. Yu. Parallel Adaptive Interpolation Algorithm based on Sparse Grids for Modeling Dynamic Systems with Interval Parameters, Programmnaya Ingeneria, 2021, vol. 12, no. 8, pp. 395—403.