The automatic generation of sparse primitives

Reviewer: Jesse Louis Barlow

There is nothing simple about sparse matrix programming. Efficient direct factorization schemes require elimination trees and sophisticated indexing structures, and there are a variety of storage structures. Worse, they are often implemented in Fortran 77, meaning that everything is done with arrays. That makes it quite difficult to do it yourself. The sparse compiler proposed in this paper could be quite a step forward. The user writes a dense matrix code and the compiler makes it into a sparse matrix code in the user's favorite sparse matrix format. Straightforward Fortran declaration structures are used to set up the arrays. The computational results given here are impressive. First, the compiler does a nice job of translating the BLAS routine SGEMV (dense matrix-vector multiply) into a ma t rix-vector multiply routine for band matrices that performs about as well as the band BLAS routine SGBMV. A general sparse matrix-vector routine performs better than the corresponding SPARSEKIT routine AMUX. Similar results are shown for transforming some other matrix operations. The operation that the authors had the most problem with is multiplying the transpose of two matrices. Considerable clever programming was necessary to make this operation efficient. As the authors note, sparse matrix multiplication is to be avoided, but nonetheless this shows that there is more to do in writing sparse compilers. The authors propose two solutions to cases where significant modifications to a dense code are necessary for the compiler to produce efficient sparse code. First, the restructuring capabilities of the compiler should be improved. Second, programmers should adhere to rules about how to structure the program. This second solution means that there will always be something for us to teach people about sparse programming. The first is a more useful solution, which I hope will lead to further results on this subject. This paper holds out promise for those who like developing sophisticated sparse matrix programs, but do not want to be sophisticated sparse matrix programmers. It is quite readable and has a good bibliography.