Algorithmic problems about geometric spaces are ubiquitous in many fields of science and engineering. For example, in data analysis, a central task is to extract important features of data, a high-dimensional point set in many cases. The extraction of the significant features then leads to applications such as visualizing the data or clustering the data in a meaningful way. Another example is in scientific computing where modeling the behavior of a physical phenomenon such as heat, sound or electricity within a geometric space is a central problem. These problems can be specified by partial differential equations (PDEs), for which efficient solvers are necessary. Many of these geometric problems can be cast as problems in linear algebra: computational problems on Laplace-de Rham operators, a sequence of matrices that succinctly present geometric spaces. Thus, faster and simpler methods can be developed for these problems using powerful tools from linear algebra, which is the focus of this project.
Recent advances in the study of graph Laplacians (the first matrix in the Laplace-de Rham sequence) have resulted in a series of simple and elegant algorithms that helped important applications in computer science and data analysis. In contrast, higher dimensional variants of Laplace-de Rham operators, in spite of their key roles in science and engineering (e.g. in solving physical equations, in performing Helmholtz/Hodge decomposition for applications in data visualization and statistical ranking, or in revealing effective geometric or topological properties of a hidden space) have remained largely under-explored. This project will fill this gap by addressing important open problems about Laplace-de Rham operators for two different types of applications under two high-level aims: (1) design efficient solvers for Laplace-de Rham matrices that appear in important problems raised from partial differential equations (PDEs), e.g. vector Laplacians in Navier-Stokes or Maxwell equations, in scientific computing, and (2) discover and harness effective properties of Laplace-de Rham matrices and their spectra for data analysis.
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
