Skyline Storage Format for sparse matrices

A sparse matrix is a matrix in which most of the elements are zero. And a matrix have most of the elements non-zero is called a dense matrix. Sparse matrices are fairly common in numerical analysis.

Skyline matrix storage is a form of a sparse matrix storage format matrix that reduces the storage requirement of a matrix. Here we need to store only the non-zero elements of the sparse matrix and the rest are implied to be zero. This reduces storage space requirements and requires less computation.

Skyline Matrix Storage formats: There are various ways of storing skyline matrix. One of them is discusses next. We take the case when the matrix is symmetric, thus we will have to store only the lower triangular part of the matrix.

  • the format consists of 3 arrays (one dimensional)  :
    • Diagonal:  contains all diagonal elements of matrix
    • Skyline: all skyline elements
    • Index: The ith elements tells where the(i+1)th row of Skyline begins.
  • Thus all elements of Skyline from position Index[i] to Index[i+1] are the off-diagonal elements of row i+1 in increasing column order.

Consider the matrix below:

GUID-ECF0F806-75F2-4E00-B070-6D5B1CAE2A08-low

 

For this matrix:

Diagonal: [1 5 4 7 -5]

Skyline:    [-1 -3 0 6 4 0 ]

Index: [0 1 1 4 6 ]

We can perform operations on this skyline format of matrix with much less complexity.

Here is the link for C++ code that multiplies a skyline matrix with a 1-D array (vector) .

https://github.com/234satwant/felt

Using normal form of matrix the complexity would be O(nXn) whereas using skyline format the complexity can be reduced to O(kXn) where k is the average number of skyline matrix in each row. Since k<n, complexity is reduced.

Note that in worst case the complexity of multiplication would be same in both cases. It is but obvious that the skyline method has advantage only when the matrix is sparse.

  • Advertisements
    Posted in GD

    Leave a Reply

    Fill in your details below or click an icon to log in:

    WordPress.com Logo

    You are commenting using your WordPress.com account. Log Out /  Change )

    Google photo

    You are commenting using your Google account. Log Out /  Change )

    Twitter picture

    You are commenting using your Twitter account. Log Out /  Change )

    Facebook photo

    You are commenting using your Facebook account. Log Out /  Change )

    Connecting to %s