  This paper shows how to optimize sparse tensor algebraic expressions by
introducing temporary tensors, called workspaces, into the resulting loop
nests. We develop a new intermediate language for tensor operations called
concrete index notation that extends tensor index notation. Concrete index
notation expresses when and where sub-computations occur and what tensor they
are stored into. We then describe the workspace optimization in this language,
and how to compile it to sparse code by building on prior work in the
literature.
  We demonstrate the importance of the optimization on several important sparse
tensor kernels, including sparse matrix-matrix multiplication (SpMM), sparse
tensor addition (SpAdd), and the matricized tensor times Khatri-Rao product
(MTTKRP) used to factorize tensors. Our results show improvements over prior
work on tensor algebra compilation and brings the performance of these kernels
on par with state-of-the-art hand-optimized implementations. For example, SpMM
was not supported by prior tensor algebra compilers, the performance of MTTKRP
on the nell-2 data set improves by 35%, and MTTKRP can for the first time have
sparse results.
