scipy.sparse.linalg.onenormest

scipy.sparse.linalg.onenormest(A, t=2, itmax=5, compute_v=False, compute_w=False)

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

Parameters

Andarray or other linear operator

A linear operator that can be transposed and that can produce matrix products.

tint, 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.

itmaxint, optional

Use at most this many iterations.

compute_vbool, optional

Request a norm-maximizing linear operator input vector if True.

compute_wbool, optional

Request a norm-maximizing linear operator output vector if True.

Returns

estfloat

An underestimate of the 1-norm of the sparse matrix.

vndarray, 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.

wndarray, 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.

Notes

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.

References

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.

Examples

>>> 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