Re: Compute eigen values/vectors of a 22k x 22k matrix
- From: Toni Lassila <toni@xxxxxxxxxxxx>
- Date: Mon, 03 Apr 2006 09:27:28 +0300
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.
The general methods for finding eigenvalues of large matrices are
iterative. Hermitian Lanczos or something might work in this case if
the matrix is either sparse enough to keep in memory or, failing that,
the matrix-vector product with it can be effectuated efficiently.
The iteration will reduce the system to a smaller tridiagonal form
which has (approximately) some subset of the largest eigenvalues of
the actual matrix as its eigenvalues. If you want all of them, you
have to iterate all the way to the end and then find the eigenvalues
of that tridiagonal matrix. It also gives you a method for finding the
eigenvectors.
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.
Depends a lot on the sparsity and structure of the matrix.
.
- Follow-Ups:
- References:
- Compute eigen values/vectors of a 22k x 22k matrix
- From: rveloso
- Re: Compute eigen values/vectors of a 22k x 22k matrix
- From: quasi
- Re: Compute eigen values/vectors of a 22k x 22k matrix
- From: quasi
- Compute eigen values/vectors of a 22k x 22k matrix
- Prev by Date: Re: JSH: On Missing persons list, draws comic books, and is Mormon
- Next by Date: Re: Compute eigen values/vectors of a 22k x 22k matrix
- Previous by thread: Re: Compute eigen values/vectors of a 22k x 22k matrix
- Next by thread: Re: Compute eigen values/vectors of a 22k x 22k matrix
- Index(es):
Relevant Pages
|
