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

On Tue, 04 Apr 2006 01:01:39 +0300, Toni Lassila <toni@xxxxxxxxxxxx>
wrote:

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

On 3 Apr 2006 16:38:13 GMT, israel@xxxxxxxxxxx (Robert Israel) wrote:

In article <mq02325o5dnhc0th2k7i6kpmd8in5peh71@xxxxxxx>,
David C. Ullrich <ullrich@xxxxxxxxxxxxxxxx> wrote:

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

There are less naive ways to find the characteristic
polynomial of large integer matrices (I'm not sure
how feasible 22k x 22k is). Suppose your matrix A is
n x n. You could calculate P(k) = det(A - k I) for
n different integers k, and use Lagrange interpolation
to find P(x). It might be best to do the calculations
mod p for several primes p whose product is larger
than twice some bound on the coefficients of P(x), and
then reconstruct the coefficients using the Chinese
Remainder Theorem.

You anticipated some of the tricks I had in mind (but not all). Of
course, the tricks are mostly standard, but they still always somehow
feel like magic.

The mod p trick is a natural for this problem. Either work mod p for a
sequence of primes p, lifting the results on the fly with the Chinese
remainder Theorem, or else do the whole thing mod p^k, with p fixed
but successively incrementing k (or perhaps doubling it).

Interpolation is also a key trick. After all, assuming we can actually
compute p(k)=det(A-kI) for a given integer k in a reasonable amount of
time, then, in principle, we can get n+1 values of p. But p is a
polynomial of degree n, so do the coefficients really think they can
hide? I guess they never heard of interpolation (together with the mod
p tricks, of course).

For sure, some estimate is needed on the time and space required to
compute a single value p(k). Getting n+1 values might very well be out
of bounds, I'm not sure.

Also, while interpolation is certainly a candidate strategy, there are
various other ideas and tricks which are potentially as good or
better.

For one thing, I'm not even sure we need the characteristic polynomial
at all -- we only need the roots. If evaluation of p(k) is fast
enough, why not simply root search directly on p(x).

But my main point is, I would never trust anything but exact integer
or rational arithmetic on a problem of this size. An alternative is
interval arithmetic which still exact in the sense of guaranteed
bounds.

That's a nice principle, but there are reasons why we don't compute
everything with exact rational arithmetic to arbitrary precision. You
still haven't explained how you intend to store all those rationals in
memory and still be able to calculate to "arbitrary precision" without
running out of memory.

How are you even going to evaluate a polynomial of degree 22,000 in a
given rational point without running out of memory? Not to mention
doing it many times iteratively as is probably needed to achieve
"arbitrary precision".

I admit I might be missing some "gotcha", but I don't think a single
evaluation at a rational point is a problem. It seems straightforward.

Assume the polynomial p(x) of degree n (n=22,000) has known integer
coefficients (bignums), all stored in RAM. Note that the size of the
coefficients will presumably be large but, since the original matrix
had coefficients all 0s and 1s, I think we can bound the coefficients
of p(x) to O(n), hence the space requirement for storing the
coefficients of p is O(n^2).

Then to evaluate p(a/b) doesn't seem like a problem. The denominators
are all powers of b and we can even homogenize if desired, so as to
defer division to the end. Moreover, it might be expedient to restrict
the choice of rational test points so that the denominators are
required to be powers of 2 (or perhaps powers of 10).

The size of a,b need not be so great since we only need accuracy
sufficient to separate the roots and to locate them to within the
specified tolerance.

Since a,b are relatively small, my guess is that evaluating p(a/b)
should require storage at most O(n^2), and probably a lot less.

quasi
.

Relevant Pages

  • Re: tetration and logaritms
    ... first another word on the matrix-method: ... then you have a matrix (of coefficients). ... This is then simply "my" matrix-method..(I collect like powers ... You gave a polynomial interpolation approach, ...
    (sci.math)
  • Re: rational solution to a bivariate polynomial
    ... Gerry Myerson wrote: ... where the coefficients are rational. ... The Gaussian rationals, ...
    (sci.math)
  • Re: Special properties of the ring of complex numbers
    ... This polynomial does not have rational coefficients. ... What about Kummer's ring? ... The algebraic closure of the rationals is, by definition, the smallest ... algebraically closed field that contains the rationals. ...
    (sci.math)
  • Re: conditions for this polynomial to be in Q[X]
    ... 2k coefficients, one for each of the ai's and bi's). ... In contrast to considering the primitive, have a look at the derivatives ... rationals. ...
    (sci.math)
  • Re: Where is the Galois group?
    ... the field of rationals -). ... I.e. if it contains no divisors of zero. ... I assume that has three distinct roots. ... with coefficients in F. So the companion matrix of the second degree factor ...
    (sci.math)
Quantcast