MUQ  0.4.3
Public Member Functions | List of all members
muq::Modeling::StochasticEigenSolver Class Reference

Two-pass stochastic algorithm for computing generalized eigenvalues from matrix products. More...

#include <StochasticEigenSolver.h>

Inheritance diagram for muq::Modeling::StochasticEigenSolver:
[legend]

Detailed Description

Two-pass stochastic algorithm for computing generalized eigenvalues from matrix products.

This class implements the two-pass stochastic algorithm outlined in [Saibaba et al., 2010] and [Villa et al., 2019]. While the standard two-pass algorithm computes a fixed number of eigenvalues and eigenvectors $r$, this implementation will continue to add new samples and recompute the decomposition until the computed eigenvalues satisfy one of three stopping criteria:

  1. The number of computed eigenvalues is greater than some threshold "NumEigs"
  2. The smallest eigenvalue is smaller than some fraction 'RelativeTolerance' of the maximum eigenvalue.
  3. The smallesst eigenvalues is smaller than some absolute tolerance 'AbsoluteTolerance'.

The values of these stopping criteria can be passed to the constructor of this class in a boost property_tree or directly set as arguments.

REFERENCES:

  • Saibaba, Kitanidis, Lee, (2010) "Randomized algorithms for Generalized Hermitian Eigenvalue Problems with application to computing Karhunen-Loeve expansion." NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS
  • Villa, Petra, Ghattas, (2019) "hIPPYlib: AN EXTENSIBLE SOFTWARE FRAMEWORK FORLARGE-SCALE INVERSE PROBLEMS GOVERNED BY PDES;PART I: DETERMINISTIC INVERSION AND LINEARIZEDBAYESIAN INFERENCE." ACM TOMS 2019

Definition at line 28 of file StochasticEigenSolver.h.

Public Member Functions

 StochasticEigenSolver (int numEigsIn, double eigRelTolIn=0.0, double eigAbsTolIn=0.0, int expectedRankIn=-1, int samplingFactorIn=-1, int blockSize=10, int verbosityIn=0)
 
 StochasticEigenSolver (boost::property_tree::ptree const &options)
 
virtual StochasticEigenSolver & compute (std::shared_ptr< LinearOperator > const &A, std::shared_ptr< LinearOperator > B=nullptr, std::shared_ptr< LinearOperator > Binv=nullptr)
 
- Public Member Functions inherited from muq::Modeling::GeneralizedEigenSolver
virtual ~GeneralizedEigenSolver ()=default
 
Eigen::VectorXd const & eigenvalues () const
 
Eigen::MatrixXd const & eigenvectors () const
 

Constructor & Destructor Documentation

◆ StochasticEigenSolver() [1/2]

StochasticEigenSolver::StochasticEigenSolver ( int  numEigsIn,
double  eigRelTolIn = 0.0,
double  eigAbsTolIn = 0.0,
int  expectedRankIn = -1,
int  samplingFactorIn = -1,
int  blockSize = 10,
int  verbosityIn = 0 
)

Definition at line 9 of file StochasticEigenSolver.cpp.

References eigRelTol.

◆ StochasticEigenSolver() [2/2]

StochasticEigenSolver::StochasticEigenSolver ( boost::property_tree::ptree const &  options)

Configuration Parameters:

Parameter Key Type Default Value Description
"NumEigs" integer - The maximum number of eigenvalues to compute. Used as stopping criteria.
"RelativeTolerance" double 0.0 Fraction of the largest eigenvalue used as stopping criteria.
"AbsoluteTolerance" double 0.0 Value of smallest eigenvalue to compute. Used as stopping criteria.
"ExpectedRank" integer 0.1*dim The expected number of eigenvalues that are larger than the the tolerances. This is used to decide on the initial number of samples to compute.
"OversamplingFactor" integer 0.5*expected rank When computing a rank $r$ eigenvalue decomposition, $r+l$ matvecs are used, where $l$ is the oversampling factor.
"BlockSize" integer 10 The number of new random matvecs to compute when the current eigenvalues do not satisfy the stopping criteria.
"Verbosity" integer 0 Specifies how much is printed to the screen. Valid values are 0 (print nothing), 1, 2, or 3

Definition at line 26 of file StochasticEigenSolver.cpp.

Member Function Documentation

◆ CholeskyQR()

std::pair< Eigen::MatrixXd, Eigen::MatrixXd > StochasticEigenSolver::CholeskyQR ( Eigen::MatrixXd const &  Y,
std::shared_ptr< LinearOperator > const &  B 
) const
private

Implements the PreCholQR algorithm of [Villa et al., 2019], which computes a QR decompsotion of the matrix \(Y\) such that the columns of \(Q\) are B-orthogonal, i.e., \(Q^T B Q=I\).

Definition at line 160 of file StochasticEigenSolver.cpp.

References muq::Modeling::GeneralizedEigenSolver::B.

Referenced by compute().

◆ compute()

StochasticEigenSolver & StochasticEigenSolver::compute ( std::shared_ptr< LinearOperator > const &  A,
std::shared_ptr< LinearOperator >  B = nullptr,
std::shared_ptr< LinearOperator >  Binv = nullptr 
)
virtual

Runs the two pass algorithm to compute the (generalized) eigenvalues and eigenvectors of the matrix \(A\).

Definition at line 36 of file StochasticEigenSolver.cpp.

References muq::Modeling::GeneralizedEigenSolver::A, muq::Modeling::GeneralizedEigenSolver::B, blockSize, CholeskyQR(), eigAbsTol, eigRelTol, muq::Modeling::GeneralizedEigenSolver::eigVals, muq::Modeling::GeneralizedEigenSolver::eigVecs, expectedRank, muq::Modeling::GeneralizedEigenSolver::GetSortSwaps(), numEigs, samplingFactor, muq::Modeling::GeneralizedEigenSolver::SortCols(), muq::Modeling::GeneralizedEigenSolver::SortVec(), and verbosity.

Referenced by muq::SamplingAlgorithms::DILIKernel::ComputeLocalLIS(), main(), and muq::SamplingAlgorithms::DILIKernel::UpdateLIS().

Member Data Documentation

◆ blockSize

int muq::Modeling::StochasticEigenSolver::blockSize
private

Definition at line 75 of file StochasticEigenSolver.h.

Referenced by compute().

◆ eigAbsTol

double muq::Modeling::StochasticEigenSolver::eigAbsTol
private

Definition at line 72 of file StochasticEigenSolver.h.

Referenced by compute().

◆ eigRelTol

double muq::Modeling::StochasticEigenSolver::eigRelTol
private

Definition at line 71 of file StochasticEigenSolver.h.

Referenced by compute(), and StochasticEigenSolver().

◆ expectedRank

int muq::Modeling::StochasticEigenSolver::expectedRank
private

Definition at line 73 of file StochasticEigenSolver.h.

Referenced by compute().

◆ numEigs

int muq::Modeling::StochasticEigenSolver::numEigs
private

Definition at line 70 of file StochasticEigenSolver.h.

Referenced by compute().

◆ samplingFactor

int muq::Modeling::StochasticEigenSolver::samplingFactor
private

Definition at line 74 of file StochasticEigenSolver.h.

Referenced by compute().

◆ verbosity

int muq::Modeling::StochasticEigenSolver::verbosity
private

Definition at line 76 of file StochasticEigenSolver.h.

Referenced by compute().

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