Re: Fast solution to very small eigenvalue problem

From: Peter Spellucci (nospamspellucci_at_fb04373.mathematik.tu-darmstadt.de)
Date: 06/24/04 

Date: Thu, 24 Jun 2004 17:34:34 +0000 (UTC)

In article <PCn*9dSnq@news.chiark.greenend.org.uk>,
 Mark Mackey <markm@chiark.greenend.org.uk> writes:
>Hi all.
>
>I need to find the eigenvector corresponding to the largest eigenvalue
>of a 4x4 matrix very quickly (because I'm doing it on hundreds of
>thousands of 4x4 matrices). The current code I'm maintaining has a
>simple Jacobi solver, which is (a) slow (it only does 30K matrices/s on
>my PC), and (b) probably overkill, as it returns all of the
>eigenvectors. I've vaguely looked at LAPACK etc, but those routines are
>AFAIK optimised for good performance on large matrices, not small ones.
>
>Does anyone have any suggestions as to the most efficient way to solve
>this problem? Extreme accuracy is not required. 4x4 is probably small
>enough that there's an analytic solution :).
>
>--
>Mark Mackey
>"The determined Real Programmer can write Fortran programs in any language."
> - "Real Programmers don't use Pascal"

you did not mention it by from "jacobi" I conclude -> symmetric.
hence:
1) transform to tridiagonal form. don't use LAPACK, write this yourself, just
   3 givens rotations.
2) use bisection on -norm(A),norm(A) for example the infinity norm =
   max row sum of abs-values.
   bisection means counting the negative pivots in the lu-decomposition of
   the tridiagonal matrix -mu*I, without pivoting, replacing a zero pivot by eps>0
   this disturbs the eigenvalues by at most eps. if the number of negative pivots is
    <= 3 at mu then mu = new lower bound, otherwise mu = new upper bound,
  until sufficient precision is attained.
3) solve now (A-mu I)*x =0 using complete pivoting and setting artificially x(4)=1,
   substituting back then.
done
hth
peter

Relevant Pages

  • Re: Fast solution to very small eigenvalue problem
    ... Mark Mackey writes: ... >I need to find the eigenvector corresponding to the largest eigenvalue ... I've vaguely looked at LAPACK etc, ... if the number of negative pivots is ...
    (sci.math.num-analysis)
  • Re: Matrix Diagonalization
    ... Fatemeh wrote: ... I tried to diagonalized a matrix via Lapack. ... but the result of eigenvector ... If x is an eigenvector of A, so is c.x, where c is a scalar. ...
    (comp.lang.fortran)
  • Re: Matrix Diagonalization
    ... I tried to diagonalized a matrix via Lapack. ... but the result of eigenvector ... If x is an eigenvector of A, so is c.x, where c is a scalar. ... Much better to try the case of all eigenvalues having differing values. ...
    (comp.lang.fortran)
  • Re: Fast solution to very small eigenvalue problem
    ... Mark Mackey wrote: ... > I need to find the eigenvector corresponding to the largest eigenvalue ... Extreme accuracy is not required. ... > enough that there's an analytic solution:). ...
    (comp.programming)
  • Re: Fast solution to very small eigenvalue problem
    ... Mark Mackey wrote: ... > I need to find the eigenvector corresponding to the largest eigenvalue ... Extreme accuracy is not required. ... > enough that there's an analytic solution:). ...
    (sci.math.num-analysis)