Compiling imperfectly-nested sparse matrix codes with dependences

Abstract. We present compiler technology for generating sparse matrix code from (i) dense matrix code and (ii) a description of the indexing structure of the sparse matrices. This technology embeds statement instances into a Carte-sian product of statement iteration and data spaces, and produces efcient sparse code by identifying common enumerations for multiple references to sparse ma-trices. This approach works for imperfectly-nested codes with dependences, and produces sparse code competitive with hand-written library code.