Accession Number:

ADA482124

Title:

The Mailman Algorithm: A Note on Matrix Vector Multiplication

Descriptive Note:

Technical rept.

Corporate Author:

YALE UNIV NEW HAVEN CT DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

2008-01-01

Pagination or Media Count:

9.0

Abstract:

Given an m x n matrix A we are interested in applying it to a real vector x epsilon Rn in less then the straightforward Omn time. For an exact, deterministic computation at the very least all entrees in A must be accessed, requiring Omn operations and matching the running time of naively applying A to x. However, we claim that if the matrix contains only a constant number of distinct values, then reading the matrix once in Omn steps is sufficient to preprocess it such that any subsequent application to vectors requires only Omn logmaxm,ng operations. Theoretically our algorithm can improve on recent results for dimensionality reduction and practically it is useful faster even for small matrices.

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE