A compact sparse matrix representation using random hash functions

In this paper, a practical method is presented that allows for the compact representation of sparse matrices. We have employed some random hash functi ons and applied the rehash technique to the compression of sparse matrices. Using our method, a large-scale sparse matrix can be compressed into some condensed tables. The zero elements of the original matrix can be determine d directly by these condensed tables, and the values of nonzero elements ca n be recovered in a row major order. Moreover, the space occupied by these condensed tables is small. Though the elements cannot be referenced directl y, the compression result can be transmitted progressively. Performance eva luation shows that our method has achieved quite some effective improvement for the compression of randomly distributed sparse matrices. (C) 2000 Else vier Science B.V. All rights reserved.