sparse.linalg.eigen.arpack.arpack

Find a few eigenvectors and eigenvalues of a matrix.

Uses ARPACK: http://www.caam.rice.edu/software/ARPACK/

Module Contents

Classes

ArpackError(self,info,infodict=_NAUPD_ERRORS) ARPACK error
ArpackNoConvergence(self,msg,eigenvalues,eigenvectors) ARPACK iteration did not converge
_ArpackParams(self,n,k,tp,mode=1,sigma=None,ncv=None,v0=None,maxiter=None,which=”LM”,tol=0)
_SymmetricArpackParams(self,n,k,tp,matvec,mode=1,M_matvec=None,Minv_matvec=None,sigma=None,ncv=None,v0=None,maxiter=None,which=”LM”,tol=0)
_UnsymmetricArpackParams(self,n,k,tp,matvec,mode=1,M_matvec=None,Minv_matvec=None,sigma=None,ncv=None,v0=None,maxiter=None,which=”LM”,tol=0)
SpLuInv(self,M) SpLuInv:
LuInv(self,M) LuInv:
IterInv(self,M,ifunc=gmres,tol=0) IterInv:
IterOpInv(self,A,M,sigma,ifunc=gmres,tol=0) IterOpInv:

Functions

choose_ncv(k) Choose number of lanczos vectors based on target number
_aslinearoperator_with_dtype(m)
get_inv_matvec(M,symmetric=False,tol=0)
get_OPinv_matvec(A,M,sigma,symmetric=False,tol=0)
eigs(A,k=6,M=None,sigma=None,which=”LM”,v0=None,ncv=None,maxiter=None,tol=0,return_eigenvectors=True,Minv=None,OPinv=None,OPpart=None) Find k eigenvalues and eigenvectors of the square matrix A.
eigsh(A,k=6,M=None,sigma=None,which=”LM”,v0=None,ncv=None,maxiter=None,tol=0,return_eigenvectors=True,Minv=None,OPinv=None,mode=”normal”) Find k eigenvalues and eigenvectors of the real symmetric square matrix
_augmented_orthonormal_cols(x,k)
_augmented_orthonormal_rows(x,k)
_herm(x)
svds(A,k=6,ncv=None,tol=0,which=”LM”,v0=None,maxiter=None,return_singular_vectors=True) Compute the largest k singular values/vectors for a sparse matrix.
class ArpackError(info, infodict=_NAUPD_ERRORS)

ARPACK error

__init__(info, infodict=_NAUPD_ERRORS)
class ArpackNoConvergence(msg, eigenvalues, eigenvectors)

ARPACK iteration did not converge

eigenvalues : ndarray
Partial result. Converged eigenvalues.
eigenvectors : ndarray
Partial result. Converged eigenvectors.
__init__(msg, eigenvalues, eigenvectors)
choose_ncv(k)

Choose number of lanczos vectors based on target number of singular/eigen values and vectors to compute, k.

class _ArpackParams(n, k, tp, mode=1, sigma=None, ncv=None, v0=None, maxiter=None, which="LM", tol=0)
__init__(n, k, tp, mode=1, sigma=None, ncv=None, v0=None, maxiter=None, which="LM", tol=0)
_raise_no_convergence()
class _SymmetricArpackParams(n, k, tp, matvec, mode=1, M_matvec=None, Minv_matvec=None, sigma=None, ncv=None, v0=None, maxiter=None, which="LM", tol=0)
__init__(n, k, tp, matvec, mode=1, M_matvec=None, Minv_matvec=None, sigma=None, ncv=None, v0=None, maxiter=None, which="LM", tol=0)
iterate()
extract(return_eigenvectors)
class _UnsymmetricArpackParams(n, k, tp, matvec, mode=1, M_matvec=None, Minv_matvec=None, sigma=None, ncv=None, v0=None, maxiter=None, which="LM", tol=0)
__init__(n, k, tp, matvec, mode=1, M_matvec=None, Minv_matvec=None, sigma=None, ncv=None, v0=None, maxiter=None, which="LM", tol=0)
iterate()
extract(return_eigenvectors)
_aslinearoperator_with_dtype(m)
class SpLuInv(M)

SpLuInv: helper class to repeatedly solve M*x=b using a sparse LU-decopposition of M

__init__(M)
_matvec(x)
class LuInv(M)

LuInv: helper class to repeatedly solve M*x=b using an LU-decomposition of M

__init__(M)
_matvec(x)
class IterInv(M, ifunc=gmres, tol=0)

IterInv: helper class to repeatedly solve M*x=b using an iterative method.

__init__(M, ifunc=gmres, tol=0)
_matvec(x)
class IterOpInv(A, M, sigma, ifunc=gmres, tol=0)

IterOpInv: helper class to repeatedly solve [A-sigma*M]*x = b using an iterative method

__init__(A, M, sigma, ifunc=gmres, tol=0)
_matvec(x)
dtype()
get_inv_matvec(M, symmetric=False, tol=0)
get_OPinv_matvec(A, M, sigma, symmetric=False, tol=0)
eigs(A, k=6, M=None, sigma=None, which="LM", v0=None, ncv=None, maxiter=None, tol=0, return_eigenvectors=True, Minv=None, OPinv=None, OPpart=None)

Find k eigenvalues and eigenvectors of the square matrix A.

Solves A * x[i] = w[i] * x[i], the standard eigenvalue problem for w[i] eigenvalues with corresponding eigenvectors x[i].

If M is specified, solves A * x[i] = w[i] * M * x[i], the generalized eigenvalue problem for w[i] eigenvalues with corresponding eigenvectors x[i]

A : ndarray, sparse matrix or LinearOperator
An array, sparse matrix, or LinearOperator representing the operation A * x, where A is a real or complex square matrix.
k : int, optional
The number of eigenvalues and eigenvectors desired. k must be smaller than N-1. It is not possible to compute all eigenvectors of a matrix.
M : ndarray, sparse matrix or LinearOperator, optional

An array, sparse matrix, or LinearOperator representing the operation M*x for the generalized eigenvalue problem

A * x = w * M * x.

M must represent a real, symmetric matrix if A is real, and must represent a complex, hermitian matrix if A is complex. For best results, the data type of M should be the same as that of A. Additionally:

If sigma is None, M is positive definite

If sigma is specified, M is positive semi-definite

If sigma is None, eigs requires an operator to compute the solution of the linear equation M * x = b. This is done internally via a (sparse) LU decomposition for an explicit matrix M, or via an iterative solver for a general linear operator. Alternatively, the user can supply the matrix or operator Minv, which gives x = Minv * b = M^-1 * b.

sigma : real or complex, optional

Find eigenvalues near sigma using shift-invert mode. This requires an operator to compute the solution of the linear system [A - sigma * M] * x = b, where M is the identity matrix if unspecified. This is computed internally via a (sparse) LU decomposition for explicit matrices A & M, or via an iterative solver if either A or M is a general linear operator. Alternatively, the user can supply the matrix or operator OPinv, which gives x = OPinv * b = [A - sigma * M]^-1 * b. For a real matrix A, shift-invert can either be done in imaginary mode or real mode, specified by the parameter OPpart (‘r’ or ‘i’). Note that when sigma is specified, the keyword ‘which’ (below) refers to the shifted eigenvalues w'[i] where:

If A is real and OPpart == ‘r’ (default),
w'[i] = 1/2 * [1/(w[i]-sigma) + 1/(w[i]-conj(sigma))].
If A is real and OPpart == ‘i’,
w'[i] = 1/2i * [1/(w[i]-sigma) - 1/(w[i]-conj(sigma))].

If A is complex, w'[i] = 1/(w[i]-sigma).

v0 : ndarray, optional
Starting vector for iteration. Default: random
ncv : int, optional
The number of Lanczos vectors generated ncv must be greater than k; it is recommended that ncv > 2*k. Default: min(n, max(2*k + 1, 20))
which : str, [‘LM’ | ‘SM’ | ‘LR’ | ‘SR’ | ‘LI’ | ‘SI’], optional

Which k eigenvectors and eigenvalues to find:

‘LM’ : largest magnitude

‘SM’ : smallest magnitude

‘LR’ : largest real part

‘SR’ : smallest real part

‘LI’ : largest imaginary part

‘SI’ : smallest imaginary part

When sigma != None, ‘which’ refers to the shifted eigenvalues w’[i] (see discussion in ‘sigma’, above). ARPACK is generally better at finding large values than small values. If small eigenvalues are desired, consider using shift-invert mode for better performance.

maxiter : int, optional
Maximum number of Arnoldi update iterations allowed Default: n*10
tol : float, optional
Relative accuracy for eigenvalues (stopping criterion) The default value of 0 implies machine precision.
return_eigenvectors : bool, optional
Return eigenvectors (True) in addition to eigenvalues
Minv : ndarray, sparse matrix or LinearOperator, optional
See notes in M, above.
OPinv : ndarray, sparse matrix or LinearOperator, optional
See notes in sigma, above.
OPpart : {‘r’ or ‘i’}, optional
See notes in sigma, above
w : ndarray
Array of k eigenvalues.
v : ndarray
An array of k eigenvectors. v[:, i] is the eigenvector corresponding to the eigenvalue w[i].
ArpackNoConvergence
When the requested convergence is not obtained. The currently converged eigenvalues and eigenvectors can be found as eigenvalues and eigenvectors attributes of the exception object.

eigsh : eigenvalues and eigenvectors for symmetric matrix A svds : singular value decomposition for a matrix A

This function is a wrapper to the ARPACK [1]_ SNEUPD, DNEUPD, CNEUPD, ZNEUPD, functions which use the Implicitly Restarted Arnoldi Method to find the eigenvalues and eigenvectors [2]_.

[1]ARPACK Software, http://www.caam.rice.edu/software/ARPACK/
[2]R. B. Lehoucq, D. C. Sorensen, and C. Yang, ARPACK USERS GUIDE: Solution of Large Scale Eigenvalue Problems by Implicitly Restarted Arnoldi Methods. SIAM, Philadelphia, PA, 1998.

Find 6 eigenvectors of the identity matrix:

>>> import scipy.sparse as sparse
>>> id = np.eye(13)
>>> vals, vecs = sparse.linalg.eigs(id, k=6)
>>> vals
array([ 1.+0.j,  1.+0.j,  1.+0.j,  1.+0.j,  1.+0.j,  1.+0.j])
>>> vecs.shape
(13, 6)
eigsh(A, k=6, M=None, sigma=None, which="LM", v0=None, ncv=None, maxiter=None, tol=0, return_eigenvectors=True, Minv=None, OPinv=None, mode="normal")

Find k eigenvalues and eigenvectors of the real symmetric square matrix or complex hermitian matrix A.

Solves A * x[i] = w[i] * x[i], the standard eigenvalue problem for w[i] eigenvalues with corresponding eigenvectors x[i].

If M is specified, solves A * x[i] = w[i] * M * x[i], the generalized eigenvalue problem for w[i] eigenvalues with corresponding eigenvectors x[i]

A : An N x N matrix, array, sparse matrix, or LinearOperator representing
the operation A * x, where A is a real symmetric matrix For buckling mode (see below) A must additionally be positive-definite
k : int, optional
The number of eigenvalues and eigenvectors desired. k must be smaller than N. It is not possible to compute all eigenvectors of a matrix.
w : array
Array of k eigenvalues
v : array
An array representing the k eigenvectors. The column v[:, i] is the eigenvector corresponding to the eigenvalue w[i].
M : An N x N matrix, array, sparse matrix, or linear operator representing

the operation M * x for the generalized eigenvalue problem

A * x = w * M * x.

M must represent a real, symmetric matrix if A is real, and must represent a complex, hermitian matrix if A is complex. For best results, the data type of M should be the same as that of A. Additionally:

If sigma is None, M is symmetric positive definite

If sigma is specified, M is symmetric positive semi-definite

In buckling mode, M is symmetric indefinite.

If sigma is None, eigsh requires an operator to compute the solution of the linear equation M * x = b. This is done internally via a (sparse) LU decomposition for an explicit matrix M, or via an iterative solver for a general linear operator. Alternatively, the user can supply the matrix or operator Minv, which gives x = Minv * b = M^-1 * b.

sigma : real

Find eigenvalues near sigma using shift-invert mode. This requires an operator to compute the solution of the linear system [A - sigma * M] x = b, where M is the identity matrix if unspecified. This is computed internally via a (sparse) LU decomposition for explicit matrices A & M, or via an iterative solver if either A or M is a general linear operator. Alternatively, the user can supply the matrix or operator OPinv, which gives x = OPinv * b = [A - sigma * M]^-1 * b. Note that when sigma is specified, the keyword ‘which’ refers to the shifted eigenvalues w'[i] where:

if mode == ‘normal’, w'[i] = 1 / (w[i] - sigma).

if mode == ‘cayley’, w'[i] = (w[i] + sigma) / (w[i] - sigma).

if mode == ‘buckling’, w'[i] = w[i] / (w[i] - sigma).

(see further discussion in ‘mode’ below)

v0 : ndarray, optional
Starting vector for iteration. Default: random
ncv : int, optional
The number of Lanczos vectors generated ncv must be greater than k and smaller than n; it is recommended that ncv > 2*k. Default: min(n, max(2*k + 1, 20))
which : str [‘LM’ | ‘SM’ | ‘LA’ | ‘SA’ | ‘BE’]

If A is a complex hermitian matrix, ‘BE’ is invalid. Which k eigenvectors and eigenvalues to find:

‘LM’ : Largest (in magnitude) eigenvalues

‘SM’ : Smallest (in magnitude) eigenvalues

‘LA’ : Largest (algebraic) eigenvalues

‘SA’ : Smallest (algebraic) eigenvalues

‘BE’ : Half (k/2) from each end of the spectrum

When k is odd, return one more (k/2+1) from the high end. When sigma != None, ‘which’ refers to the shifted eigenvalues w'[i] (see discussion in ‘sigma’, above). ARPACK is generally better at finding large values than small values. If small eigenvalues are desired, consider using shift-invert mode for better performance.

maxiter : int, optional
Maximum number of Arnoldi update iterations allowed Default: n*10
tol : float
Relative accuracy for eigenvalues (stopping criterion). The default value of 0 implies machine precision.
Minv : N x N matrix, array, sparse matrix, or LinearOperator
See notes in M, above
OPinv : N x N matrix, array, sparse matrix, or LinearOperator
See notes in sigma, above.
return_eigenvectors : bool
Return eigenvectors (True) in addition to eigenvalues
mode : string [‘normal’ | ‘buckling’ | ‘cayley’]

Specify strategy to use for shift-invert mode. This argument applies only for real-valued A and sigma != None. For shift-invert mode, ARPACK internally solves the eigenvalue problem OP * x'[i] = w'[i] * B * x'[i] and transforms the resulting Ritz vectors x’[i] and Ritz values w’[i] into the desired eigenvectors and eigenvalues of the problem A * x[i] = w[i] * M * x[i]. The modes are as follows:

‘normal’ :
OP = [A - sigma * M]^-1 * M, B = M, w’[i] = 1 / (w[i] - sigma)
‘buckling’ :
OP = [A - sigma * M]^-1 * A, B = A, w’[i] = w[i] / (w[i] - sigma)
‘cayley’ :
OP = [A - sigma * M]^-1 * [A + sigma * M], B = M, w’[i] = (w[i] + sigma) / (w[i] - sigma)

The choice of mode will affect which eigenvalues are selected by the keyword ‘which’, and can also impact the stability of convergence (see [2] for a discussion)

ArpackNoConvergence

When the requested convergence is not obtained.

The currently converged eigenvalues and eigenvectors can be found as eigenvalues and eigenvectors attributes of the exception object.

eigs : eigenvalues and eigenvectors for a general (nonsymmetric) matrix A svds : singular value decomposition for a matrix A

This function is a wrapper to the ARPACK [1]_ SSEUPD and DSEUPD functions which use the Implicitly Restarted Lanczos Method to find the eigenvalues and eigenvectors [2]_.

[1]ARPACK Software, http://www.caam.rice.edu/software/ARPACK/
[2]R. B. Lehoucq, D. C. Sorensen, and C. Yang, ARPACK USERS GUIDE: Solution of Large Scale Eigenvalue Problems by Implicitly Restarted Arnoldi Methods. SIAM, Philadelphia, PA, 1998.
>>> import scipy.sparse as sparse
>>> id = np.eye(13)
>>> vals, vecs = sparse.linalg.eigsh(id, k=6)
>>> vals
array([ 1.+0.j,  1.+0.j,  1.+0.j,  1.+0.j,  1.+0.j,  1.+0.j])
>>> vecs.shape
(13, 6)
_augmented_orthonormal_cols(x, k)
_augmented_orthonormal_rows(x, k)
_herm(x)
svds(A, k=6, ncv=None, tol=0, which="LM", v0=None, maxiter=None, return_singular_vectors=True)

Compute the largest k singular values/vectors for a sparse matrix.

A : {sparse matrix, LinearOperator}
Array to compute the SVD on, of shape (M, N)
k : int, optional
Number of singular values and vectors to compute. Must be 1 <= k < min(A.shape).
ncv : int, optional
The number of Lanczos vectors generated ncv must be greater than k+1 and smaller than n; it is recommended that ncv > 2*k Default: min(n, max(2*k + 1, 20))
tol : float, optional
Tolerance for singular values. Zero (default) means machine precision.
which : str, [‘LM’ | ‘SM’], optional

Which k singular values to find:

  • ‘LM’ : largest singular values
  • ‘SM’ : smallest singular values

New in version 0.12.0.

v0 : ndarray, optional

Starting vector for iteration, of length min(A.shape). Should be an (approximate) left singular vector if N > M and a right singular vector otherwise. Default: random

New in version 0.12.0.

maxiter : int, optional

Maximum number of iterations.

New in version 0.12.0.

return_singular_vectors : bool or str, optional
  • True: return singular vectors (True) in addition to singular values.

New in version 0.12.0.

  • “u”: only return the u matrix, without computing vh (if N > M).
  • “vh”: only return the vh matrix, without computing u (if N <= M).

New in version 0.16.0.

u : ndarray, shape=(M, k)
Unitary matrix having left singular vectors as columns. If return_singular_vectors is “vh”, this variable is not computed, and None is returned instead.
s : ndarray, shape=(k,)
The singular values.
vt : ndarray, shape=(k, N)
Unitary matrix having right singular vectors as rows. If return_singular_vectors is “u”, this variable is not computed, and None is returned instead.

This is a naive implementation using ARPACK as an eigensolver on A.H * A or A * A.H, depending on which one is more efficient.

>>> from scipy.sparse import csc_matrix
>>> from scipy.sparse.linalg import svds, eigs
>>> A = csc_matrix([[1, 0, 0], [5, 0, 2], [0, -1, 0], [0, 0, 3]], dtype=float)
>>> u, s, vt = svds(A, k=2)
>>> s
array([ 2.75193379,  5.6059665 ])
>>> np.sqrt(eigs(A.dot(A.T), k=2)[0]).real
array([ 5.6059665 ,  2.75193379])