spectrum.h File Reference

Description

Methods for computing eigenvalues and eigenvectors of graph matrices.

For applications in spectral graph theory, we are interested in the spectrum of the Graph adjacency and Laplacian matrix spectrums.

Moreover, for each matrix, we are usually interested in the extreme eigenvalues at one end of the spectrum or the other.

As such, this module provides methods for computing the extreme eigenvalues and eigenvectors of normalised or unnormalised adjacency or Laplacian matrix of some graph.

We limit ourselves to these cases as this is the most common application in spectral Graph theory, and these matrices are 'well-behaved' for the solver algorithms. If you'd like to compute the spectrum of a more general matrix, you could consider using the Spectra C++ library directly.

Typedefs
typedef std::tuple< Eigen::VectorXd, Eigen::MatrixXd >	stag::EigenSystem

Enumerations
enum	stag::EigenSortRule { Largest , Smallest }
enum	stag::GraphMatrix { Adjacency , Laplacian , NormalisedLaplacian }

Functions
stag::EigenSystem	stag::compute_eigensystem (stag::Graph *g, stag::GraphMatrix mat, StagInt num_eigs, stag::EigenSortRule which)
Eigen::MatrixXd	stag::compute_eigenvectors (stag::Graph *g, stag::GraphMatrix mat, StagInt num_eigs, stag::EigenSortRule which)
Eigen::VectorXd	stag::compute_eigenvalues (stag::Graph *g, stag::GraphMatrix mat, StagInt num_eigs, stag::EigenSortRule which)
Eigen::VectorXd	stag::power_method (const SprsMat *mat, StagInt num_iterations, Eigen::VectorXd initial_vector)
Eigen::VectorXd	stag::power_method (const SprsMat *mat, StagInt num_iterations)
Eigen::VectorXd	stag::power_method (const SprsMat *mat, Eigen::VectorXd initial_vector)
Eigen::VectorXd	stag::power_method (const SprsMat *mat)
StagReal	stag::rayleigh_quotient (const SprsMat *mat, Eigen::VectorXd &vec)

Typedef Documentation

EigenSystem

typedef std::tuple<Eigen::VectorXd, Eigen::MatrixXd> stag::EigenSystem

A convenience type for returning eigenvalues and eigenvectors together.

Enumeration Type Documentation

EigenSortRule

enum stag::EigenSortRule

When computing eigenvectors and eigenvalues, we always compute the values at one end of the spectrum or the other.

The EigenSortRule is used to specify whether to compute the largest or smallest eigenvalues.

GraphMatrix

enum stag::GraphMatrix

When computing eigenvectors and eigenvalues, these values are used to specify which Graph matrix we are using to compute the spectrum.

Function Documentation

compute_eigensystem()

stag::EigenSystem stag::compute_eigensystem	(	stag::Graph *	g,
		stag::GraphMatrix	mat,
		StagInt	num_eigs,
		stag::EigenSortRule	which
	)

Compute the eigenvalues and eigenvectors of a graph matrix.

Computes a given number of eigenvectors at one end of the spectrum of a graph matrix.

The following example demonstrates how to compute the 3 largest eigenvectors and eigenvalues of the normalised laplacian of a cycle graph.

#include <Spectra/SymEigsSolver.h>
#include <stag/graph.h>
#include <stag/spectrum.h>
 
int main() {
  // Create a cycle graph
  stag::Graph myGraph = stag::cycle_graph(10);
 
  // Compute a few eigenvalues and eigenvectors
  StagInt k = 3;
  stag::EigenSystem eigensystem = stag::compute_eigensystem(
      myGraph, stag::GraphMatrix::NormalisedLaplacian,
      k, stag::EigenSortRule::Largest);
 
  Eigen::VectorXd eigenvalues = get<0>(eigensystem);
  Eigen::MatrixXd eigenvectors = get<1>(eigensystem);
 
  return 0;
}

Parameters

g	the graph on which to operate
mat	which graph matrix to use to compute the spectrum
num_eigs	the number of eigenvalues and eigenvectors to compute
which	a stag::EigenSortRule value indicating which eigenvectors to return

Returns

a stag::EigenSystem object containing the computed eigenvalues and eigenvectors

Exceptions

std::runtime_error

if the eigenvalue calculation does not converge

compute_eigenvectors()

Eigen::MatrixXd stag::compute_eigenvectors	(	stag::Graph *	g,
		stag::GraphMatrix	mat,
		StagInt	num_eigs,
		stag::EigenSortRule	which
	)

Compute the eigenvectors of a graph matrix.

If you would like to calculate the eigenvectors and eigenvalues together, then you should instead use stag::compute_eigensystem.

Parameters

g	the graph on which to operate
mat	which graph matrix to use to compute the spectrum
num_eigs	the number of eigenvectors to compute
which	a stag::EigenSortRule value indicating which eigenvectors to return

Returns

an Eigen::MatrixXd object containing the computed eigenvectors

Exceptions

std::runtime_error

if the eigenvector calculation does not converge

compute_eigenvalues()

Eigen::VectorXd stag::compute_eigenvalues	(	stag::Graph *	g,
		stag::GraphMatrix	mat,
		StagInt	num_eigs,
		stag::EigenSortRule	which
	)

Compute the eigenvalues of a graph matrix.

Computes a given number of eigenvalues at one end of the spectrum of a graph matrix.

If you would like to calculate the eigenvectors and eigenvalues together, then you should instead use stag::compute_eigensystem.

Parameters

g	the graph on which to operate
mat	which graph matrix to use to compute the spectrum
num_eigs	the number of eigenvalues to compute
which	a stag::EigenSortRule value indicating which eigenvalues to return

Returns

an Eigen::VectorXd object containing the computed eigenvalues

Exceptions

std::runtime_error

if the eigenvalue calculation does not converge

power_method() [1/4]

Eigen::VectorXd stag::power_method	(	const SprsMat *	mat,
		StagInt	num_iterations,
		Eigen::VectorXd	initial_vector
	)

Apply the power method to compute the dominant eigenvector of a matrix.

Given a matrix \(M\), an initial vector \(v_0\), and a number of iterations \(t\), the power method calculates the vector

\[ v_t = M^t v_0, \]

which is close to the eigenvector of \(M\) with largest eigenvalue.

The running time of the power method is \(O(t \cdot \mathrm{nnz}(M))\), where \(\mathrm{nnz}(M)\) is the number of non-zero elements in the matrix \(M\).

Parameters

mat	the matrix \(M\) on which to operate.
num_iterations	(optional) the number of iterations of the power method to apply. It this argument is omitted, \(O(\log(n))\) iterations are used which results in a vector whose Rayleigh quotient is a \((1 - \epsilon)\) approximation of the dominant eigenvalue.
initial_vector	(optional) the initial vector to use for the power iteration. If this argument is omitted, a random unit vector will be used.

Returns

the vector \(v_t\) computed by repeated multiplication with \(M\).

power_method() [2/4]

Eigen::VectorXd stag::power_method	(	const SprsMat *	mat,
		StagInt	num_iterations
	)

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

power_method() [3/4]

Eigen::VectorXd stag::power_method	(	const SprsMat *	mat,
		Eigen::VectorXd	initial_vector
	)

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

power_method() [4/4]

Eigen::VectorXd stag::power_method

(

const SprsMat *

mat

)

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

rayleigh_quotient()

StagReal stag::rayleigh_quotient	(	const SprsMat *	mat,
		Eigen::VectorXd &	vec
	)

Compute the Rayleigh quotient of the given vector and matrix.

Given a matrix \(M\), the Rayleigh quotient of vector \(v\) is

\[ R(M, v) = \frac{v^\top M v}{v^\top v}. \]

Parameters

mat	a sparse matrix \(M \in \mathbb{R}^{n \times n}\).
vec	a vector \(v \in \mathbb{R}^n\).

Returns

the Rayleigh quotient \(R(M, v)\).