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

On Sun, 02 Apr 2006 22:34:23 -0400, 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.

quasi

Whoops -- now that I see R.G. Vickson's reply, I realize that I missed
the "k". I read it as 22 x 22 which is not big at all.

If k means 1000, then a 22k x 22k matrix is a big matrix and might be
too big for the CAS progs. Maybe, maybe not. They can at least store
such a matrix if you have enough RAM and/or disk space, but the
problem will then be time. CAS packages are slow relative to custom
software written in compiled languages such as C or C++.

The space complexity of your problem is O(n^2), but the time
complexity is O(n^3) (actually a little less -- O(n^2.81), I think,
with specialized algorithms).

O(n^3) for your problem means some constant times 10^13. Given the
simple requirements of the problem, the constant is probability not
too big, but with that time complexity, I wouldn't even bother with a
CAS.

Instead, I would write a custom program in C. You will also need a
bignum package or custom bignum routines since even though your matrix
entries are all 0,1, the characteristic polynomial is almost certain
to have coefficients outside the range of standard integer sizes.
Also, even if the eigenvalues get approximated as decimals (or complex
numbers with decimal components), you definitely want to get the
coefficients of the characteristic polynomial exactly as integers. All
approximations should be deferred to the root finding phase.

My gut feel is that finding the eigenvalues of a 22k x 22k matrix is
within reach of modern computers, but it might take days, weeks, or
months, depending on the computing power (ram, cpu speed, etc.) and
the software used. However, it might be possible to get a substantial
speedup by using multiple computers together with algorithms oriented
to parallel processors.

Can I ask, what is the application?

quasi
.

Relevant Pages

  • Re: Guter 3D Function Plotter gesucht
    ... Wenn du die Möglichkeit hast günstige Studenten- oder Schullizenzen zu ... CAS zu werfen: Maple,Mathematica,Mupad ... dass Mathematica mit Version 6 eine komplett neue ... Maple ...
    (de.sci.mathematik)
  • Re: "Take home CAS" for students?
    ... and looking at the place of a CAS within them. ... > For a while I was investigating MuPAD, and although I like MuPAD very ... > I've just started dipping my toes into Maxima, ... Fill in the nine missing integers so that the equations are correct and ...
    (sci.math.symbolic)
  • My Ideal CAS
    ... I use Maxima, and I think that it is generally excellent. ... short of my ideal, however, which would have the following features: ... and shared (also like Google docs). ... that is better than the CAS's coverage of that area, ...
    (sci.math.symbolic)
  • Re: maxima: integration
    ... It's the answer any CAS known ... The problem is maxima doesn't report the absolute value eg. ... complex numbers, not just the reals. ... expressions differ by only a constant, one is a correct antiderivative if ...
    (sci.math.symbolic)
  • Re: CAS =?windows-1252?Q?f=FCr_Lernen_und_Studium?=
    ... Florian Lindner wrote: ... Beim umschauen ist mir Maple und Mathematica aufgefallen, ...
    (de.sci.mathematik)