1function rho = lu_normest (A, L, U)
2%LU_NORMEST estimates norm (L*U-A, 1) without forming L*U-A
3%
4% Example:
5%
6%       rho = lu_normest (A, L, U)
7%
8% which estimates the computation of the 1-norm:
9%
10%       rho = norm (A-L*U, 1)
11%
12% This code can be quite easily adapted to estimate the 1-norm of any
13% matrix E, where E itself is dense or not explicitly represented, but the
14% computation of E (and E') times a vector is easy.  In this case, our matrix
15% of interest is:
16%
17%       E = A-L*U
18%
19% That is, L*U is the LU factorization of A, where A, L and U
20% are sparse.  This code works for dense matrices A and L too,
21% but it would not be needed in that case, since E is easy to compute
22% explicitly.  For sparse A, L, and U, computing E explicitly would be quite
23% expensive, and thus normest (A-L*U) would be prohibitive.
24%
25% For a detailed description, see Davis, T. A. and Hager, W. W.,
26% Modifying a sparse Cholesky factorization, SIAM J. Matrix Analysis and
27% Applications, 1999, vol. 20, no. 3, 606-627.
28%
29% See also normest
30
31% The three places that the matrix-vector multiply E*x is used are highlighted.
32% Note that E is never formed explicity.
33
34% Copyright 1995-2009 by William W. Hager and Timothy A. Davis
35
36[m n] = size (A) ;
37
38if (m ~= n)
39    % pad A, L, and U with zeros so that they are all square
40    if (m < n)
41        U = [ U ; (sparse (n-m,n)) ] ;
42        L = [ L , (sparse (m,n-m)) ; (sparse (n-m,n)) ] ;
43        A = [ A ; (sparse (n-m,n)) ] ;
44    else
45        U = [ U , (sparse (n,m-n)) ; (sparse (m-n,m)) ] ;
46        L = [ L , (sparse (m,m-n)) ] ;
47        A = [ A , (sparse (m,m-n)) ] ;
48    end
49end
50
51[m n] = size (A) ;	    %#ok
52
53notvisited = ones (m, 1) ;  % nonvisited(j) is zero if j is visited, 1 otherwise
54rho = 0 ;    % the global rho
55
56for trial = 1:3 % {
57
58   x = notvisited ./ sum (notvisited) ;
59   rho1 = 0 ;    % the current rho for this trial
60
61   %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
62   %%% COMPUTE Ex1 = E*x EFFICIENTLY: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
63   %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
64   Ex1 = (A*x) - L*(U*x) ;
65   %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
66
67   rho2 = norm (Ex1, 1) ;
68
69   while rho2 > rho1 % {
70
71        rho1 = rho2 ;
72        y = 2*(Ex1 >= 0) - 1 ;
73
74        %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
75        %%% COMPUTE z = E'*y EFFICIENTLY: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
76        %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
77        z = (A'*y) - U'*(L'*y) ;
78        %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
79
80        [zj, j] = max (abs (z .* notvisited)) ;
81        j = j (1) ;
82        if (abs (z (j)) > z'*x) % {
83            x = zeros (m, 1) ;
84            x (j) = 1 ;
85            notvisited (j) = 0 ;
86        else % } {
87            break ;
88        end % }
89
90        %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
91        %%% COMPUTE Ex1 = E*x EFFICIENTLY: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
92        %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
93        Ex1 = (A*x) - L*(U*x) ;
94        %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
95
96        rho2 = norm (Ex1, 1) ;
97
98    end % }
99
100    rho = max (rho, rho1) ;
101
102end % }
103