sparse.linalg._onenormest

Sparse block 1-norm estimator.

Module Contents

Functions

onenormest(A,t=2,itmax=5,compute_v=False,compute_w=False) Compute a lower bound of the 1-norm of a sparse matrix.
_blocked_elementwise(func) Decorator for an elementwise function, to apply it blockwise along
sign_round_up(X) This should do the right thing for both real and complex matrices.
_max_abs_axis1(X)
_sum_abs_axis0(X)
elementary_vector(n,i)
vectors_are_parallel(v,w)
every_col_of_X_is_parallel_to_a_col_of_Y(X,Y)
column_needs_resampling(i,X,Y=None)
resample_column(i,X)
less_than_or_close(a,b)
_algorithm_2_2(A,AT,t) This is Algorithm 2.2.
_onenormest_core(A,AT,t,itmax) Compute a lower bound of the 1-norm of a sparse matrix.
onenormest(A, t=2, itmax=5, compute_v=False, compute_w=False)

Compute a lower bound of the 1-norm of a sparse matrix.

A : ndarray or other linear operator
A linear operator that can be transposed and that can produce matrix products.
t : int, optional
A positive parameter controlling the tradeoff between accuracy versus time and memory usage. Larger values take longer and use more memory but give more accurate output.
itmax : int, optional
Use at most this many iterations.
compute_v : bool, optional
Request a norm-maximizing linear operator input vector if True.
compute_w : bool, optional
Request a norm-maximizing linear operator output vector if True.
est : float
An underestimate of the 1-norm of the sparse matrix.
v : ndarray, optional
The vector such that ||Av||_1 == est*||v||_1. It can be thought of as an input to the linear operator that gives an output with particularly large norm.
w : ndarray, optional
The vector Av which has relatively large 1-norm. It can be thought of as an output of the linear operator that is relatively large in norm compared to the input.

This is algorithm 2.4 of [1].

In [2] it is described as follows. “This algorithm typically requires the evaluation of about 4t matrix-vector products and almost invariably produces a norm estimate (which is, in fact, a lower bound on the norm) correct to within a factor 3.”

New in version 0.13.0.

[1]Nicholas J. Higham and Francoise Tisseur (2000), “A Block Algorithm for Matrix 1-Norm Estimation, with an Application to 1-Norm Pseudospectra.” SIAM J. Matrix Anal. Appl. Vol. 21, No. 4, pp. 1185-1201.
[2]Awad H. Al-Mohy and Nicholas J. Higham (2009), “A new scaling and squaring algorithm for the matrix exponential.” SIAM J. Matrix Anal. Appl. Vol. 31, No. 3, pp. 970-989.
>>> from scipy.sparse import csc_matrix
>>> from scipy.sparse.linalg import onenormest
>>> A = csc_matrix([[1., 0., 0.], [5., 8., 2.], [0., -1., 0.]], dtype=float)
>>> A.todense()
matrix([[ 1.,  0.,  0.],
        [ 5.,  8.,  2.],
        [ 0., -1.,  0.]])
>>> onenormest(A)
9.0
>>> np.linalg.norm(A.todense(), ord=1)
9.0
_blocked_elementwise(func)

Decorator for an elementwise function, to apply it blockwise along first dimension, to avoid excessive memory usage in temporaries.

sign_round_up(X)

This should do the right thing for both real and complex matrices.

From Higham and Tisseur: “Everything in this section remains valid for complex matrices provided that sign(A) is redefined as the matrix (aij / |aij|) (and sign(0) = 1) transposes are replaced by conjugate transposes.”

_max_abs_axis1(X)
_sum_abs_axis0(X)
elementary_vector(n, i)
vectors_are_parallel(v, w)
every_col_of_X_is_parallel_to_a_col_of_Y(X, Y)
column_needs_resampling(i, X, Y=None)
resample_column(i, X)
less_than_or_close(a, b)
_algorithm_2_2(A, AT, t)

This is Algorithm 2.2.

A : ndarray or other linear operator
A linear operator that can produce matrix products.
AT : ndarray or other linear operator
The transpose of A.
t : int, optional
A positive parameter controlling the tradeoff between accuracy versus time and memory usage.
g : sequence
A non-negative decreasing vector such that g[j] is a lower bound for the 1-norm of the column of A of jth largest 1-norm. The first entry of this vector is therefore a lower bound on the 1-norm of the linear operator A. This sequence has length t.
ind : sequence
The ith entry of ind is the index of the column A whose 1-norm is given by g[i]. This sequence of indices has length t, and its entries are chosen from range(n), possibly with repetition, where n is the order of the operator A.

This algorithm is mainly for testing. It uses the ‘ind’ array in a way that is similar to its usage in algorithm 2.4. This algorithm 2.2 may be easier to test, so it gives a chance of uncovering bugs related to indexing which could have propagated less noticeably to algorithm 2.4.

_onenormest_core(A, AT, t, itmax)

Compute a lower bound of the 1-norm of a sparse matrix.

A : ndarray or other linear operator
A linear operator that can produce matrix products.
AT : ndarray or other linear operator
The transpose of A.
t : int, optional
A positive parameter controlling the tradeoff between accuracy versus time and memory usage.
itmax : int, optional
Use at most this many iterations.
est : float
An underestimate of the 1-norm of the sparse matrix.
v : ndarray, optional
The vector such that ||Av||_1 == est*||v||_1. It can be thought of as an input to the linear operator that gives an output with particularly large norm.
w : ndarray, optional
The vector Av which has relatively large 1-norm. It can be thought of as an output of the linear operator that is relatively large in norm compared to the input.
nmults : int, optional
The number of matrix products that were computed.
nresamples : int, optional
The number of times a parallel column was observed, necessitating a re-randomization of the column.

This is algorithm 2.4.