# `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 .

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

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