An optimal storage format for sparse matrices

    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