Jordan algebra

Gene

Matrix (chemical analysis)

Combinatorics

Physics

Algebra over a field

Linear algebra

Algebra representation

Artificial intelligence

Tensor (intrinsic definition)

Composite material

Gaussian

Tensor algebra

Compiler

Matrix multiplication

Parallel computing

Chemistry

Materials science

Programming language

Pure mathematics

Transformation (genetics)

Geometry

Multiplication (music)

Mathematics

Computer science

Tensor product

Biochemistry

Sparse matrix

Workspace

Quantum mechanics

Theoretical computer science

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