If matrix A is given explicitly, i.e. by its elements, its 1-norm can be calculated by definition as the maximum column sums of modules. Sometimes it is required to estimate the norm of the matrix which is given implicitly, i.e. the matrix elements are not given, but multiplication by a vector is avalilable.

Such a problem can occur when finding the norm of the matrix which is given by its LU decomposition A = LU. Finding all the matrix elements requires O(N ³) operations whereas multiplication by a vector only requires O(N ²). Another situation when this problem can occur is when evaluating the norm of an inverse matrix: finding all the elements of matrix A ^-1 requires O(N ³) operations whereas multiplication (i.e. solving a system of linear equations Ay=x) requires only O(N ²) operations if we know the LU decomposition of the matrix.

Algorithm's principle of operation

The idea behind the iteration algorithm is simple: an arbitrary starting vector is taken and multiplied by matrix A several times.

If Ax₀  ≠ 0 algorithm allows to estimate the lower boundary of the norm of the matrix A as a ratio of x_i+1  and x_i . The algorithm implemented here is more complex but its main idea is the same.

Subroutine description

This algorithm is one of the few on this site which require back communication. It needs the operation of the multiplication matrix by a vector which can't be realized by subroutine IterativeEstimate1Norm because matrix A is given implicitly.

Therefore the algorithm functioning is organized as follows: on the first run, the zero parameter KASE is passed into the subroutine. This indicates the start of the iterative algorithm. If, after returning from IterativeEstimate1Norm parameter KASE isn't equal to 0, the returned vector X should be multiplied by matrix A (if KASE=1) or by matrix A ^T (if KASE=2), and the subroutine IterativeEstimate1Norm should be called again with the same parameters. If, after returning from a subroutine parameter KASE=0, the iterative algorithm has finished its work and the subroutine has returned the matrix norm.

The subroutine parameters and functioning are described in more detail in the program comments. It makes sense to examine the subroutine DemoIterativeEstimate1Norm which demonstrates the usage of the subroutine IterativeEstimate1Norm.

Report a bug

C#

C# 1.0 source.
estnorm.csharp.zip - Matrix 1-norm estimation

C++

C++ source.
estnorm.cpp.zip - Matrix 1-norm estimation
ablas.zip - optimized basic linear algebra subroutines with SSE2 support (for C++ sources only)

C++, multiple precision arithmetic

C++ source. MPFR/GMP is used.
GMP source is available from gmplib.org. MPFR source is available from www.mpfr.org.
estnorm.mpfr.zip - Matrix 1-norm estimation
mpfr.zip - precompiled Win32 MPFR/GMP binaries

Delphi

Delphi source.
Can be compiled under FPC (in Delphi compatibility mode).
estnorm.delphi.zip - Matrix 1-norm estimation

Visual Basic 6

Visual Basic 6 source.
estnorm.vb6.zip - Matrix 1-norm estimation

Zonnon ^beta

Zonnon source.
Zonnon is an experimental language developed at ETH Zurich.
See www.zonnon.ethz.ch for more information.
estnorm.zonnon.zip - Matrix 1-norm estimation