Public Abstract

DE-SC0022266: Leverage Score Sampling for Parametric PDEs

Award Status: Inactive

Institution: New York University, New York, NY
UEI: NX9PXMKW5KW8
DUNS: 041968306

Most Recent Award Date: 07/21/2022
Number of Support Periods: 2
PM: Lee, Steven

Current Budget Period: 09/01/2022 - 08/31/2023
Current Project Period: 09/01/2021 - 08/31/2023
PI: Musco, Christopher

Supplement Budget Period: N/A

Public Abstract

This project proposes a new class of randomized techniques for efficiently solving large-scale, parametric partial differential equations (PDEs), which underlie some of the most important computational problems in DOE-relevant applications. A common requirement is to approximate the entire solution space of a PDE as parameters of the underlying physical system change, which can happen for a variety of reasons. In Uncertainty Quantification (UQ), parameters are random quantities; in Model-driven Design, parameters are sequentially modified to optimize some objective; and in Data Assimilation, parameters are tuned to fit a PDE solution to measured data. The key to reducing enormous computational complexity in all of these applications is to avoid the cost of completely re-solving the PDE for different parameters by taking advantage of redundancy between solutions. This project will develop novel methods for exploiting redundancy by extending powerful importance sampling methods from Randomized Numerical Linear Algebra (RandNLA) to PDEs. Concretely, the research is centered around a matrix sampling technique known as leverage score sampling. This project will generalize leverage scores to be used as importance sampling probabilities for learning multidimensional scalar functions, a primitive which can then be applied to solving parametric PDEs, either through reduced order modeling or Quantity-of-Interest approximation. The project has three primary objectives, which will involve the development of new algorithms and software, as well as new theoretical tools and analysis: (1) New models: The project will develop methods for applying and theoretically analyzing leverage score sampling for important classes of high-dimensional function, including sparse Fourier functions and neural networks, which have high potential for modeling parametric PDEs. (2) Variance reduction: The project will design novel pseudo- and quasi-random variants of leverage score sampling that reduce variance during function fitting, and will be critical in improving the practical effectiveness of leverage-based methods. (3) Distribution adaptivity: The project will study specialized leverage score methods for UQ problems where parameters follow non-uniform probability distributions. The end result of this project will be a family of new algorithms that can accurately approximate the entire solution space of a parametric PDE, after having only incurred the computational cost of solving that PDE for a small set of training parameters. The algorithms developed have the potential to offer orders-of-magnitude reduction in computational cost over existing techniques like naive Monte Carlo methods and deterministic sample collection. The project will also help build connections between different research areas, bridging the wide gap between numerical methods and fields like machine learning and theoretical computer science. By doing so, the project will help pave the way for future work on randomized methods in computational science, and more generally help to broaden the algorithmic toolkit available for solving the field’s most important problems.

This project proposes a new class of randomized techniques for efficiently solving large-scale, parametric partial differential equations (PDEs), which underlie some of the most important computational problems in DOE-relevant applications. A common requirement is to approximate the entire solution space of a PDE as parameters of the underlying physical system change, which can happen for a variety of reasons. In Uncertainty Quantification (UQ), parameters are random quantities; in Model-driven Design, parameters are sequentially modified to optimize some objective; and in Data Assimilation, parameters are tuned to fit a PDE solution to measured data.

The key to reducing enormous computational complexity in all of these applications is to avoid the cost of completely re-solving the PDE for different parameters by taking advantage of redundancy between solutions. This project will develop novel methods for exploiting redundancy by extending powerful importance sampling methods from Randomized Numerical Linear Algebra (RandNLA) to PDEs. Concretely, the research is centered around a matrix sampling technique known as leverage score sampling. This project will generalize leverage scores to be used as importance sampling probabilities for learning multidimensional scalar functions, a primitive which can then be applied to solving parametric PDEs, either through reduced order modeling or Quantity-of-Interest approximation.

The project has three primary objectives, which will involve the development of new algorithms and software, as well as new theoretical tools and analysis: (1) New models: The project will develop methods for applying and theoretically analyzing leverage score sampling for important classes of high-dimensional function, including sparse Fourier functions and neural networks, which have high potential for modeling parametric PDEs. (2) Variance reduction: The project will design novel pseudo- and quasi-random variants of leverage score sampling that reduce variance during function fitting, and will be critical in improving the practical effectiveness of leverage-based methods. (3) Distribution adaptivity: The project will study specialized leverage score methods for UQ problems where parameters follow non-uniform probability distributions.

The end result of this project will be a family of new algorithms that can accurately approximate the entire solution space of a parametric PDE, after having only incurred the computational cost of solving that PDE for a small set of training parameters. The algorithms developed have the potential to offer orders-of-magnitude reduction in computational cost over existing techniques like naive Monte Carlo methods and deterministic sample collection. The project will also help build connections between different research areas, bridging the wide gap between numerical methods and fields like machine learning and theoretical computer science. By doing so, the project will help pave the way for future work on randomized methods in computational science, and more generally help to broaden the algorithmic toolkit available for solving the field’s most important problems.