Sparse matrix compression

Compressing a checkered pattern

Assume that we want to compress a matrix \(A\), originally stored in BSR format following a checkered pattern such as the one in the figure:

Checkered pattern of non-zero elements in matrix \(A\in\mathbb{R}^{361\times{}361}\) and compressed into blocks of size \(19\times 19\).

Using the TRE tool, we get the following 5-dimensional polyhedron (using the same format you are used to but without the leading 1’s column):

\begin{equation} \mathbf{U}|\overrightarrow{w}=\left[\begin{array}{ccccc|c}-1&0&0&0&0&28\\ 0&-1&0&0&0&1\\ -1&-1&0&0&0&28\\ 0&0&-1&0&0&18\\ 0&-1&0&-1&0&28\\ 0&0&0&0&-1&18\\ 1&0&0&0&0&0\\ 0&1&0&0&0&0\\ 0&0&1&0&0&0\\ 0&0&0&1&0&0\\ 0&0&0&0&1&0\\ \end{array}\right]\nonumber \\ \end{equation}

and the projection vector:

\begin{equation} \overrightarrow{c}=\left[\begin{array}{ccccc}41154&20596&1083&38&1\end{array}\right]\nonumber \\ \end{equation}

This reconstruction was raised from the “flattened” positions of the array, i.e., \(f((x,y))=x*361+y\).

In order to transform a point \(\overrightarrow{p}\) from the compressed 5-dimensional space to the original 2-dimensional one:

\begin{equation} \overrightarrow{p}=\left[\begin{array}{ccccc}p_{1}&p_{2}&p_{3}&p_{4}&p_{5}\end{array}\right]\nonumber \\ \end{equation} \begin{equation} f(\overrightarrow{p})=\overrightarrow{p}\cdot\overrightarrow{c}\nonumber \\ \end{equation} \begin{equation} (x,y)=(f(\overrightarrow{p})/361,f(\overrightarrow{p})\%361)\nonumber \\ \end{equation}

i.e., we first translate from the 5-dimensional version to the flattened one, and then from the flattened to the 2-dimensional one.

The inverse translation is a bit more complex. It must fulfill two conditions:

\begin{equation} f(\overrightarrow{p})=f((x,y))\nonumber \\ \end{equation} \begin{equation} \overrightarrow{p}\in\mathcal{D}(U|w)\nonumber \\ \end{equation}