The Mailman Algorithm: A Note on Matrix Vector Multiplication
Edo Liberty, Steven W. Zucker · 2008
Given an m × n matrix A we are interested in applying it to a real vector x ∈ R n in less then the straightforward O(mn) time.For an exact, deterministic computation at the very least all entrees in A must be accessed, requiring O(mn) operations and matching the running time of naively applying A tox.However, we claim that if the matrix contains only a constant number of distinct values, then reading the matrix once in O(mn) steps is sufficient to preprocess it such that any subsequent application to vectors requires only O(mn/ log(max{m, n})) operations.Theoretically our algorithm can improve on recent results for dimensionality reduction and practically it is useful (faster) even for small matrices.