The Sparse Matrix ADT

Matrices (HSM Ch.2.4.1)
- Stored in a C++ 2 dimensional array
- A sparse matrix object is a set of triples <row,column,value>, where each row-column combination is unique.
- Operations include input, output, transpose, add, multiply.
Sparse Matrix Representation (HSM Ch.2.4.2)
- Fixed maximal number of terms
  - class MatrixTerm
  - class SparseMatrix
  - Terms must be stored in row-major order
  - Matrix may not have as many terms as maximal
- Dynamic number of terms (HSM Ch.2.4.5)
  - slmatrix.h
  - slmatrix.cpp
  - Have to compute size before creation. Hard work to add new terms.
Sparse Matrix Algorithms
- Transpose (HSM Ch.2.4.3)
  - Algorithm does each row of the transposed matrix by looking through all terms for ones in the correct column.
  - Time complexity
    - O(NumberOfTerms * NumberOfColumns)
    - Conventional representation is O(NumberOfRows * NumberOfColumns), which is less than O(NumberOfTerms * NumberOfColumns) except if very sparse.
    - If matrix is not too sparse, NumberOfTerms is O(NumberOfRows * NumberOfColumns), so transpose complexity is O(NumberOfRows * NumberOfColumns²)
- Fast transpose
  - Algorithm computes in advance the starting array index and size for each row in the transposed matrix.
  - Time complexity
    - O(NumberOfTerms + NumberOfColumns), which is less than O(NumberOfRows * NumberOfColumns) for sparse matrices.
    - If matrix is not too sparse then NumberOfTerms is O(NumberOfRows * NumberOfColumns), so complexity is O(NumberOfRows * NumberOfColumns)
  - Pay in space complexity due to the extra storage
- Multiply (HSM Ch.2.4.4)
  - Algorithm (fast) transposes the RHS so that the column elements are in the right order.
  - Complexity
    - Have to account for the multiplications and the indexing in each matrix.
    - For each row of LHS, indexing through the terms of the row is done for each column of RHS, which is O(TermsInLHSRow * NumberofRHSColumns).
      This is done for every row, producing O(NumberOfLHSTerms * NumberofRHSColumns).
    - For each row of LHS, for each column of RHS, indexing through the column's terms of RHS with a possible mulitplication and sum, is done for the number of terms in the column. This is done for all columns, so that in total all terms of the RHS are visited. This produces O(NumberofLHSRows * NumberOfRHSTerms).
    - Total complexity is O((NumberofRHSColumns * NumberOfLHSTerms) + (NumberofLHSRows * NumberOfRHSTerms))
    - Conventional complexity is O(NumberofLHSRows * NumberofLHSColumns * NumberofRHSColumns).
      As NumberofLHSRows * NumberofLHSColumns >= NumberOfLHSTerms and NumberofLHSColumns * NumberofRHSColumns >= NumberOfRHSTerms, this is higher complexity. However the constant factors are again higher.
    - Space complexity is worse than the conventional approach, due to the added space for the transposed matrix and the internal space for fast transpose.

Exercises

Analysis of sparse matrix operations: HSM Ch.2.4, exercise 1,2.
Sparse matrix representation with a dynamic number of terms: HSM Ch.2.4, exercise 8.

Lab Tasks

Exam Style Questions

Define the sparse matrix ADT.
Describe how an array can be effectively used to store a sparse matrix. What is the space complexity of this storage method?
Give an algorithm (at a high level, no programming details are required) for computing the transpose of a sparse matrix, stored using an array. (Higher marks will be earned for an algorithm of lower time complexity). What is the asymptotic complexity of the algorithm?
Give an algorithm (at a high level, no programming details are required) for adding two sparse matrices stored in arrays of fixed size. What is the asymptotic complexity of the algorithm?