stag.spectrum Namespace Reference

Functions
Tuple[np.ndarray, np.ndarray]	compute_eigensystem (graph.Graph g, str matrix, int num, str which)
	Compute the eigenvalues and eigenvectors of a given graph matrix.
np.ndarray	compute_eigenvalues (graph.Graph g, str matrix, int num, str which)
	Compute the eigenvalues of a specified graph matrix.
np.ndarray	compute_eigenvectors (graph.Graph g, str matrix, int num, str which)
	Compute the eigenvectors of a specified graph matrix.
np.ndarray	power_method (utility.SprsMat mat, int num_iterations=None, np.ndarray initial_vector=None)
	Apply the power method to compute the dominant eigenvector of a matrix.
float	rayleigh_quotient (utility.SprsMat mat, np.ndarray vec)
	Compute the Rayleigh quotient of the given vector and matrix.

Function Documentation

compute_eigensystem()

Tuple[np.ndarray, np.ndarray] stag.spectrum.compute_eigensystem	(	graph.Graph	g,
		str	matrix,
		int	num,
		str	which
	)

Compute the eigenvalues and eigenvectors of a given graph matrix.

The second argument controls which graph matrix to use and should be one of

• 'Laplacian',
• 'NormalisedLaplacian', or
• 'Adjacency'.

The final argument specifies which eigenvalues to compute and should be either

• 'Smallest', or
• 'Largest'.

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

import stag.graph
import stag.spectrum
 
myGraph = stag.graph.cycle_graph(10)
eigenvalues, eigenvectors = stag.spectrum.compute_eigensystem(
    myGraph, 'NormalisedLaplacian', 3, 'Largest')

Parameters

g	the graph whose spectrum you would like to compute
matrix	the name of the graph matrix on which to operate
num	the number of eigenvalues and eigenvectors to compute
which	whether to compute the smallest or largest eigenvalues

Returns

a tuple containing the computed eigenvalues and eigenvectors

compute_eigenvalues()

np.ndarray stag.spectrum.compute_eigenvalues	(	graph.Graph	g,
		str	matrix,
		int	num,
		str	which
	)

Compute the eigenvalues of a specified graph matrix.

The second argument controls which graph matrix to use and should be one of

• 'Laplacian',
• 'NormalisedLaplacian', or
• 'Adjacency'.

The final argument specifies which eigenvalues to compute and should be either

• 'Smallest', or
• 'Largest'.

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

Parameters

g	the graph whose spectrum you would like to compute
matrix	the name of the graph matrix on which to operate
num	the number of eigenvalues to compute
which	whether to compute the smallest or largest eigenvalues

Returns

a numpy array containing the computed eigenvalues

compute_eigenvectors()

np.ndarray stag.spectrum.compute_eigenvectors	(	graph.Graph	g,
		str	matrix,
		int	num,
		str	which
	)

Compute the eigenvectors of a specified graph matrix.

The second argument controls which graph matrix to use and should be one of

• 'Laplacian',
• 'NormalisedLaplacian', or
• 'Adjacency'.

The final argument specifies which eigenvectors to compute and should be either

• 'Smallest', or
• 'Largest'.

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

Parameters

g	the graph whose spectrum you would like to compute
matrix	the name of the graph matrix on which to operate
num	the number of eigenvectors to compute
which	whether to compute the vectors corresponding to the smallest or largest eigenvalues

Returns

a numpy array containing the computed eigenvectors as columns

power_method()

np.ndarray stag.spectrum.power_method	(	utility.SprsMat	mat,
		int	num_iterations = None,
		np.ndarray	initial_vector = None
	)

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\).

rayleigh_quotient()

float stag.spectrum.rayleigh_quotient	(	utility.SprsMat	mat,
		np.ndarray	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)\).