Title

An optimal storage format for sparse matrices

Authors

Authors

E. Montagne;A. Ekambaram

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

Abbreviated Journal Title

Inf. Process. Lett.

Keywords

sparse matrix; matrix vector product; data structures; Computer Science, Information Systems

Abstract

The irregular nature of sparse matrix-vector multiplication, Ax = y, has led to the development of a variety of compressed storage formats, which are widely used because they do not store any unnecessary elements. One of these methods, the Jagged Diagonal Storage format (JDS) is, in addition, considered appropriate for the implementation of iterative methods on parallel and vector processors. In this work we present the Transpose Jagged Diagonal Storage format (TJDS) which drew inspiration from the Jagged Diagonal Storage scheme but requires less storage space than JDS. We propose an alternative storage scheme which makes no assumptions about the sparsity pattern of the matrix and only needs three linear arrays instead of the four linear arrays required by JDS. Specifically, the data is aligned in such a way that the permutation array used in JDS, to permute the solution vector back to the original ordering, is unnecessary. This allow us to save the memory space required to store an integer vector of length n, where n stands for the number of columns in the sparse matrix A. This storage saving reaches, for the selection of matrices used in this work, from 14% up to 45% of the number of non-zero values of the sparse matrices. We present a case study of a 6 x 6 sparse matrix to show the data structures and the algorithm to compute Ax = y using the TJDS format. (C) 2004 Elsevier B.V. All rights reserved.

Journal Title

Information Processing Letters

Volume

90

Issue/Number

2

Publication Date

1-1-2004

Document Type

Article

Language

English

First Page

87

Last Page

92

WOS Identifier

WOS:000220453600006

ISSN

0020-0190

Share

COinS