Performance of Unidirectional Hierarchization for Component Grids Virtually Maximized

AbstractThe sparse grid combination technique provides a framework to solve high-dimensional numerical problems with standard solvers. To combine the component grid solutions of the combination technique either interpolation and sampling or a change of basis from the full grid basis to the hierarchical basis is required. We implement a memory efficient hierarchization algorithm for the component grids of the sparse grid combination technique performing this change of basis. By exploiting the structure of the component grids, this implementation comes within a factor of 1.5 of the runtime achievable for large grids by any hierarchization algorithm implementing the unidirectional principle. The implementation outperforms the currently fastest generic software StructuredSG [2] by a factor between 5.8x and 41x for problems larger than 30MiB