Title

An Optimal Storage Format For Sparse Matrices

Keywords

Data structures; Matrix vector product; Sparse matrix

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×6 sparse matrix to show the data structures and the algorithm to compute Ax = y using the TJDS format. © 2004 Elsevier B.V. All rights reserved.

Publication Date

4-30-2004

Publication Title

Information Processing Letters

Volume

90

Issue

2

Number of Pages

87-92

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/j.ipl.2004.01.014

Socpus ID

1542425156 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/1542425156

This document is currently not available here.

Share

COinS