Public Member Functions | Private Types | Private Member Functions | Private Attributes | List of all members
Spectra::SymEigsShiftSolver< Scalar, SelectionRule, OpType > Class Template Reference
Eigen Solvers

#include <SymEigsShiftSolver.h>

Inheritance diagram for Spectra::SymEigsShiftSolver< Scalar, SelectionRule, OpType >:
Inheritance graph
[legend]

Public Member Functions

 SymEigsShiftSolver (OpType *op, Index nev, Index ncv, Scalar sigma)
 
- Public Member Functions inherited from Spectra::SymEigsBase< Scalar, SelectionRule, OpType, IdentityBOp >
Index compute (Index maxit=1000, Scalar tol=1e-10, int sort_rule=LARGEST_ALGE)
 
Vector eigenvalues () const
 
virtual Matrix eigenvectors (Index nvec) const
 
virtual Matrix eigenvectors () const
 
int info () const
 
void init (const Scalar *init_resid)
 
void init ()
 
Index num_iterations () const
 
Index num_operations () const
 

Private Types

typedef Eigen::Array< Scalar, Eigen::Dynamic, 1 > Array
 
typedef Eigen::Index Index
 

Private Member Functions

void sort_ritzpair (int sort_rule)
 

Private Attributes

const Scalar m_sigma
 

Additional Inherited Members

- Protected Attributes inherited from Spectra::SymEigsBase< Scalar, SelectionRule, OpType, IdentityBOp >
LanczosFac m_fac
 
const Index m_n
 
const Index m_ncv
 
const Index m_nev
 
Index m_niter
 
Index m_nmatop
 
OpType * m_op
 
Vector m_ritz_val
 

Detailed Description

template<typename Scalar = double, int SelectionRule = LARGEST_MAGN, typename OpType = DenseSymShiftSolve<double>>
class Spectra::SymEigsShiftSolver< Scalar, SelectionRule, OpType >

This class implements the eigen solver for real symmetric matrices using the shift-and-invert mode. The background information of the symmetric eigen solver is documented in the SymEigsSolver class. Here we focus on explaining the shift-and-invert mode.

The shift-and-invert mode is based on the following fact: If $\lambda$ and $x$ are a pair of eigenvalue and eigenvector of matrix $A$, such that $Ax=\lambda x$, then for any $\sigma$, we have

\[(A-\sigma I)^{-1}x=\nu x\]

where

\[\nu=\frac{1}{\lambda-\sigma}\]

which indicates that $(\nu, x)$ is an eigenpair of the matrix $(A-\sigma I)^{-1}$.

Therefore, if we pass the matrix operation $(A-\sigma I)^{-1}y$ (rather than $Ay$) to the eigen solver, then we would get the desired values of $\nu$, and $\lambda$ can also be easily obtained by noting that $\lambda=\sigma+\nu^{-1}$.

The reason why we need this type of manipulation is that the algorithm of Spectra (and also ARPACK) is good at finding eigenvalues with large magnitude, but may fail in looking for eigenvalues that are close to zero. However, if we really need them, we can set $\sigma=0$, find the largest eigenvalues of $A^{-1}$, and then transform back to $\lambda$, since in this case largest values of $\nu$ implies smallest values of $\lambda$.

To summarize, in the shift-and-invert mode, the selection rule will apply to $\nu=1/(\lambda-\sigma)$ rather than $\lambda$. So a selection rule of LARGEST_MAGN combined with shift $\sigma$ will find eigenvalues of $A$ that are closest to $\sigma$. But note that the eigenvalues() method will always return the eigenvalues in the original problem (i.e., returning $\lambda$ rather than $\nu$), and eigenvectors are the same for both the original problem and the shifted-and-inverted problem.

Template Parameters
ScalarThe element type of the matrix. Currently supported types are float, double and long double.
SelectionRuleAn enumeration value indicating the selection rule of the shifted-and-inverted eigenvalues. The full list of enumeration values can be found in Enumerations.
OpTypeThe name of the matrix operation class. Users could either use the wrapper classes such as DenseSymShiftSolve and SparseSymShiftSolve, or define their own that implements all the public member functions as in DenseSymShiftSolve.

Below is an example that illustrates the use of the shift-and-invert mode:

#include <Eigen/Core>
#include <Spectra/SymEigsShiftSolver.h>
// <Spectra/MatOp/DenseSymShiftSolve.h> is implicitly included
#include <iostream>
using namespace Spectra;
int main()
{
// A size-10 diagonal matrix with elements 1, 2, ..., 10
Eigen::MatrixXd M = Eigen::MatrixXd::Zero(10, 10);
for(int i = 0; i < M.rows(); i++)
M(i, i) = i + 1;
// Construct matrix operation object using the wrapper class
DenseSymShiftSolve<double> op(M);
// Construct eigen solver object with shift 0
// This will find eigenvalues that are closest to 0
SymEigsShiftSolver< double, LARGEST_MAGN,
DenseSymShiftSolve<double> > eigs(&op, 3, 6, 0.0);
eigs.init();
eigs.compute();
if(eigs.info() == SUCCESSFUL)
{
Eigen::VectorXd evalues = eigs.eigenvalues();
// Will get (3.0, 2.0, 1.0)
std::cout << "Eigenvalues found:\n" << evalues << std::endl;
}
return 0;
}

Also an example for user-supplied matrix shift-solve operation class:

#include <Eigen/Core>
#include <Spectra/SymEigsShiftSolver.h>
#include <iostream>
using namespace Spectra;
// M = diag(1, 2, ..., 10)
class MyDiagonalTenShiftSolve
{
private:
double sigma_;
public:
int rows() { return 10; }
int cols() { return 10; }
void set_shift(double sigma) { sigma_ = sigma; }
// y_out = inv(A - sigma * I) * x_in
// inv(A - sigma * I) = diag(1/(1-sigma), 1/(2-sigma), ...)
void perform_op(double *x_in, double *y_out)
{
for(int i = 0; i < rows(); i++)
{
y_out[i] = x_in[i] / (i + 1 - sigma_);
}
}
};
int main()
{
MyDiagonalTenShiftSolve op;
// Find three eigenvalues that are closest to 3.14
SymEigsShiftSolver<double, LARGEST_MAGN,
MyDiagonalTenShiftSolve> eigs(&op, 3, 6, 3.14);
eigs.init();
eigs.compute();
if(eigs.info() == SUCCESSFUL)
{
Eigen::VectorXd evalues = eigs.eigenvalues();
// Will get (4.0, 3.0, 2.0)
std::cout << "Eigenvalues found:\n" << evalues << std::endl;
}
return 0;
}

Definition at line 158 of file SymEigsShiftSolver.h.

Member Typedef Documentation

template<typename Scalar = double, int SelectionRule = LARGEST_MAGN, typename OpType = DenseSymShiftSolve<double>>
typedef Eigen::Array<Scalar, Eigen::Dynamic, 1> Spectra::SymEigsShiftSolver< Scalar, SelectionRule, OpType >::Array
private

Definition at line 162 of file SymEigsShiftSolver.h.

template<typename Scalar = double, int SelectionRule = LARGEST_MAGN, typename OpType = DenseSymShiftSolve<double>>
typedef Eigen::Index Spectra::SymEigsShiftSolver< Scalar, SelectionRule, OpType >::Index
private

Definition at line 161 of file SymEigsShiftSolver.h.

Constructor & Destructor Documentation

template<typename Scalar = double, int SelectionRule = LARGEST_MAGN, typename OpType = DenseSymShiftSolve<double>>
Spectra::SymEigsShiftSolver< Scalar, SelectionRule, OpType >::SymEigsShiftSolver ( OpType *  op,
Index  nev,
Index  ncv,
Scalar  sigma 
)
inline

Constructor to create a eigen solver object using the shift-and-invert mode.

Parameters
opPointer to the matrix operation object, which should implement the shift-solve operation of $A$: calculating $(A-\sigma I)^{-1}v$ for any vector $v$. Users could either create the object from the wrapper class such as DenseSymShiftSolve, or define their own that implements all the public member functions as in DenseSymShiftSolve.
nevNumber of eigenvalues requested. This should satisfy $1\le nev \le n-1$, where $n$ is the size of matrix.
ncvParameter that controls the convergence speed of the algorithm. Typically a larger ncv_ means faster convergence, but it may also result in greater memory use and more matrix operations in each iteration. This parameter must satisfy $nev < ncv \le n$, and is advised to take $ncv \ge 2\cdot nev$.
sigmaThe value of the shift.

Definition at line 193 of file SymEigsShiftSolver.h.

Member Function Documentation

template<typename Scalar = double, int SelectionRule = LARGEST_MAGN, typename OpType = DenseSymShiftSolve<double>>
void Spectra::SymEigsShiftSolver< Scalar, SelectionRule, OpType >::sort_ritzpair ( int  sort_rule)
inlineprivatevirtual

Reimplemented from Spectra::SymEigsBase< Scalar, SelectionRule, OpType, IdentityBOp >.

Definition at line 167 of file SymEigsShiftSolver.h.

Member Data Documentation

template<typename Scalar = double, int SelectionRule = LARGEST_MAGN, typename OpType = DenseSymShiftSolve<double>>
const Scalar Spectra::SymEigsShiftSolver< Scalar, SelectionRule, OpType >::m_sigma
private

Definition at line 164 of file SymEigsShiftSolver.h.

The documentation for this class was generated from the following file:

gtsam
Author(s):
autogenerated on Sat May 8 2021 02:59:21