Re: Compute eigen values/vectors of a 22k x 22k matrix


quasi wrote:
On Sun, 02 Apr 2006 21:04:15 -0700, Ronald Bruck <bruck@xxxxxxxxxxxx>
wrote:

In article <h721325jlvf4na3dbm6m9mithpl1l0355s@xxxxxxx>, quasi
<quasi@xxxxxxxx> wrote:

On 2 Apr 2006 19:28:31 -0700, "rveloso" <rvelosoo@xxxxxxxxx> wrote:

Hi all, wonder if anyone has suggestion about how to compute eigen
values/vectors of a 22k x 22k matrix. The matrix only has 0's and 1's
and is symmetric.
Any free software/optimal fast techiques are appreciatted. Thanks,

Any CAS program (for example Maple, Mathematica, or Maxima) should be
able to do it easily.

While I prefer Maple or Mathematica, they both cost money whereas
Maxima is free.

I really don't think this is very practical. CAS's have large
overhead--just naively creating a 22000 x 22000 random matrix of 0's
and 1's (without exploiting the symmetry, without forcing the entries
to be IEEE reals--so they're created as pointers to integer) takes
several minutes in Mathematica (on a machine with 4GB of physical
memory, running Mac OS X 10.4.5). I shudder to think what the time to
compute the eigenvalues would be.

Yes, I agree.

I had read the original post too quickly and thought the dimensions in
question were only 22 x 22.

In fact, come to think of it, just
the STORAGE requirements, exploiting the symmetry and using
double-precision reals, would be 1/2 * 22000^2 * 8 bytes, close to 2GB.
That's without ANY auxiliary storage for computing. Gonna be a lot of
swapping going on.

I think the easiest way to do this would be to write a little program
in C (or FORTRAN) to create such a matrix and then call the appropriate
eigenvalue routine from LAPACK. Shouldn't be hard, if you have the
RAM. I have a routine (to find eigenvalues/eigenvectors by Jacobi
iterations) which works in high precision (I routinely do 16384 bits,
but that's out of the question for this problem), using the Gnu
Multi-Precision Library, and it might be interesting to code that up to
compare with the numerical results of double-precision. But of course
there's all the frigging overhead of GMP, and my AMD64 Linux box only
has 2GB of physical RAM... Damn, where are those 16GB DIMMs when you
need them? :-)

How 'bout some numerical analysts weighing in on this? Naively, 22000
seems kinda big, but what sort of sizes do people routinely compute the
eigenvalues for nowadays? For example, how does computation time go up
with the dimension n of a square matrix? n^2? n^3? IIRC, asking for
the eigenVECTORS (besides becoming very inaccurate as you move down the
list of eigenvalues) takes a lot longer. And still more storage. But
surely the problem is nicely parallelizable?

I'm guessing 22000 is rather moderate compared to what can be done
today, on big fast supermultiprocessor machines. But I'm guessing.

Yes, I think it's within range (with high-powered PCs and custom
software), but unless it's really important, I would forget it. The
logistics will surely be a nightmare.

On the other hand, if you wait a few years (decades?), it might be a
piece of cake -- just a toy problem that any schoolchild could run on
their pocket calculator,

So, there would be some point in time when starting would produce an
answer just at the time of a later start with a better method. This is
like sending people on a voyage to a distant star. Their descendants
arrive after centuries, only to meet their distant ancestors who arrive
by the latest wormhole.
--
john

.

Relevant Pages

  • Re: Compute eigen values/vectors of a 22k x 22k matrix
    ... Any CAS program (for example Maple, Mathematica, or Maxima) should be ... and 1's (without exploiting the symmetry, ... compute the eigenvalues would be. ... I have a routine (to find eigenvalues/eigenvectors by Jacobi ...
    (sci.math)
  • Re: Compute eigen values/vectors of a 22k x 22k matrix
    ... Any CAS program (for example Maple, Mathematica, or Maxima) should be ... and 1's (without exploiting the symmetry, ... compute the eigenvalues would be. ... I have a routine (to find eigenvalues/eigenvectors by Jacobi ...
    (sci.math)
  • Re: ARPACK to get all eigenvalues
    ... >Peter Spellucci wrote: ... >> the spectrum near the shift and varying the shift you might finally be able ... eigenvalues of a huge real symmetric matrix, ... (exploting symmetry) ...
    (sci.math.num-analysis)
  • Problem with eigs()
    ... am trying to find the largest and smallest eigenvalues using ... eigs() routine. ... Error with ARPACK routine dsaupd: ... a preconditioner, by solving generalized eigenvalue problem, ...
    (comp.soft-sys.matlab)
  • Re: repeated eigenvalues
    ... > is there any way of telling whether a matrix will have repeated eigenvalues? ... Physically motivated (usually Hermitian) matrices usually have repeated ... Sometimes the symmetry is obvious, sometimes it is "hidden" and requires ... Professor Emeritus of Physics ...
    (sci.math.num-analysis)