I meant to write: twice in case of a rectangular matrix. By the way, if you want to have the two sides matrices [U,D,V]=svd(A) You will need to run Lanczos twice: once with A and another time with A'. So run time should be doubled.
On Mon, Dec 12, 2011 at 7:08 PM, Danny Bickson <[email protected]>wrote: > 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. >> > >
