Incorrect eigenvalues SciPy sparse linalg.eigs, eigsh for non-diagonal M matrix

Question

Why do eigh and eigsh from scipy.sparse.linalg as used below give incorrect results when solving the generalized eigenvalue problem A * x = lambda * M * x , if M is non-diagonal?

import mkl
import numpy as np
from scipy import linalg as LA
from scipy.sparse import linalg as LAsp
from scipy.sparse import csr_matrix

A = np.diag(np.arange(1.0,7.0))
M = np.array([[ 25.1,   0. ,   0. ,  17.3,   0. ,   0. ],
       [  0. ,  33.6,  16.8,   8.4,   4.2,   2.1],
       [  0. ,  16.8,   3.6,   0. ,  11. ,   0. ],
       [ 17.3,   8.4,   0. ,   4.2,   0. ,   9.5],
       [  0. ,   4.2,  11. ,   0. ,   2.7,   8.3],
       [  0. ,   2.1,   0. ,   9.5,   8.3,   4.4]])

Asp = csr_matrix(np.matrix(A,dtype=float))
Msp = csr_matrix(np.matrix(M,dtype=float))

D, V = LA.eig(A, b=M)

eigno  = 4
Dsp0, Vsp0 = LAsp.eigs(csr_matrix(np.matrix(np.dot(np.linalg.inv(M),A))),
                         k=eigno,which='LM',return_eigenvectors=True)
Dsp1, Vsp1 = LAsp.eigs(Asp,k=eigno,M=Msp,which='LM',return_eigenvectors=True)
Dsp2, Vsp2 = LAsp.eigsh(Asp,k=eigno,M=Msp,which='LA',return_eigenvectors=True,
                          maxiter=1000)

From LA.eig and checking with MatLab the eigenvalues for this small generalized eigenvalue problem with test matrices A and M should be:

D = [ 0.7208+0.j,  0.3979+0.j, -0.3011+0.j, -0.3251+0.j,  0.0357+0.j,  0.0502+0.j]

I want to use sparse matrices because the actual A and M matrices involved are around 30,000 x 30,000. A is always square, real and diagonal, M is always square, real and symmetric. When M is diagonal I get the correct results. However, both eigs and eigsh give incorrect results when solving the generalized eigenvalue problem for a non-diagonal M matrix.

Dsp1 = [-1.6526+2.3357j, -1.6526-2.3357j, -0.6243+2.7334j, -0.6243-2.7334j]

Dsp2 = [ 2.01019097,  3.09248265,  4.06799498,  7.01216316]

When I convert the problem to the standard eigenvalue form M^-1 * A * x = lambda * x, eigs gives the correct result (Dsp0). For large matrices this is not an option because it takes too long to compute the inverse of M.

I noticed that using mkl or not yields different Dsp1 and Dsp2 eigenvalues as well. Could this eigenvalue problem be caused by an issue with my Python installation? I am running Python 2.7.8 anaconda with SciPy 0.15.1 - np19py27_p0 [mkl] on Mac OS 10.10.2.

Warren Weckesser · Accepted Answer · 2015-02-12T14:04:50.560

5

Both eigs and eigsh require that M be positive definite (see the descriptions of M in the docstrings for more details).

Your matrix M is not positive definite. Note the negative eigenvalues:

In [212]: M
Out[212]: 
array([[ 25.1,   0. ,   0. ,  17.3,   0. ,   0. ],
       [  0. ,  33.6,  16.8,   8.4,   4.2,   2.1],
       [  0. ,  16.8,   3.6,   0. ,  11. ,   0. ],
       [ 17.3,   8.4,   0. ,   4.2,   0. ,   9.5],
       [  0. ,   4.2,  11. ,   0. ,   2.7,   8.3],
       [  0. ,   2.1,   0. ,   9.5,   8.3,   4.4]])

In [213]: np.linalg.eigvals(M)
Out[213]: 
array([ 45.92443169,  33.92113421, -13.12639751, -10.6991868 ,
         5.34183619,  12.23818222])

edited Feb 12 '15 at 14:04

answered Feb 12 '15 at 13:47

Warren Weckesser

110,654
19
194
214

What Python packages can solve generalized eigenvalue problems with sparse indefinite, symmetric M matrices? It seems SciPy and PySparse cannot do this. – Feb 13 '15 at 18:54
2

@bjvanbruchem You might be able to use the `sigma` parameter in the scipy `eigs[h]` function to use the shift-invert method, or just add a constant to the diagonal to make the eigenvalues positive. – rubenvb Oct 08 '15 at 09:07
@rubenvb That is indeed the correct approach for this problem. I have solved the issue using scipy eigsh with a value for sigma and mode='buckling'. – Oct 26 '15 at 11:43

Incorrect eigenvalues SciPy sparse linalg.eigs, eigsh for non-diagonal M matrix

1 Answers1

Linked