Combinatorics

Physics

Tensor (intrinsic definition)

Pure mathematics

Multiplication (music)

Mathematics

Workspace

Gene

Jordan algebra

Matrix (chemical analysis)

Algebra over a field

Gaussian

Linear algebra

Tensor algebra

Compiler

Algebra representation

Matrix multiplication

Parallel computing

Artificial intelligence

Composite material

Chemistry

Materials science

Programming language

Transformation (genetics)

Geometry

Computer science

Tensor product

Sparse matrix

Quantum mechanics

Theoretical computer science

Biochemistry

Quantum

Robot

This paper shows how to extend sparse tensor algebra compilers to introduce temporary tensors called workspaces to avoid inefficient sparse data structures accesses. We develop an intermediate representation (IR) for tensor operations called concrete index notation that specifies when sub-computations occur and where they are stored. We then describe the workspace transformation in this IR, how to programmatically invoke it, and how the IR is compiled to sparse code. Finally, we show how the transformation can be used to optimize sparse tensor kernels, including sparse matrix multiplication, sparse tensor addition, and the matricized tensor times Khatri-Rao product (MTTKRP). Our results show that the workspace transformation brings the performance of these kernels on par with hand-optimized implementations. For example, we improve the performance of MTTKRP with dense output by up to 35%, and enable generating sparse matrix multiplication and MTTKRP with sparse output, neither of which were supported by prior tensor algebra compilers.

Tensor Algebra Compilation with Workspaces