pymor.algorithms.rand_la

Module Contents

class pymor.algorithms.rand_la.RandomizedRangeFinder(A, source_product=None, range_product=None, A_adj=None, power_iterations=0, failure_tolerance=1e-15, num_testvecs=20, lambda_min=None, block_size=None, iscomplex=False)

Bases: pymor.core.base.BasicObject

Adaptive randomized range approximation of A.

This is an implementation of Algorithm 1 in [BS18].

Given the Operator A, the return value of this method is the VectorArray B with the property

\[\Vert A - P_{span(B)} A \Vert \leq tol\]

with a failure probability smaller than failure_tolerance, where the norm denotes the operator norm. The inner product of the range of A is given by range_product and the inner product of the source of A is given by source_product.

Parameters

A

The Operator A.

source_product

Inner product Operator of the source of A.

range_product

Inner product Operator of the range of A.

power_iterations

Number of power iterations.

A_adj

Adjoint Operator to use for power iterations. If None the adjoint is computed using A, source_product and range_product. Set to A for a self for a known self-adjoint operator.

failure_tolerance

Maximum failure probability.

num_testvecs

Number of test vectors.

lambda_min

The smallest eigenvalue of source_product. If None, the smallest eigenvalue is computed using scipy.

block_size

Number of basis vectors to add per iteration.

iscomplex

If True, the random vectors are chosen complex.

Methods

estimate_error
find_range	Find the range of A.

estimate_error()

find_range(basis_size=None, tol=None)

Find the range of A.

Parameters

basis_size

Maximum dimension of range approximation.

tol

Error tolerance for the algorithm.

Returns

VectorArray which contains the basis, whose span approximates the range of A.

pymor.algorithms.rand_la.adaptive_rrf(A, source_product=None, range_product=None, tol=0.0001, failure_tolerance=1e-15, num_testvecs=20, lambda_min=None, iscomplex=False)

Adaptive randomized range approximation of A.

This is an implementation of Algorithm 1 in [BS18].

Given the Operator A, the return value of this method is the VectorArray B with the property

\[\Vert A - P_{span(B)} A \Vert \leq tol\]

with a failure probability smaller than failure_tolerance, where the norm denotes the operator norm. The inner product of the range of A is given by range_product and the inner product of the source of A is given by source_product.

Parameters

A

The Operator A.

source_product

Inner product Operator of the source of A.

range_product

Inner product Operator of the range of A.

tol

Error tolerance for the algorithm.

failure_tolerance

Maximum failure probability.

num_testvecs

Number of test vectors.

lambda_min

The smallest eigenvalue of source_product. If None, the smallest eigenvalue is computed using scipy.

iscomplex

If True, the random vectors are chosen complex.

Returns

B

VectorArray which contains the basis, whose span approximates the range of A.

pymor.algorithms.rand_la.random_generalized_svd(A, source_product=None, range_product=None, modes=6, p=20, q=2)

Randomized SVD of an Operator.

Viewing A as an \(m\) by \(n\) matrix, the return value of this method is the randomized generalized singular value decomposition of A:

\[A = U \Sigma V^{-1},\]

where the inner product on the range \(\mathbb{R}^m\) is given by

\[(x, y)_S = x^TSy\]

and the inner product on the source \(\mathbb{R}^n\) is given by

\[(x, y) = x^TTy.\]

This method is based on [SHvBW21].

Parameters

A

The Operator for which the randomized SVD is to be computed.

range_product

Range product Operator \(S\) w.r.t which the randomized SVD is computed.

source_product

Source product Operator \(T\) w.r.t which the randomized SVD is computed.

modes

The first modes approximated singular values and vectors are returned.

p

If not 0, adds p columns to the randomly sampled matrix (oversampling parameter).

q

If not 0, performs q so-called power iterations to increase the relative weight of the first singular values.

Returns

U

VectorArray of approximated left singular vectors.

s

One-dimensional NumPy array of the approximated singular values.

Vh

VectorArray of the approximated right singular vectors.

pymor.algorithms.rand_la.random_ghep(A, E=None, modes=6, p=20, q=2, single_pass=False)

Approximates a few eigenvalues of a symmetric linear Operator with randomized methods.

Approximates modes eigenvalues w with corresponding eigenvectors v which solve the eigenvalue problem

\[A v_i = w_i v_i\]

or the generalized eigenvalue problem

\[A v_i = w_i E v_i\]

if E is not None.

This method is an implementation of algorithm 6 and 7 in [SLK16].

Parameters

A

The Hermitian linear Operator for which the eigenvalues are to be computed.

E

The Hermitian Operator which defines the generalized eigenvalue problem.

modes

The number of eigenvalues and eigenvectors which are to be computed.

p

If not 0, adds p columns to the randomly sampled matrix in the rrf method (oversampling parameter).

q

If not 0, performs q power iterations to increase the relative weight of the larger singular values. Ignored when single_pass is True.

single_pass

If True, computes the GHEP where only one set of matvecs Ax is required, but at the expense of lower numerical accuracy. If False, the methods require two sets of matvecs Ax.

Returns

w

A 1D NumPy array which contains the computed eigenvalues.

V

A VectorArray which contains the computed eigenvectors.

pymor.algorithms.rand_la.randomized_ghep(A, E=None, n=6, power_iterations=0, oversampling=20, single_pass=False, return_evecs=False)

Approximates a few eigenvalues of a Hermitian linear Operator with randomized methods.

Approximates modes eigenvalues w with corresponding eigenvectors v which solve the eigenvalue problem

\[A v_i = w_i v_i\]

or the generalized eigenvalue problem

\[A v_i = w_i E v_i\]

if E is not None.

This method is an implementation of algorithm 6 and 7 in [SLK16].

Parameters

A

The Hermitian linear Operator for which the eigenvalues are to be computed.

E

The Hermitian Operator which defines the generalized eigenvalue problem.

n

The number of eigenvalues and eigenvectors which are to be computed. Defaults to 6.

power_iterations

The number of power iterations to increase the relative weight of the larger singular values. Ignored when single_pass is True.

oversampling

The number of samples that are drawn in addition to the desired basis size in the randomized range approximation process.

single_pass

If True, computes the GHEP where only one set of matvecs Ax is required, but at the expense of lower numerical accuracy. If False, the methods performs two sets of matvecs Ax (default).

return_evecs

If True, the eigenvectors are computed and returned. Defaults to False.

Returns

w

A 1D NumPy array which contains the computed eigenvalues.

V

A VectorArray which contains the computed eigenvectors.

pymor.algorithms.rand_la.randomized_svd(A, n, source_product=None, range_product=None, power_iterations=0, oversampling=20)

Randomized SVD of an Operator based on [SHvBW21].

Viewing the Operator \(A\) as an \(m\) by \(n\) matrix, this methods computes and returns the randomized generalized singular value decomposition of A according [SHvBW21]:

\[A = U \Sigma V^{-1},\]

where the inner product on the range \(\mathbb{R}^m\) is given by

\[(x, y)_R = x^TRy\]

and the inner product on the source \(\mathbb{R}^n\) is given by

\[(x, y)_S = x^TSy.\]

Note that \(U\) is \(R\)-orthogonal, i.e. \(U^TRU=I\) and \(V\) is \(S\)-orthogonal, i.e. \(V^TSV=I\). In particular, V^{-1}=V^TS.

Parameters

A

The Operator for which the randomized SVD is to be computed.

n

The number of eigenvalues and eigenvectors which are to be computed.

source_product

Source product Operator \(S\) w.r.t. which the randomized SVD is computed.

range_product

Range product Operator \(R\) w.r.t. which the randomized SVD is computed.

power_iterations

The number of power iterations to increase the relative weight of the larger singular values.

oversampling

The number of samples that are drawn in addition to the desired basis size in the randomized range approximation process.

Returns

U

VectorArray containing the approximated left singular vectors.

s

One-dimensional NumPy array of the approximated singular values.

V

VectorArray containing the approximated right singular vectors.

pymor.algorithms.rand_la.rrf(A, source_product=None, range_product=None, q=2, l=8, return_rand=False, iscomplex=False)

Randomized range approximation of A.

Given the Operator A, the return value of this method is the VectorArray Q whose vectors form an approximate orthonormal basis for the range of A.

This method is based on algorithm 2 in [SHvBW21].

Parameters

A

The Operator A.

source_product

Inner product Operator of the source of A.

range_product

Inner product Operator of the range of A.

q

The number of power iterations.

l

The block size of the normalized power iterations.

return_rand

No longer available. Must be False.

iscomplex

If True, the random vectors are chosen complex.

Returns

Q

VectorArray which contains the basis, whose span approximates the range of A.