Efficient Zero/One Matrix-Vector Multiplication Based on Cache

This article describes a new method which we have used for computing matrix-vector products. Matrix-vector multiplication is the core of black-box algorithm, which is effective when we analyze the properties of sparse or structured matrix. Hence it is very useful to optimize the calculation. Here we design an algorithm for large-sized sparse zero-one matrix-vector products based on the theory of cache, whose advantage is that it can reduce cache misses to the minimum. We divide the matrix M into several vertical strips and vector x is stripped by system in the corresponding way. Then we calculate the products of all stripped matrix and the vector, and add all the results together to obtain the Zo matrix-vector product. We use C++ language to implement the algorithm in Windows XP and have experiments to compare the time costs between the Zo and stripped matrix-vector products of various blocking schemes. After many experiments, we find the most appropriate blocking scheme to suit the cache size.