Sparse Matrices

Question

How can we display a sparse matrix? Someone who wanted to help me said: use linked lists.
Also I have read some where that we should create class like this :

SpMatrix
{
    int non_zero_value;
    int i,j;
}

Exactly what is a sparse matrix, I have read wekipedia and other sites. but the problem isn't solved yet.

thanks in advance.

Answer 1

A sparse is a matrix with most elements equal to 0. For example a matrix that has non-zero elements only on the diagonal is clearly a sparse matrix:

1 0 0 0
0 2 0 0 
0 0 3 0 
0 0 0 4

Clearly it's a waste of space to store all the elements of the matrix since most are zero. There a number of techniques to store such matrices and it really depends on how generic you want to be and to the specific problem in hand.

Most times you end up having a specific class for each different kind of sparse matrix you want to support, e.g. diagonal, triangular, band diagonal, etc. That usually gives you more efficient code than a generic solution.

It's a complex problem with no ready made recipes. You can use linked lists or anything else really.