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