mahout-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Danny Bickson <danny.bick...@gmail.com>
Subject Re: Mahout Lanczos SVD complexity
Date Mon, 12 Dec 2011 17:08:32 GMT
In each Lanczos iteration you multiply by the matrix A (in case of a square
matrix)
or twice, by the matrix A' and A. Multiplication is linear in the number of
non zero edges.
See http://en.wikipedia.org/wiki/Lanczos_algorithm
Finally a decomposition of a tridiagonal matrix T for extracting the
eigenvalues.
I think it is also linear in the number of iterations (since the size of T
is number of iterations+1). Note that this code is not distributed since it
can be efficiently done on a single node.
The last step is the Ritz transformation - a product of the intermediate
vectors v
with the eigenvectors. This step may be heavy since those matrices are
typically dense.

Best,

DB

2011/12/12 Fernando Fernández <fernando.fernandez.gonzalez@gmail.com>

> Hi all,
>
> This is a question for everybody, though it may be better answered by Jake
> Mannix. Do you guys know what is the complexity of the algorithm
> implemented in mahout for Lancos SVD? Linear, quadratic, etc..
>
>
> Thanks in advance!!
> Fernando.
>

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message