← Back to branch summary

~logan/ubuntu/trusty/suitesparse/4.2.1-3ubuntu1

« back to all changes in this revision

Viewing changes to CHOLMOD/MATLAB/lu_normest.m

  • Committer: Bazaar Package Importer
  • Author(s): Christophe Prud'homme
  • Date: 2007-05-29 09:36:29 UTC
  • mfrom: (1.1.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20070529093629-zowquo0b7slkk6nc
Tags: 3.0.0-2
http://bugs.debian.org/426349
http://bugs.debian.org/426354
* suitesparse builds properly twice in a row
* Bug fix: "suitesparse - FTBFS: Broken build depens: libgfortran1-dev",
  thanks to Bastian Blank (Closes: #426349).
* Bug fix: "suitesparse_3.0.0-1: FTBFS: build-depends on
  libgfortran1-dev", thanks to Steve Langasek (Closes: #426354).

Show diffs side-by-side

added added

removed removed

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