Nonlinear Spatial Discretization Using Sparse Grids

John Loffeld | 20-FS-018

Project Overview

Many of Lawrence Livermore National Laboratory's mission focus areas are modeled by multidimensional systems that feature sharp gradients and discontinuities. Examples include National Ignition Facility (NIF) magnetic fusion energy kinetic codes, stochastic partial differential equations for uncertainty quantification, and ensemble simulations for machine learning. Such problems are often also plagued by dimensionality, where the combination of high dimensionality and geometric growth of complexity with dimension results in exorbitant computational cost. Sparse grids are a particularly effective approach to address this issue for structured grid-based problems. Through careful error cancellation, achieved by combining solutions resolved along individual dimensions, their computational expense only grows logarithmically in the number of dimensions. However, until now, this approach had not been developed for nonlinear discretization schemes, which are needed to resolve sharp gradients and discontinuities. The challenge is that the error cancellation needed by sparse grids is not upheld by such schemes if applied directly, as the truncation error becomes solution-dependent.

During this feasibility study, we examined approaches for employing the well-known Weighted Essentially Non-Oscillatory (WENO) family of nonlinear discretizations for dealing with discontinuities in a sparse-grids context. We found that a global Lax-Friedrichs type of upwinding maintained sparse grid-error cancellation and obviated the need for central WENO schemes. The technique can also be applied to non-WENO discretizations that require upwinding. We discovered that the interpolation used during grid combination destroys conservation, which is unacceptable for problems based on conservation laws and can result in numerical instability. This issue is currently unaddressed in the sparse grids literature. We determined that satisfying local conservation while interpolating between grids at orders greater than 2 is not possible under general circumstances. However, we devised higher order interpolation strategies that maintain global conservation and appear to resolve instabilities due to lack of conservation. Finally, since error cancellation during combination happens between pairs of grids matched along a dimension, we synchronize WENO weights by taking the worst-case weights over all cells in overlapping regions between the pairs in order to uphold the correct cancellation. We found that convergence under this approach is negatively impacted by the coarsest levels, presumably because cancellation becomes ineffective in the face of particularly large magnitudes for the error terms. Numerical tests show that accuracy can be recovered, at some penalty to cost, by pruning coarse levels in the tree. More investigation into circumventing this effect is needed, or, alternatively, developing algorithms that balance the tradeoff. 

Mission Impact

The work developed here widens the applicability of sparse grids to many high-dimensional problems in high-energy-density (HED) science, as well as high-performance computing, simulation, and data science, which are both Laboratory core competencies. Of particular note are kinetic models used by NIF and in HED physics laser-plasma interactions, as well as simulations of magnetically confined fusion devices.