sdrelton/matrix-est-maxelts

MATLAB code to estimate the largest element of a matrix using only matrix-vector products.

For full details please see the readme file in our GitHub repository.
The functions in this repository are designed to estimate the quantity (in MATLAB notation) max(max(abs(A))), or equivalently norm(A(:),inf), where the m-by-n matrix A is not known explicitly. For example we may have A = B*C, A = expm(B), or A = inv(B), where forming A explicitly is impractical (maybe even impossible if B and C are large and sparse). However in each case forming matrix-vector products with A and its conjugate transpose may nevertheless be possible and even relatively inexpensive.

The two codes in this repository, normestm and normestm_multi, are designed to find the largest and the largest p elements of A, respectively. The code normestm_multi depends upon maxk_default. A more optimized version of this function is available, authored by Bruno Luong. This free software can be downloaded from the MATLAB File Exchange but it uses MEX files and can be difficult to install and get working. To make use of this code, should you be able to install and run it successfully, replace all occurences of maxk_default with maxk in normestm_multi.m

The quantity max(max(abs(A))) can be expressed as the mixed subordinate (1,inf)-norm of A. Underlying our algorithms is an algorithm of Boyd (1974) and Tao (1975) for estimating mixed subordinate norms. Full details of the algorithms, along with thorough numerical experiments investigating their performance, can be found in the (open access) paper

N. J. Higham and S. D. Relton, "Estimating the Largest Entries of a Matrix", MIMS EPrint 2015.116, Manchester Institute for Mathematical Sciences, The University of Manchester, UK, December 2015.

To check that the code is functioning properly you can run the testcode in MATLAB.