1%NN Compare nesdis with metis, in both quality and run time
2%
3% Example:
4%   nn
5% See also cholmod_test
6
7% Copyright 2007, Timothy A. Davis, http://www.suitesparse.com
8
9index = ssget ;
10f = find (index.amd_lnz > 0) ;
11[ignore i] = sort (index.amd_lnz (f)) ;
12f = f (i) ;
13nmat = length (f) ;
14
15T1 = zeros (1,nmat) ;
16T2 = zeros (1,nmat) ;
17TM = zeros (1,nmat) ;
18Lnz1 = zeros (1,nmat) ;
19Lnz2 = zeros (1,nmat) ;
20LnzM = zeros (1,nmat) ;
21Fl1 = zeros (1,nmat) ;
22Fl2 = zeros (1,nmat) ;
23FlM = zeros (1,nmat) ;
24
25for k = 1:nmat
26
27    i = f (k) ;
28    Prob = ssget (i,index) ;
29    A = Prob.A ;
30    [m n] = size (A) ;
31
32    if (m ~= n)
33	continue ;
34    end
35
36    fprintf ('%35s: ', Prob.name) ;
37
38    if (m == n)
39	mode = 'sym' ;
40	A = A + A' ;
41	len = n ;
42    elseif (m < n)
43	mode = 'row' ;
44	len = m ;
45    else
46	mode = 'col' ;
47	len = n ;
48    end
49
50    fprintf (' %s ', mode) ;
51
52    % try nesdis using camd, and splitting connected components
53    tic
54    [p2 cparent2 cmember2] = nesdis (A, mode, [200 1]) ;
55    t2 = toc ;
56
57    % subplot (3,3,7) ; treeplot (cparent2) ;
58
59    % try nesdis using camd
60    tic
61    [p1 cparent1 cmember1] = nesdis (A, mode) ;
62    t1 = toc ;
63
64    % subplot (3,3,8) ; treeplot (cparent1) ;
65
66    % try metis
67    tic
68    pm = metis (A, mode) ;
69    tm = toc ;
70
71    if (any (sort (p1) ~= 1:len))
72	error ('p1!') ;
73    end
74
75    if (any (sort (p2) ~= 1:len))
76	error ('p2!') ;
77    end
78
79    % compare ordering quality
80
81    if (m == n)
82	c2 = symbfact2 (A (p2,p2), mode) ; fl2 = sum (c2.^2) ; c2 = sum (c2) ;
83	c1 = symbfact2 (A (p1,p1), mode) ; fl1 = sum (c1.^2) ; c1 = sum (c1) ;
84	cm = symbfact2 (A (pm,pm), mode) ; flm = sum (cm.^2) ; cm = sum (cm) ;
85    elseif (m < n)
86	c2 = symbfact2 (A (p2, :), mode) ; fl2 = sum (c2.^2) ; c2 = sum (c2) ;
87	c1 = symbfact2 (A (p1, :), mode) ; fl1 = sum (c1.^2) ; c1 = sum (c1) ;
88	cm = symbfact2 (A (pm, :), mode) ; flm = sum (cm.^2) ; cm = sum (cm) ;
89    else
90	c2 = symbfact2 (A ( :,p2), mode) ; fl2 = sum (c2.^2) ; c2 = sum (c2) ;
91	c1 = symbfact2 (A ( :,p1), mode) ; fl1 = sum (c1.^2) ; c1 = sum (c1) ;
92	cm = symbfact2 (A ( :,pm), mode) ; flm = sum (cm.^2) ; cm = sum (cm) ;
93    end
94
95    T1 (k) = t1 ;
96    T2 (k) = t2 ;
97    TM (k) = tm ;
98    Lnz1 (k) = c1 ;
99    Lnz2 (k) = c2 ;
100    LnzM (k) = cm ;
101    Fl1 (k) = fl1 ;
102    Fl2 (k) = fl2 ;
103    FlM (k) = flm ;
104    tmax = max ([max(T1 (1:k)) max(T2 (1:k)) max(TM (1:k))]) ;
105    tmin = min ([min(T1 (1:k)) min(T2 (1:k)) min(TM (1:k))]) ;
106    cmax = max ([max(Lnz1 (1:k)) max(Lnz2 (1:k)) max(LnzM (1:k))]) ;
107    flmax =max ([max(Fl1 (1:k)) max(Fl2 (1:k)) max(FlM (1:k))]) ;
108
109    fprintf (...
110	'time %8.2f %8.2f %8.2f speedup %8.2f  flop %8.2e %8.2e %8.2e ratio %8.2f\n', ...
111	t2, t1, tm, tm/t1, fl2, fl1, flm, flm/fl1) ;
112
113    if (mod (k, 20) ~= 0)
114	continue
115    end
116
117    subplot (3,3,1) ;
118    x = T1 (1:k) ./ T2 (1:k) ;
119    semilogy (1:k, x, 'o', [1 k], [1 1], 'r-') ;
120    axis tight
121    title (sprintf ('(nesdis default)/(with split) time, median: %g', ...
122	median (x))) ;
123
124    subplot (3,3,2) ;
125    x = (Lnz1 (1:k) ./ Lnz2 (1:k)) ;
126    semilogy (1:k, x, 'o', [1 k], [1 1], 'r-') ;
127    axis tight
128    title (sprintf ('(nesdis default)/(with split) lnz, median: %g', ...
129	median (x))) ;
130
131    subplot (3,3,3) ;
132    x = (Fl1 (1:k) ./ Fl2 (1:k)) ;
133    semilogy (1:k, x, 'o', [1 k], [1 1], 'r-') ;
134    axis tight
135    title (sprintf ('(nesdis default)/(with split) flops, median: %g', ...
136	median (x))) ;
137
138    subplot (3,3,4) ;
139    x = T1 (1:k) ./ TM (1:k) ;
140    semilogy (1:k, x, 'o', [1 k], [1 1], 'r-') ;
141    axis tight
142    title (sprintf ('(nesdis default)/metis time, median %g', median (x))) ;
143
144    subplot (3,3,5) ;
145    x = (Lnz1 (1:k) ./ LnzM (1:k)) ;
146    semilogy (1:k, x, 'o', [1 k], [1 1], 'r-') ;
147    axis tight
148    title (sprintf ('(nesdis default)/metis lnz, median: %g', median (x))) ;
149
150    subplot (3,3,6) ;
151    x = (Fl1 (1:k) ./ FlM (1:k)) ;
152    semilogy (1:k, x, 'o', [1 k], [1 1], 'r-') ;
153    axis tight
154    title (sprintf ('(nesdis default)/metis flops, median: %g', median (x))) ;
155
156    drawnow
157
158    % pause
159end
160