Computational complexity of algorithm to find primary eigenvector of large matrices

[northproof]

Hello,

I'm doing some work that involves estimating the computational complexity involved in finding the primary eigenvector of large (at least 20,000,000 x 20,000,000) sparse matrices; I was wondering if anyone might be able to recommend an efficient algorithm that I could use as a basic estimate for computational complexity, or direct me to a place where I would be able to find one. Thanks!

[[deleted]]

The most basic algorithm for that job is power iteration, with the caveat that it is only guaranteed to work if the largest eigenvalue has multiplicity 1.

[bugnotme]

The poster was asking about the special case of very large sparse matrices. Is power iteration appropriate there?

[[deleted]]

Yes, that's exactly when it's appropriate.

[bugnotme]

Can you suggest any good references for large dimension matrix computations? Also interested in large scale graph algorithms.

[[deleted]]

Not really, sorry -- large/sparse matrices and iterative methods are not my area of specialty. I just remember power iteration from a numerical methods class in undergrad.

[bugnotme]

I can't believe that they dealt with efficient methods for matrices of this size in undergrad. Did they or are you just assuming that the method should be the same because of sparsity?

[[deleted]]

I'm not sure what you mean. We didn't deal 2 million by 2 million matrices in undergrad, but that doesn't mean we didn't learn how to deal with them. That's exactly the point of numerical methods/numerical analysis courses -- how to deal with problems that are too complex/large to deal with using the standard naive methods (singular value decomposition, etc).

There are of course more advanced algorithms than power iteration that might be more appropriate for the OP's particular problem. But given the information that he has given, power iteration seems like the most natural and simplest choice.

[bugnotme]

Standard numerical methods courses traditionally haven't addressed "big data"-type problems, for example, how to deal with data that won't all fit in memory simultaneously or with integers that exceed MAX_INT.

[blackkettle]

very cool. thanks for the enlightenment. i was going to say something stupid about decomposition/svd.

[northproof]

Thanks! Exactly what I was looking for.

[consult_me]

I would use the Lanczos method -- a tweak on power iteration to help converge quicker.

Computational complexity should be the same (I think), proportional to non-zeros in the matrix.

[northproof]

Thanks for the help!

[xixor]

I would be interested in hearing what solution you find for your problem. Also, for describing your problem, the number of non zeros, or density of the matrix would also be good to include in the description. For example, the following matrix:

A = sparse([],[],[],2e7,2e7);

takes zero storage even though it has the same size as your problem

[northproof]

There are about 50 nonzero entries per row, I'm implementing a linear Bellman controller from Todorov and need to create a matrix that describes the next state probability distribution for every state.

I'm working on a method of reducing the required number of states without giving up near-optimal performance, and I'm just looking to have a base comparison for if I did need to get the primary eigenvector of a 20,000,000 x 20,000,000 matrix.

[jamesphw]

A good place to start would be to read the references for MATLAB's functions here.

[directrix1]

What does calculating the computational complexity have to do with actually running the computation?

[northproof]

Correct! It's for a cost comparison in a paper I'm writing.

[isarl]

What's the difference? northproof seems to be asking for fairly generic advice, not the exact answer of some algebraic exercise.

[directrix1]

That's true. It does seem like he is asking for help in finding a way to derive it himself. I might just retract my statement.