Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: A Generic Programming System for Sparse Matrix Computations
Authors: Mateev, Nikolay
Kotlyar, Vladimir
Pingali, Keshav
Stodghill, Paul
Keywords: computer science
technical report
Issue Date: Jul-1999
Publisher: Cornell University
Abstract: Sparse matrices are stored in compressed formats in which zeros are not stored explicitly. Writing high-performance sparse matrix libraries is a difficult and tedious job because there are many compressed formats in use and each of them requires specialized code. In this paper, we argue that (i) compressed formats should be viewed as {\em indexed-sequential access structures} (in the database sense), and (ii) efficient sparse codes exploit such indexing structures wherever possible. This point of view leads naturally to restructuring compiler technology that can be used to synthesize many sparse codes from high-level algorithms and specifications of sparse formats, exploiting indexing structures for efficiency. We show that appropriate abstractions of the indexing structures of commonly used formats can be provided to such a compiler through the type structure of a language like C++. Finally, we describe experimental results obtained from the {\em Bernoulli Sparse Compiler} which demonstrate that the performance of code generated by this compiler is comparable to the performance of programs in the NIST Sparse BLAS library. One view of this system is that it exploits restructuring compiler technology to perform a novel kind of template instantiation.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
99-1755.pdf353.77 kBAdobe PDFView/Open
99-1755.ps646.02 kBPostscriptView/Open
old.ps206 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us