Compiling and Compressing Structured Tensors
summary
Two systems compile symbolic sparsity into executable code: an earlier DSL-driven compiler called Struct that infers structure inference (diagonals, symmetry, covariance patterns) and a 2025 follow-up that adds polyhedral indexing to pack only needed elements into a continuous compressed buffer. Results show orders-of-magnitude complexity reductions and up to ~5× extra speed over the iteration-only code, plus parallel loop generation; storage, cache locality and vectorization improve because only indexed elements are stored and iterated.
AI-written summary · about
chapters (10)
- 0:00Introduction
- 1:43Combining dense and sparse benefits
- 2:46Sparsity structure encoding
- 6:03Storage and locality challenges
- 7:28Polyhedral analysis for indexing
- 10:27Limitations of DSL approach
- 12:18Generalizing structured computation
- 13:45Recovering tensor structure
- 14:26Interoperability with sparse layouts
- 14:49Future work and hardware
related talks
20mCompiling Structured Tensor Algebra
14mCompressed and Parallelized Structured Tensor Algebra
32mCompilation of Dynamic Sparse Tensor Algebra
28mFunctional Sparse Tensor Compilation
19mCompiler Support for Sparse Tensor Convolutions
15mCompilation of Sparse Array Programming Models
20mVectorizing Sparse Coiteration for Two-finger Loop Structure (Extended Abstract)
32mhow compiler smarts can help improve the performance of numerical methods