Essays/Eigenvalues

The original text of this page was posted on the forum JForum:programming/2007-August/007959 by John Randall.

A number of ways for calculating eigenvalues in J have been proposed. It is interesting to compare those methods..

NB. LAPACK

require '~addons/math/lapack/lapack.ijs'
require '~addons/math/lapack/dgeev.ijs'
ev=:[: clean_jlapack_ 1 >@{ dgeev_jlapack_

NB. Iterative QR algorithm

rheval=:+/ .*&>/@|.@(128!:0)  NB. Roger Hui
rh=: (<0 1) |: rheval^:_

mseval=:(>&(1&{) +/ .* >&(0&{))&(128!:0)  NB. M. Shimura
ms=: (<0 1) |: mseval^:_

NB. Leverrier-Faddeev Algorithm
char=: 3 : 0
X=.I=.=@i.n=.#y[p=.1
for_k. >:i.n do.
 X=.y +/ . * X
 p=.p,pk=.-k%~+/(<0 1)|:X
 X=.X+pk*I
end.
|.p
)
lf=:>@{:@p.@char

The LAPACK method is a direct method, but does preconditioning.

The QR method is iterative, and so is able to get past small instabilities.

Methods which find the characteristic polynomial, like the LF method, work well on small examples, but because of the instability of finding polynomial roots, may go wrong with large examples.

   dm=:*=@i.@# NB. diagonal matrix

   (-:ev@dm) >:i.20
1
   (-:rh@dm) >:i.20
1
   (-:ms@dm) >:i.20
1
   (-:lf@dm) >:i.20
0

See Also

• LAPACK addon
• QR Decomposition essay
• Eugene McDonnell's At Play with J article Oh, No, Not Eigenvalues Again!
• links to some forum threads on Eigenvalues:
  • • JForum:programming/2007-July/007566
    • JForum:programming/2007-August/007635
    • JForum:programming/2007-August/007957
• search J forums for "eigenvalue"