1function test12 (nmat) 2%TEST12 test etree2 and compare with etree 3% Example: 4% test12(nmat) 5% See also cholmod_test 6 7% Copyright 2007, Timothy A. Davis, http://www.suitesparse.com 8 9fprintf ('=================================================================\n'); 10fprintf ('test12: test etree2 and compare with etree\n') ; 11 12index = ssget ; 13 14% only test matrices with nrows = 109000 or less. large ones nearly always 15% cause a MATLAB segfault. 16% f = find (index.nrows < 109000) ; 17f = 1:length (index.nrows) ; 18 19% sort by row dimension 20[ignore i] = sort (index.nrows (f)) ; 21f = f (i) ; 22 23if (nargin > 0) 24 nmat = max (0,nmat) ; 25 nmat = min (nmat, length (f)) ; 26 f = f (1:nmat) ; 27end 28 29% MATLAB 7.0 (R14, sp2, linux) etree gives a segfault for these matrices: 30s_skip = [ 803 374 1287 1311 1308 957 958 1257 955 761 1282 1230 1256 ... 31 924 1302 537 820 821 822 1258 ... 32 844 845 1238 804 939 1270 1305 1208 1209 290 879 928 1307 1244 ... 33 1275 1276 1296 885 1269 959 542 1290 ] ; 34 35sym_skip = s_skip ; 36 37p_sym_skip = 1296 ; 38p_symt_skip = 1296 ; 39 40symt_skip= [ s_skip 592 593 809 ] ; 41 42rowcol_skip = [ 646 ... 43 1224 803 588 589 374 1287 562 563 801 1311 1246 951 1308 950 ... 44 957 958 800 1257 564 565 955 761 1282 590 591 1230 1256 952 566 ... 45 567 924 1302 1293 1294 537 820 821 822 1306 849 1258 592 593 ... 46 1225 844 845 1226 1238 1227 804 939 1270 752 753 1305 809 1228 ... 47 1208 1209 1291 1292 1300 856 1229 290 879 928 1307 857 1244 ... 48 1275 1276 1296 885 858 859 1269 1263 959 542 1290 ] ; 49 50col_skip = [ rowcol_skip 647 612 610 648 799 651 652 750 751 640 ] ; 51 52row_skip= [ rowcol_skip 903 373 ] ; 53 54% f = f (find (f == 1290) : end) ; 55 56fprintf ('Matrices to test: %d\n', length (f)) ; 57 58 59for i = f 60 61 % try 62 63 Problem = ssget (i) ; 64 A = spones (Problem.A) ; 65 [m n] = size (A) ; 66 fprintf ('\n%4d: %-20s nrow: %6d ncol: %6d nnz: %10d\n', ... 67 i, Problem.name, m, n, nnz(A)) ; 68 69 % if (max (m,n) < 500) 70 % A = full (A) ; 71 % end 72 73 % warmup, for accurate timing 74 etree (sparse (1)) ; 75 etree2 (sparse (1)) ; 76 amd2 (sparse (1)) ; 77 78 % test column etree 79 skip = any (i == col_skip) | m > 109000 ; %#ok 80 if (~skip) 81 tic ; 82 [parent post] = etree (A, 'col') ; 83 t1 = toc ; 84 else 85 t1 = Inf ; 86 end 87 88 tic ; 89 [my_parent my_post] = etree2 (A, 'col') ; 90 t2 = toc ; 91 92 if (~skip) 93 if (any (parent ~= my_parent)) 94 error ('parent invalid!') ; 95 end 96 end 97 fprintf ('etree(A,''col''): %8.4f %8.4f speedup %8.2f ',... 98 t1, t2, t1/t2); 99 if (~skip) 100 if (any (post ~= my_post)) 101 fprintf ('postorder differs') ; 102 end 103 end 104 fprintf ('\n') ; 105 106 % test row etree 107 skip = any (i == row_skip) | m > 109000 ; %#ok 108 if (~skip) 109 tic ; 110 [parent post] = etree (A', 'col') ; 111 t1 = toc ; 112 else 113 t1 = Inf ; 114 end 115 116 tic ; 117 [my_parent my_post] = etree2 (A, 'row') ; 118 t2 = toc ; 119 120 if (~skip) 121 if (any (parent ~= my_parent)) 122 error ('parent invalid!') ; 123 end 124 end 125 fprintf ('etree(A,''row''): %8.4f %8.4f speedup %8.2f ',... 126 t1, t2, t1/t2); 127 if (~skip) 128 if (any (post ~= my_post)) 129 fprintf ('postorder differs') ; 130 end 131 end 132 fprintf ('\n') ; 133 134 135 136 if (m == n) 137 138 for trial = 1:2 139 140 if (trial == 1) 141 skip1 = any (i == sym_skip) | m > 109000 ; %#ok 142 skip2 = any (i == symt_skip) | m > 109000 ; %#ok 143 else 144 skip1 = any (i == p_sym_skip) | m > 109000 ; %#ok 145 skip2 = any (i == p_symt_skip) | m > 109000 ; %#ok 146 fprintf ('after amd:\n') ; 147 p = amd2 (A) ; % use AMD from SuiteSparse 148 A = A (p,p) ; 149 end 150 151 % test symmetric etree, using triu(A) 152 if (~skip1) 153 tic ; 154 [parent post] = etree (A) ; 155 t1 = toc ; 156 else 157 t1 = Inf ; 158 end 159 160 tic ; 161 [my_parent my_post] = etree2 (A) ; 162 t2 = toc ; 163 164 if (~skip1) 165 if (any (parent ~= my_parent)) 166 error ('parent invalid!') ; 167 end 168 end 169 fprintf ('etree(A): %8.4f %8.4f speedup %8.2f ',... 170 t1, t2, t1/t2); 171 if (~skip1) 172 if (any (post ~= my_post)) 173 fprintf ('postorder differs') ; 174 end 175 end 176 fprintf ('\n') ; 177 178 % test symmetric etree, using tril(A) 179 if (~skip2) 180 tic ; 181 [parent post] = etree (A') ; 182 t1 = toc ; 183 else 184 t1 = Inf ; 185 end 186 187 tic ; 188 [my_parent my_post] = etree2 (A, 'lo') ; 189 t2 = toc ; 190 191 if (~skip2) 192 if (any (parent ~= my_parent)) 193 error ('parent invalid!') ; 194 end 195 end 196 fprintf('etree(A''): %8.4f %8.4f speedup %8.2f ',... 197 t1, t2, t1/t2); 198 if (~skip2) 199 if (any (post ~= my_post)) 200 fprintf ('postorder differs') ; 201 end 202 end 203 fprintf ('\n') ; 204 205 end 206 207 end 208 209 % catch 210 % fprintf ('%d: failed\n', i) ; 211 % end 212end 213 214fprintf ('test12 passed\n') ; 215