# 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):

$$\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 \\$$

and the projection vector:

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

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:

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

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:

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