Navigation

Operators and Keywords

Function List:

C++ API

: nest = normest1 (A)
: nest = normest1 (A, t)
: nest = normest1 (A, t, x0)
: nest = normest1 (Afun, t, x0, p1, p2, …)
: [nest, v] = normest1 (A, …)
: [nest, v, w] = normest1 (A, …)
: [nest, v, w, iter] = normest1 (A, …)

Estimate the 1-norm of the matrix A using a block algorithm.

normest1 is best for large sparse matrices where only an estimate of the norm is required. For small to medium sized matrices, consider using norm (A, 1). In addition, normest1 can be used for the estimate of the 1-norm of a linear operator A when matrix-vector products A * x and A' * x can be cheaply computed. In this case, instead of the matrix A, a function Afun (flag, x) is used; it must return:

  • the dimension n of A, if flag is "dim"
  • true if A is a real operator, if flag is "real"
  • the result A * x, if flag is "notransp"
  • the result A' * x, if flag is "transp"

A typical case is A defined by b ^ m, in which the result A * x can be computed without even forming explicitly b ^ m by: 

y = x;
for i = 1:m
  y = b * y;
endfor

The parameters p1, p2, … are arguments of Afun (flag, x, p1, p2, …).

The default value for t is 2. The algorithm requires matrix-matrix products with sizes n x n and n x t.

The initial matrix x0 should have columns of unit 1-norm. The default initial matrix x0 has the first column ones (n, 1) / n and, if t > 1, the remaining columns with random elements -1 / n, 1 / n, divided by n.

On output, nest is the desired estimate, v and w are vectors such that w = A * v, with norm (w, 1) = c * norm (v, 1). iter contains in iter(1) the number of iterations (the maximum is hardcoded to 5) and in iter(2) the total number of products A * x or A' * x performed by the algorithm.

Algorithm Note: normest1 uses random numbers during evaluation. Therefore, if consistent results are required, the "state" of the random generator should be fixed before invoking normest1.

Reference: N. J. Higham and F. Tisseur, A block algorithm for matrix 1-norm estimation, with and application to 1-norm pseudospectra, SIAM J. Matrix Anal. Appl., pp. 1185–1201, Vol 21, No. 4, 2000.

See also: normest, norm, cond, condest.

Package: octave