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.
>
