condest: Compute Approximate CONDition number and 1-Norm of (Large) Matrices

Description

Estimate, i.e. compute approximately the CONDition number of a (potentially large, often sparse) matrix A. It works by apply a fast approximation of the 1-norm, norm(A,"1"), through onenormest(.).

Usage

condest(A, t = min(n, 5), normA = norm(A, "1"),
        silent = FALSE, quiet = TRUE)
onenormest(A, t = min(n, 5), A.x, At.x, n,
           silent = FALSE, quiet = silent,
           iter.max = 10, eps = 4 * .Machine$double.eps)

Arguments

a square matrix, optional for onenormest(), where instead of A, A.x and At.x can be specified, see there.

number of columns to use in the iterations.

normA

number; (an estimate of) the 1-norm of A, by default norm(A, "1"); may be replaced by an estimate.

silent

logical indicating if warning and (by default) convergence messages should be displayed.

quiet

logical indicating if convergence messages should be displayed.

A.x, At.x

when A is missing, these two must be given as functions which compute A %% x, or t(A) %% x, respectively.

== nrow(A), only needed when A is not specified.

iter.max

maximal number of iterations for the 1-norm estimator.

eps

the relaive change that is deemed irrelevant.

Value

Both functions return a list; onenormest() with components,
esta number $> 0$, the estimated norm(A, "1").
vthe maximal $A X$ column.
The function condest() returns a list with components,
esta number $> 0$, the estimated condition number $\hat\kappa$; when $r :=$rcond(A), $1/\hat\kappa \approx r$.
vinteger vector length n, with an 1 at the index j with maximal column A[,j] in $A$.
wnumeric vector, the largest $A x$ found.
iterthe number of iterations used.

References

Nicholas J. Higham and Françoise Tisseur (2000). A Block Algorithm for Matrix 1-Norm Estimation, with an Application to 1-Norm Pseudospectra. SIAM J. Matrix Anal. Appl. 21, 4, 1185--1201. http://dx.doi.org/10.1137/S0895479899356080 William W. Hager (1984). Condition Estimates. SIAM J. Sci. Stat. Comput. 5, 311--316.

Examples

Run this code

data(KNex)
mtm <- with(KNex, crossprod(mm))
system.time(ce <- condest(mtm))
## reciprocal
1 / ce$est
system.time(rc <- rcond(mtm)) # takes ca  3 x  longer
rc
all.equal(rc, 1/ce$est) # TRUE -- the approxmation was good