A compact sparse matrix representation using random hash functions

✍ Scribed by Ji-Han Jiang; Chin-Chen Chang; Tung-Shou Chen

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 374 KB
• Volume: 32
• Category: Article
• ISSN: 0169-023X
• DOI: 10.1016/s0169-023x(99)00017-8

✦ Synopsis

In this paper, a practical method is presented that allows for the compact representation of sparse matrices. We have employed some random hash functions 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 determined directly by these condensed tables, and the values of nonzero elements can be recovered in a row major order. Moreover, the space occupied by these condensed tables is small. Though the elements cannot be referenced directly, the compression result can be transmitted progressively. Performance evaluation shows that our method has achieved quite some eective improvement for the compression of randomly distributed sparse matrices.