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 <[email protected]> > 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. >
