Page 97 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes The compressed row storage (CRS) format puts the subsequent non-zeros of the matrix
rows in contiguous memory locations.

Compressed column storage (CCS), also called the Harwell-Boeing sparse matrix format
is identical to the CRS format except that the columns of are stored (traversed) instead of
the rows.

Block matrices typically arise from the discretisation of partial differential equations in
which there are several degrees of freedom associated with a grid point.

Compressed diagonal storage scheme is particularly useful if the matrix arises from a
finite element or finite difference discretisation on a tensor product grid.
The jagged diagonal storage (JDS) format can be useful for the implementation of iterative
methods on parallel and vector processors.
Skyline matrices, also called variable band or profile matrices is mostly of importance in
direct solution methods, but it can be used for handling the diagonal blocks in block
matrix factorization methods.

6.4 Keywords

Block Matrices: Block matrices typically arise from the discretisation of partial differential
equations in which there are several degrees of freedom associated with a grid point.
CCS: Compressed column storage (CCS), also called the Harwell-Boeing sparse matrix format is
identical to the CRS format except that the columns of are stored (traversed) instead of the rows.

CDS: Compressed diagonal storage scheme is particularly useful if the matrix arises from a
finite element or finite difference discretisation on a tensor product grid.
CRS: The compressed row storage (CRS) format puts the subsequent non-zeros of the matrix
rows in contiguous memory locations.
JDS: The jagged diagonal storage (JDS) format can be useful for the implementation of iterative
methods on parallel and vector processors.
SKS: Skyline matrices, also called variable band or profile matrices is mostly of importance in
direct solution methods, but it can be used for handling the diagonal blocks in block matrix
factorization methods.
Sparse Matrices: A sparse matrix is a matrix that allows special techniques to take advantage of
the large number of zero elements.
Triangular Matrices: A triangular matrix is a square matrix in which all the elements either
above or below the main diagonal are zero.

6.5 Review Questions

1. Illustrate with example how to delete an element form an arrays.
2. Elucidate the insert operation on arrays with example.
3. What is a sparse matrix? Discuss its usage with example.

4. Illustrate the concept of representing non-zero elements of a sparse matrix.
5. Discuss various storage schemes used for the matrix.
6. Make distinction between Compressed Row Storage and Compressed Column Storage.

90 LOVELY PROFESSIONAL UNIVERSITY