scipy.sparse.linalg.onenormest#

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

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

Added 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

>>> import numpy as np
>>> 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.toarray()
array([[ 1.,  0.,  0.],
       [ 5.,  8.,  2.],
       [ 0., -1.,  0.]])
>>> onenormest(A)
9.0
>>> np.linalg.norm(A.toarray(), ord=1)
9.0