  Automated code generation and performance optimizations for sparse tensor
algebra are cardinal since they have become essential in many real-world
applications like quantum computing, physics, chemistry, and machine learning.
General sparse tensor algebra compilers are not always versatile enough to
generate asymptotically optimal code for sparse tensor contractions. This paper
shows how to optimize and generate asymptotically better schedules for complex
tensor expressions using kernel fission and fusion. We present a generalized
loop transformation to achieve loop nesting for minimized memory footprint and
reduced asymptotic complexity.
  Furthermore, we present an auto-scheduler that uses a partially ordered
set-based cost model that uses both time and auxiliary memory complexities in
its pruning stages. In addition, we highlight the use of SMT solvers in sparse
auto-schedulers to prune the Pareto frontier of schedules to the smallest
number of possible schedules with user-defined constraints available at compile
time. Finally, we show that our auto-scheduler can select asymptotically better
schedules that use our compiler transformation to generate optimized code. Our
results show that the auto-scheduler achieves orders of magnitude speedup
compared to the TACO-generated code for several real-world tensor algebra
computations on different real-world inputs.
