Sparse Matrix
Table of Contents
If number of nonzero elements is in \(O(n)\) where \(n\) is the number of rows or columns. [Neural Acceleration of Graph Based Utility Functions for Sparse Matrices.pdf: Page 3]
1. Fill In
The fill-in of a matrix are those entries that change from an initial zero to a non-zero value during the execution of an algorithm. (https://en.wikipedia.org/wiki/Sparse_matrix)
2. Banded Matrix
https://en.wikipedia.org/wiki/Sparse_matrix#Banded
- Lower band
- Upper band
- Bandwidth
By rearranging the rows and columns of a matrix A it may be possible to obtain a matrix A′ with a lower bandwidth.
2.1. Graph Bandwidth Problem
https://en.wikipedia.org/wiki/Graph_bandwidth
In graph theory, the graph bandwidth problem is to label the \(n\) vertices \(v_i\) of a graph \(G\) with distinct integers \(f(v_i)\) so that the quantity \(\max{ |f(v_i) − f(v_j) | : v_i v_j \in E }\) is minimized (\(E\) is the edge set of \(G\))
This problem is a special case of Quadratic Bottlneck Assignment Problem (QBAP).
The bandwidth problem is NP-hard, even for some special cases. Regarding the existence of efficient approximation algorithms, it is known that the bandwidth is NP-hard to approximate within any constant, and this even holds when the input graphs are restricted to caterpillar trees with maximum hair length 2.
A heuristic algorithm for obtaining linear graph layouts of low bandwidth is the Cuthill–McKee algorithm. Fast multilevel algorithm for graph bandwidth computation was proposed in.
