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