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

On Mon, 03 Apr 2006 13:21:52 +0300, Toni Lassila <toni@xxxxxxxxxxxx>
wrote:

On Mon, 03 Apr 2006 02:49:23 -0400, quasi <quasi@xxxxxxxx> wrote:

On Mon, 03 Apr 2006 09:27:28 +0300, Toni Lassila <toni@xxxxxxxxxxxx>
wrote:

On Mon, 03 Apr 2006 00:16:57 -0400, quasi <quasi@xxxxxxxx> wrote:

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 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.

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).

Strassen's algorithm has nothing to do with finding eigenvalues. You
never ever do any matrix-matrix multiplications or decompositions to
matrices of that size.

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.

OK, that is not going to get you anything but garbage.
You don't find the eigenvalues of any matrix by computing anything with the
characteristic polynomial.

Well, maybe it's not the best method, but explain why it's not
feasible. You get a polynomial with integer coefficients of degree
22000^2 which is not out of range in terms of space.

Even if you were able to compute the polynomial exactly, finding the
roots of high-degree polynomials is numerically unstable. Polynomials
with integer coefficients don't get a free pass.

I don't need a free pass, but I will certainly not trust a root
finding function from a CAS. I'll control the evaluation myself, thank
you.

Consider the following Matlab example:

ermax = zeros(100,1);
ermin = zeros(100,1);
for n=1:100
A = eye(n);
ermax(n) = max(real(roots(poly(A))));
ermin(n) = min(real(roots(poly(A))));
end
t = (1:100);
plot(t,ermax,'x',t,ermin,'o')

The matrix A of course should have eigenvalues all 1, but even for toy
matrices the eigenvalues computed by solving for the roots diverge.

Ah, but you say, is the problem not with the way that Matlab
approximates the characteristic polynomial? Surely it computes the
eigenvalues first and only then approximates the characteristic
polynomial, which is where the problems arise.

Fair enough, then replace with this:

ermax(n) = max(real(roots(poly(ones(n,1)))));
ermin(n) = min(real(roots(poly(ones(n,1)))));

The result is pretty much the same.

Forget Matlab. We've all pretty much agreed that a CAS is a bad idea.

As far as evaluation, I would evaluate exactly using _rational
numbers_.

All the problems you allude to disappear.

The roots can then be isolated to arbitrary precision.

quasi
.

Relevant Pages

  • Re: Compute eigen values/vectors of a 22k x 22k matrix
    ... Any CAS program should be ... Strassen's algorithm has nothing to do with finding eigenvalues. ... coefficients of the characteristic polynomial exactly as integers. ... roots of high-degree polynomials is numerically unstable. ...
    (sci.math)
  • Re: eigenvalues
    ... The question about eigenvalues will have to be at least as hard as ... the corresponding question about roots of polynomials (every polynomial ... But even for polynomials the question is not easy; ... best answer there is probably the use of Sturm sequences, ...
    (sci.math.num-analysis)
  • Re: Compute eigen values/vectors of a 22k x 22k matrix
    ... Any CAS program should be ... Strassen's algorithm has nothing to do with finding eigenvalues. ... roots of high-degree polynomials is numerically unstable. ... matrices the eigenvalues computed by solving for the roots diverge. ...
    (sci.math)
  • Re: Computer Algebra Algorithms lisp vs. C. BENCHMARKS?
    ... If we can decide on a few algorithms to code, ... To be specific I would propose that each of the univariate polynomials would ... In Lisp, Maple, Mathematica, etc. such facilities are part of the language. ... A CAS is a collection of interacting ...
    (sci.math.symbolic)
  • Re: Compute eigen values/vectors of a 22k x 22k matrix
    ... Any CAS program should be ... Strassen's algorithm has nothing to do with finding eigenvalues. ... coefficients of the characteristic polynomial exactly as integers. ... You don't find the eigenvalues of any matrix by computing anything with the ...
    (sci.math)
Loading