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

On Mon, 03 Apr 2006 06:38:51 -0400, quasi <quasi@xxxxxxxx> wrote:

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.

Um. Have you actually _done_ this, or are you certain for
some other reason that your ideas on how to do it are
going to work better than the suggestions of the people
who do have experience in such things?

Using the characteristic polynomial is simply hopeless
here. Honest.

First question: How long does it take to _find_ the
characteristic polynomial of a 22kx22k matrix?

A naive approach to an nxn determinant takes n! steps.
You can find the determinant of an nxn _numerical_
matrix in far fewer steps using gaussian elimination.
Trying to find the determinant of a polynomial-valued
matrix that way is going to involve thousands of
intermediate matrices whose entries are rational
functions of very high degree, or if you're clever,
at least polynomials of very high degree. How much
space does it take to _store_ a 22kx22k matrix when
each entry is a polynomial of degree 20k? How long
does it take to calculate the gcd of two entries
in such a matrix?

quasi


************************

David C. Ullrich
.

Relevant Pages

  • 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: 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. ... roots of high-degree polynomials is numerically unstable. ... matrices the eigenvalues computed by solving for the roots diverge. ...
    (sci.math)
  • 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: JSH: Keep it simple
    ... arbitrary rule that you take roots of monic polynomials with integer coefficients. ... integral root is divisible by something that is coprime to ... Your claim regarding rational roots of this polynomial cannot do that, since the standard theory makes no claims regarding common factors among such roots. ...
    (sci.math)