Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2009

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Eigenvalues of sparse arrays

  • To: mathgroup at smc.vnet.net
  • Subject: [mg102378] Re: Eigenvalues of sparse arrays
  • From: gopher <gophergoon at gmail.com>
  • Date: Fri, 7 Aug 2009 05:30:52 -0400 (EDT)
  • References: <200907310952.FAA19221@smc.vnet.net> <h50sjj$6pl$1@smc.vnet.net>

On Aug 3, 4:49 am, Mark McClure <mcmcc... at unca.edu> wrote:
> On Sun, Aug 2, 2009 at 5:59 AM, gopher <gopherg... at gmail.com> wrote:
> > Thanks for your reply. I read those docs but IMO they are somewhat
> > misleading. They state that the Arnoldi method may not converge but
> > not that it may converge and still give spurious eigenvalues.
>
> I agree; a warning should be issued.  There are simple tests based on
> condition numbers for this sort of thing.
>
> The matrix I was using is here (it is only 156x156):
>
> >https://netfiles.uiuc.edu:443/aroy2/www/sparse%20array/bugmatrix.dat
>
> Arnoldi iteration is a technique to find the *largest* eigenvalue of a
> matrix.  We can find other eigenvalues of the matrix A by applying Arnoldi
> iteration to the matrix (A-sI)^(-1), where s is a number close to the
> eigenvalue we want. This works since s+1/m is an eigenvalue of A close tos,
> whenever m is a large eigenvalue of (A-sI)^(-1).  Not surprisingly, there is
> a problem if s is too close to an exact eigenvalue, for then A-sI is
> singular.  A simple test for this possibility is the condition number of
> A-sI, which should not be too large.  In your case, you are looking for
> eigenvalues close to zero of a matrix that is singular to start with.  The
> condition number of this matrix is huge, since it's singular.
>
> dat = N[Import[
>     "https://netfiles.uiuc.edu/aroy2/www/sparse%20array/bugmatrix.dat";]];
> sp = SparseArray[dat];
> LinearAlgebra`MatrixConditionNumber[sp]
>     7.22615*10^17
>
> We can fix the situation by using the Shift sub-option of the Arnoldi
> method.  This options specifies the number s and should be set close to
> zero, but certainly not equal to zero.  We can do this as follows.
>
> Eigenvalues[sp, 6,
>  Method -> {"Arnoldi", "Shift" -> 0.01}]
>     {0.382326, -0.382326, 0.350062, -0.350062, 4.74967*10^-15,
> 9.95731*10^-16}
>
> Eigenvalues[dat, -6]
>     {0.382326, -0.382326, -0.350062, 0.350062, 2.29823*10^-15,
> 7.57673*10^-16}
>
> Hope that helps,
> Mark

Thanks very much, Mark and Roman. That was quite educational.

I am going to submit a bug report about this since it seems
Mathematica ought to give at least a warning when shift is too close
to an eigenvalue, given that the user cannot explicitly choose Lapack
over the Arnoldi method.

Abhishek


  • Prev by Date: Re: A Sum-like notation for iteration
  • Next by Date: Re: Re: Simple Slideshow templates?
  • Previous by thread: Re: Eigenvalues of sparse arrays
  • Next by thread: Re: Mapping GPS data