Efficient strategy for adaptive partition of N-dimensional intervals in the framework of diagonal algorithms

In this paper, the problem of the minimal description of the structure of functional f(x) over an N-dimensional interval is considered. The description is obtained by applying diagonal algorithms, i.e., procedures sequentially partitioning the given hyperinterval and evaluating f(x) at the vertices corresponding to the main diagonal of each generated subinterval. Two partition strategies traditionally used for solving this problem are analyzed and it is demonstrated that using them can result in a high number of redundant evaluations of the functional f(x) A new efficient partition strategy is proposed; it reduces considerably the number of evaluations of f(x) and the memory complexity.