  We address the problem of optimizing mixed sparse and dense tensor algebra in
a compiler. We show that standard loop transformations, such as strip-mining,
tiling, collapsing, parallelization and vectorization, can be applied to
irregular loops over sparse iteration spaces. We also show how these
transformations can be applied to the contiguous value arrays of sparse tensor
data structures, which we call their position space, to unlock load-balanced
tiling and parallelism.
  We have prototyped these concepts in the open-source TACO system, where they
are exposed as a scheduling API similar to the Halide domain-specific language
for dense computations. Using this scheduling API, we show how to optimize
mixed sparse/dense tensor algebra expressions, how to generate load-balanced
code by scheduling sparse tensor algebra in position space, and how to generate
sparse tensor algebra GPU code. Our evaluation shows that our transformations
let us generate good code that is competitive with many hand-optimized
implementations from the literature.
