On Thu, Nov 17, 2011 at 7:21 AM, Jake Mannix <[email protected]> wrote:
> On Thu, Nov 17, 2011 at 5:26 AM, Sean Owen <[email protected]> wrote: > > > One more question. OK, so I use Lanczos to find V_k by finding the top k > > eigenvectors of AT * A. A is sparse. But isn't AT * A dense, then? Is > that > > just how it is? > > > > A'A and AA' are both dense, yes, but you never compute them. Actually, they aren't necessarily dense. Computing them explicitly can still be a pain in a****. > ... > 1) you do two Matrix - Vector multiplications per Lanczos iteration: > first > take (sparse) A and multiply it by a vector v. Then take (also sparse) A' > and multiply it by the now-computed u = Av. A'u = A'(A v) = (A'A)v > This is the traditional method used in most implementations of Lanczos. Jake's one-pass map-reduce is better for our needs.
