I have the following situation: I have a sequence of vectors $x_1, x_2,.. $ and for each I want to compute the product $Ax_i$ where $A$ is fixed at the outset. Although there is no information about the structure of $x_i$, $A$ typically has a particular pattern where many values are repeated and I would like to compute these products as fast as possible.
One example of $A$ looks like this:
Here the white regions are 0.
I wonder if there is some way of storing information about $A$ or modify it somehow that would allow me to reduce the number of operations for each product. For rows that are all 0 this is trivial – one can just store the row indicies that indicate such rows. It's also possible to store information about which rows are duplicated so as to reuse row computations. I have also considered ordering the rows of the matrix such as to minimize the mean difference between each row and only compute the difference at each row. This seems to run into problems for the more complicated patterns, however.
I was wondering if there is any known methods for these kinds of problems.
Edit: another idea I had is that since the no. of unique values in the matrix is fairly low, one could decompose the product as $Ax = A_1x + A_2x + \dots A_nx$ where $A_i$ contains only one unique value, but I'm still not sure if this can provide any advantage for this problem.