CAREER: Next-Generation Infrastructure for Tensor Computations

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

Matrices and their higher-order generalization (tensors) provide a mathematical toolbox for expressing a large variety of algorithms. Consequently, linear algebra operations on dense matrices have served as the backbone of high-performance scientific computing applications. This research aims to translate this benefit to more complex problems, by improving software infrastructure and parallel performance of sparse matrix and tensor operations. The proposed methods will be applied to accelerate analysis of large graphs, approximation of multidimensional datasets by tensor decompositions, and simulation of quantum systems. By providing a high-level library for distributed sparse tensors, the research will improve the development productivity of scientists and engineers from disciplines including chemistry, physics, and bioinformatics. Deployment of tensor-based techniques on massively-parallel computing systems will enable simulations of larger scale and higher accuracy, making new innovations in computational science possible. Additionally, development of web-based educational modules for programming with tensors and understanding parallel performance will make the software and methods accessible to the broader scientific community. Tensor decompositions and tensor networks are fundamental techniques in approximation of multi-dimensional data and functions. The frontiers of tensor computations in quantum chemistry and data analysis involve methods that contract tensors of different order, size, and sparsity. Recent developments have led to provably efficient algorithms and software for contraction of a pair of dense tensors and multiplication of a pair of sparse matrices. However, in the context of sparse multi-tensor operations, opportunities for asymptotic cost improvements remain. In particular, there is a lack of software and rigorous algorithmic analysis for sparse matrix and tensor computations involving hyper-sparsity and output sparsity, as well as for all-at-once contraction of multiple tensors, which can be advantageous in the presence of sparsity. Further, at the software library level, open problems remain in leveraging layout persistence, reuse of mapping logic, and automated performance modeling. The project will address these gaps in the state-of-the-art of available computational infrastructure by developing new parallel algorithms and systems techniques for sparse multi-tensor contraction. These innovations will be integrated into the Cyclops library and studied in the context of applications in graph analysis, tensor decomposition, and tensor networks. 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.