large matrix eigenvalue problem

I need solve a very large complex matrix (not sparse and not symmetry) eigenvalue problem, e.g., 1e4*1e4 or even 1e6*1e6.

How large dimensions of the matrix can Mathematica support? And, how about the run time?

Or, any one have good suggestions for this?

-
kkkk = 1000;Timing[Eigenvalues[RandomReal[{0, 1}, {kkkk, kkkk}]]][[1]] -> 4.2 seconds, kkkk = 1200; Timing[Eigenvalues[RandomReal[{0, 1}, {kkkk, kkkk}]]][[1]]-> 6.4 seconds. I have a relatively slow computer. –  Jacob Akkerboom Apr 24 '13 at 9:49
Here is a measurement series on a computer with 12 CPUs (not entirely quiet) data = {{1000, 1.7}, {1200, 1.9}, {2000, 6.5}, {4000, 64.7}, {5000, 70.}, {6000, 107.}, {8000, 237.}, {10000, 466.}} First is the size kkkk then are computation seconds. You can extrapolate from that until you run out of memory.... –  user21 Apr 24 '13 at 10:47
1e4 in 12*466s, seems OK for me. Thanks. –  hsxie Apr 24 '13 at 13:13
10000x10000 should be okay on 64 bit machines. For the 10^6 size range I think all you can hope for is to get the largest few using some variant of the power method. This will only fly if you have a simple way to obtain matrix-times-vector without putting the entire matrix in memory. –  Daniel Lichtblau Apr 24 '13 at 14:06

64 bit Mathematica does not have any practical limits on this. What limits you is the speed of your computer and the available memory. A $k\times k$ matrix will take a bit more than $8\times k^2 / 1024^3$ gigabytes of memory, so you see that a $10^6 \times 10^6$ matrix needs ~7500 GB of memory to store. You probably don't have that much in your computer.

As for the speed, start with smaller matrices, benchmark and increase the size slowly. Then you'll be able to to extrapolate how long a given size takes to solve on your computer, and you can make decisions about what computations to attempt.

From my previous experience, the size limit is somewhere between 25000-50000 unless you're prepared to wait for days. But don't trust me on it, measure! A twofold increase in matrix size will make the difference between a day or a week of computation time.

-
Can LAPACK or other packages used in cluster be better? Or, they are the same algorithm? –  hsxie Apr 24 '13 at 13:09
@hsxie LAPACK is an API, not really a package (i.e. it's a standardized set of functions for linear algebra). There are many implementations of it. Mathematica is using one of the fastest ones, the MKL. This means that you won't be able to improve performance by much by pure computational optimization. What you could do theoretically is exploit the structure of your problem (e.g. is the matrix sparse? do you really need all eigenvalues or just a few large ones? maybe there are better methods) –  Szabolcs Apr 24 '13 at 15:14
@hsxie I do not know if there are methods which distribute the matrix throughout the memory of several computers in a cluster. You'd have to google for that. (I know that there are good methods like that if you only want the largest eigenvalue, but reading your question I think you want all of them). –  Szabolcs Apr 24 '13 at 15:15
@hsxie Of course if you could refit your problem for C or Fortran, then (C)LAPACK would most probably be both faster and more economic memorywise to calculate eigenvalues. I recently ran such code and it quite easily solved matrices of size (2^15)*(2^15), requiring around 16GB memory. 2^16 would need ~60GB, and it failed on a machine with 70GB. Needless to say, I did all the prototyping in Mathematica. –  István Zachar Apr 25 '13 at 5:49
For distributed problems there is ScaLAPACK (based on MPI and BLACS). 8TB of RAM, while a lot for a single machine, isn't unreasonable for a mid-sized cluster. The scaling of the computation time is more difficult to get away from, however. –  Oleksandr R. Apr 25 '13 at 12:58

I had a chance to experiment with large matrices (up to 1000 x 1000) or around. The main problem might be coming from a completely different angle. From my experience, you absolutely must use high precision arithmetic (by using SetPrecision with some fairly large number) in order to obtain meaningful results, especially for the extreme values of eigenvalues. Just experiment with Eigenvalues with and without SetPrecision with at least 100-200 digits and you will see if it affects your particular case. To the best of my knowledge, this can't be easily done in most of numeric packages.

-