Scribd
Upload
6 views6 pages

Understanding Sparse and Symmetric Matrices

The document discusses matrices, focusing on symmetric and sparse matrices. It explains how symmetric matrices can be stored using a 1-D array and how sparse matrices, which contain many zero elements, can be represented using either an array or a linked list. Additionally, it highlights the limitations of using a 1-D array for sparse matrices and the advantages of linked representations.

Uploaded by

Pratyush Barik
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
6 views6 pages

Understanding Sparse and Symmetric Matrices

The document discusses matrices, focusing on symmetric and sparse matrices. It explains how symmetric matrices can be stored using a 1-D array and how sparse matrices, which contain many zero elements, can be represented using either an array or a linked list. Additionally, it highlights the limitations of using a 1-D array for sparse matrices and the advantages of linked representations.

Uploaded by

Pratyush Barik
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd

Matrices

Ms. Dincy Davis


Department of Computer Science
Symmetric Matrix
 An n x n matrix can be represented using 1-D
array of size n(n+1)/2 by storing either the lower or
upper triangle of the matrix
 Use one of the methods for a triangular matrix
 The elements that are not explicitly stored may be
computed from those that are stored
– How do we compute this?

2
Sparse Matrix
A matrix is sparse if many of its elements are zero
 A matrix that is not sparse is dense
 The boundary is not precisely defined
– Diagonal and tridiagonal matrices are sparse
– We classify triangular matrices as dense
 Two possible representations
– array
– linked list

 Read Example 7.6

3
Array Representation of Sparse Matrix
 The nonzero entries may be mapped into a 1D
array in row-major order
 To reconstruct the matrix structure, need to record
the row and column each nonzero comes from

4
Array Representation of Sparse Matrix
template<class T> template<class T>
class Term { class sparseMatrix {
private: private:
int row, col; int rows, cols,
T value; int terms;
}; Term<T> *a;
int MaxTerms;
public:
//…
};

5
Linked Representation of Sparse Matrix
• A shortcoming of the 1-D array of a sparse matrix is that we
need to know the number of nonzero terms in each of the
sparse matrices when the array is created
• A linked representation can overcome this shortcoming

You might also like