1 /* ========================================================================= */ 2 /* === CAMD: approximate minimum degree ordering ========================== */ 3 /* ========================================================================= */ 4 5 /* ------------------------------------------------------------------------- */ 6 /* CAMD Version 2.4, Copyright (c) 2013 by Timothy A. Davis, Yanqing Chen, */ 7 /* Patrick R. Amestoy, and Iain S. Duff. See ../README.txt for License. */ 8 /* email: DrTimothyAldenDavis@gmail.com */ 9 /* ------------------------------------------------------------------------- */ 10 11 /* CAMD finds a symmetric ordering P of a matrix A so that the Cholesky 12 * factorization of P*A*P' has fewer nonzeros and takes less work than the 13 * Cholesky factorization of A. If A is not symmetric, then it performs its 14 * ordering on the matrix A+A'. Two sets of user-callable routines are 15 * provided, one for int integers and the other for SuiteSparse_long integers. 16 * 17 * The method is based on the approximate minimum degree algorithm, discussed 18 * in Amestoy, Davis, and Duff, "An approximate degree ordering algorithm", 19 * SIAM Journal of Matrix Analysis and Applications, vol. 17, no. 4, pp. 20 * 886-905, 1996. 21 */ 22 23 #ifndef CAMD_H 24 #define CAMD_H 25 26 /* make it easy for C++ programs to include CAMD */ 27 #ifdef __cplusplus 28 extern "C" { 29 #endif 30 31 /* get the definition of size_t: */ 32 #include <stddef.h> 33 34 #include "SuiteSparse_config.h" 35 36 int camd_order /* returns CAMD_OK, CAMD_OK_BUT_JUMBLED, 37 * CAMD_INVALID, or CAMD_OUT_OF_MEMORY */ 38 ( 39 int n, /* A is n-by-n. n must be >= 0. */ 40 const int Ap [ ], /* column pointers for A, of size n+1 */ 41 const int Ai [ ], /* row indices of A, of size nz = Ap [n] */ 42 int P [ ], /* output permutation, of size n */ 43 double Control [ ], /* input Control settings, of size CAMD_CONTROL */ 44 double Info [ ], /* output Info statistics, of size CAMD_INFO */ 45 const int C [ ] /* Constraint set of A, of size n; can be NULL */ 46 ) ; 47 48 SuiteSparse_long camd_l_order /* see above for description of arguments */ 49 ( 50 SuiteSparse_long n, 51 const SuiteSparse_long Ap [ ], 52 const SuiteSparse_long Ai [ ], 53 SuiteSparse_long P [ ], 54 double Control [ ], 55 double Info [ ], 56 const SuiteSparse_long C [ ] 57 ) ; 58 59 /* Input arguments (not modified): 60 * 61 * n: the matrix A is n-by-n. 62 * Ap: an int/SuiteSparse_long array of size n+1, containing column 63 * pointers of A. 64 * Ai: an int/SuiteSparse_long array of size nz, containing the row 65 * indices of A, where nz = Ap [n]. 66 * Control: a double array of size CAMD_CONTROL, containing control 67 * parameters. Defaults are used if Control is NULL. 68 * 69 * Output arguments (not defined on input): 70 * 71 * P: an int/SuiteSparse_long array of size n, containing the output 72 * permutation. If row i is the kth pivot row, then P [k] = i. In 73 * MATLAB notation, the reordered matrix is A (P,P). 74 * Info: a double array of size CAMD_INFO, containing statistical 75 * information. Ignored if Info is NULL. 76 * 77 * On input, the matrix A is stored in column-oriented form. The row indices 78 * of nonzero entries in column j are stored in Ai [Ap [j] ... Ap [j+1]-1]. 79 * 80 * If the row indices appear in ascending order in each column, and there 81 * are no duplicate entries, then camd_order is slightly more efficient in 82 * terms of time and memory usage. If this condition does not hold, a copy 83 * of the matrix is created (where these conditions do hold), and the copy is 84 * ordered. 85 * 86 * Row indices must be in the range 0 to 87 * n-1. Ap [0] must be zero, and thus nz = Ap [n] is the number of nonzeros 88 * in A. The array Ap is of size n+1, and the array Ai is of size nz = Ap [n]. 89 * The matrix does not need to be symmetric, and the diagonal does not need to 90 * be present (if diagonal entries are present, they are ignored except for 91 * the output statistic Info [CAMD_NZDIAG]). The arrays Ai and Ap are not 92 * modified. This form of the Ap and Ai arrays to represent the nonzero 93 * pattern of the matrix A is the same as that used internally by MATLAB. 94 * If you wish to use a more flexible input structure, please see the 95 * umfpack_*_triplet_to_col routines in the UMFPACK package, at 96 * http://www.suitesparse.com. 97 * 98 * Restrictions: n >= 0. Ap [0] = 0. Ap [j] <= Ap [j+1] for all j in the 99 * range 0 to n-1. nz = Ap [n] >= 0. Ai [0..nz-1] must be in the range 0 100 * to n-1. Finally, Ai, Ap, and P must not be NULL. If any of these 101 * restrictions are not met, CAMD returns CAMD_INVALID. 102 * 103 * CAMD returns: 104 * 105 * CAMD_OK if the matrix is valid and sufficient memory can be allocated to 106 * perform the ordering. 107 * 108 * CAMD_OUT_OF_MEMORY if not enough memory can be allocated. 109 * 110 * CAMD_INVALID if the input arguments n, Ap, Ai are invalid, or if P is 111 * NULL. 112 * 113 * CAMD_OK_BUT_JUMBLED if the matrix had unsorted columns, and/or duplicate 114 * entries, but was otherwise valid. 115 * 116 * The CAMD routine first forms the pattern of the matrix A+A', and then 117 * computes a fill-reducing ordering, P. If P [k] = i, then row/column i of 118 * the original is the kth pivotal row. In MATLAB notation, the permuted 119 * matrix is A (P,P), except that 0-based indexing is used instead of the 120 * 1-based indexing in MATLAB. 121 * 122 * The Control array is used to set various parameters for CAMD. If a NULL 123 * pointer is passed, default values are used. The Control array is not 124 * modified. 125 * 126 * Control [CAMD_DENSE]: controls the threshold for "dense" rows/columns. 127 * A dense row/column in A+A' can cause CAMD to spend a lot of time in 128 * ordering the matrix. If Control [CAMD_DENSE] >= 0, rows/columns 129 * with more than Control [CAMD_DENSE] * sqrt (n) entries are ignored 130 * during the ordering, and placed last in the output order. The 131 * default value of Control [CAMD_DENSE] is 10. If negative, no 132 * rows/columns are treated as "dense". Rows/columns with 16 or 133 * fewer off-diagonal entries are never considered "dense". 134 * 135 * Control [CAMD_AGGRESSIVE]: controls whether or not to use aggressive 136 * absorption, in which a prior element is absorbed into the current 137 * element if is a subset of the current element, even if it is not 138 * adjacent to the current pivot element (refer to Amestoy, Davis, 139 * & Duff, 1996, for more details). The default value is nonzero, 140 * which means to perform aggressive absorption. This nearly always 141 * leads to a better ordering (because the approximate degrees are 142 * more accurate) and a lower execution time. There are cases where 143 * it can lead to a slightly worse ordering, however. To turn it off, 144 * set Control [CAMD_AGGRESSIVE] to 0. 145 * 146 * Control [2..4] are not used in the current version, but may be used in 147 * future versions. 148 * 149 * The Info array provides statistics about the ordering on output. If it is 150 * not present, the statistics are not returned. This is not an error 151 * condition. 152 * 153 * Info [CAMD_STATUS]: the return value of CAMD, either CAMD_OK, 154 * CAMD_OK_BUT_JUMBLED, CAMD_OUT_OF_MEMORY, or CAMD_INVALID. 155 * 156 * Info [CAMD_N]: n, the size of the input matrix 157 * 158 * Info [CAMD_NZ]: the number of nonzeros in A, nz = Ap [n] 159 * 160 * Info [CAMD_SYMMETRY]: the symmetry of the matrix A. It is the number 161 * of "matched" off-diagonal entries divided by the total number of 162 * off-diagonal entries. An entry A(i,j) is matched if A(j,i) is also 163 * an entry, for any pair (i,j) for which i != j. In MATLAB notation, 164 * S = spones (A) ; 165 * B = tril (S, -1) + triu (S, 1) ; 166 * symmetry = nnz (B & B') / nnz (B) ; 167 * 168 * Info [CAMD_NZDIAG]: the number of entries on the diagonal of A. 169 * 170 * Info [CAMD_NZ_A_PLUS_AT]: the number of nonzeros in A+A', excluding the 171 * diagonal. If A is perfectly symmetric (Info [CAMD_SYMMETRY] = 1) 172 * with a fully nonzero diagonal, then Info [CAMD_NZ_A_PLUS_AT] = nz-n 173 * (the smallest possible value). If A is perfectly unsymmetric 174 * (Info [CAMD_SYMMETRY] = 0, for an upper triangular matrix, for 175 * example) with no diagonal, then Info [CAMD_NZ_A_PLUS_AT] = 2*nz 176 * (the largest possible value). 177 * 178 * Info [CAMD_NDENSE]: the number of "dense" rows/columns of A+A' that were 179 * removed from A prior to ordering. These are placed last in the 180 * output order P. 181 * 182 * Info [CAMD_MEMORY]: the amount of memory used by CAMD, in bytes. In the 183 * current version, this is 1.2 * Info [CAMD_NZ_A_PLUS_AT] + 9*n 184 * times the size of an integer. This is at most 2.4nz + 9n. This 185 * excludes the size of the input arguments Ai, Ap, and P, which have 186 * a total size of nz + 2*n + 1 integers. 187 * 188 * Info [CAMD_NCMPA]: the number of garbage collections performed. 189 * 190 * Info [CAMD_LNZ]: the number of nonzeros in L (excluding the diagonal). 191 * This is a slight upper bound because mass elimination is combined 192 * with the approximate degree update. It is a rough upper bound if 193 * there are many "dense" rows/columns. The rest of the statistics, 194 * below, are also slight or rough upper bounds, for the same reasons. 195 * The post-ordering of the assembly tree might also not exactly 196 * correspond to a true elimination tree postordering. 197 * 198 * Info [CAMD_NDIV]: the number of divide operations for a subsequent LDL' 199 * or LU factorization of the permuted matrix A (P,P). 200 * 201 * Info [CAMD_NMULTSUBS_LDL]: the number of multiply-subtract pairs for a 202 * subsequent LDL' factorization of A (P,P). 203 * 204 * Info [CAMD_NMULTSUBS_LU]: the number of multiply-subtract pairs for a 205 * subsequent LU factorization of A (P,P), assuming that no numerical 206 * pivoting is required. 207 * 208 * Info [CAMD_DMAX]: the maximum number of nonzeros in any column of L, 209 * including the diagonal. 210 * 211 * Info [14..19] are not used in the current version, but may be used in 212 * future versions. 213 */ 214 215 /* ------------------------------------------------------------------------- */ 216 /* direct interface to CAMD */ 217 /* ------------------------------------------------------------------------- */ 218 219 /* camd_2 is the primary CAMD ordering routine. It is not meant to be 220 * user-callable because of its restrictive inputs and because it destroys 221 * the user's input matrix. It does not check its inputs for errors, either. 222 * However, if you can work with these restrictions it can be faster than 223 * camd_order and use less memory (assuming that you can create your own copy 224 * of the matrix for CAMD to destroy). Refer to CAMD/Source/camd_2.c for a 225 * description of each parameter. */ 226 227 void camd_2 228 ( 229 int n, 230 int Pe [ ], 231 int Iw [ ], 232 int Len [ ], 233 int iwlen, 234 int pfree, 235 int Nv [ ], 236 int Next [ ], 237 int Last [ ], 238 int Head [ ], 239 int Elen [ ], 240 int Degree [ ], 241 int W [ ], 242 double Control [ ], 243 double Info [ ], 244 const int C [ ], 245 int BucketSet [ ] 246 ) ; 247 248 void camd_l2 249 ( 250 SuiteSparse_long n, 251 SuiteSparse_long Pe [ ], 252 SuiteSparse_long Iw [ ], 253 SuiteSparse_long Len [ ], 254 SuiteSparse_long iwlen, 255 SuiteSparse_long pfree, 256 SuiteSparse_long Nv [ ], 257 SuiteSparse_long Next [ ], 258 SuiteSparse_long Last [ ], 259 SuiteSparse_long Head [ ], 260 SuiteSparse_long Elen [ ], 261 SuiteSparse_long Degree [ ], 262 SuiteSparse_long W [ ], 263 double Control [ ], 264 double Info [ ], 265 const SuiteSparse_long C [ ], 266 SuiteSparse_long BucketSet [ ] 267 268 ) ; 269 270 /* ------------------------------------------------------------------------- */ 271 /* camd_valid */ 272 /* ------------------------------------------------------------------------- */ 273 274 /* Returns CAMD_OK or CAMD_OK_BUT_JUMBLED if the matrix is valid as input to 275 * camd_order; the latter is returned if the matrix has unsorted and/or 276 * duplicate row indices in one or more columns. Returns CAMD_INVALID if the 277 * matrix cannot be passed to camd_order. For camd_order, the matrix must also 278 * be square. The first two arguments are the number of rows and the number 279 * of columns of the matrix. For its use in CAMD, these must both equal n. 280 */ 281 282 int camd_valid 283 ( 284 int n_row, /* # of rows */ 285 int n_col, /* # of columns */ 286 const int Ap [ ], /* column pointers, of size n_col+1 */ 287 const int Ai [ ] /* row indices, of size Ap [n_col] */ 288 ) ; 289 290 SuiteSparse_long camd_l_valid 291 ( 292 SuiteSparse_long n_row, 293 SuiteSparse_long n_col, 294 const SuiteSparse_long Ap [ ], 295 const SuiteSparse_long Ai [ ] 296 ) ; 297 298 /* ------------------------------------------------------------------------- */ 299 /* camd_cvalid */ 300 /* ------------------------------------------------------------------------- */ 301 302 /* Returns TRUE if the constraint set is valid as input to camd_order, 303 * FALSE otherwise. */ 304 305 int camd_cvalid 306 ( 307 int n, 308 const int C [ ] 309 ) ; 310 311 SuiteSparse_long camd_l_cvalid 312 ( 313 SuiteSparse_long n, 314 const SuiteSparse_long C [ ] 315 ) ; 316 317 /* ------------------------------------------------------------------------- */ 318 /* CAMD memory manager and printf routines */ 319 /* ------------------------------------------------------------------------- */ 320 321 /* moved to SuiteSparse_config.c */ 322 323 /* ------------------------------------------------------------------------- */ 324 /* CAMD Control and Info arrays */ 325 /* ------------------------------------------------------------------------- */ 326 327 /* camd_defaults: sets the default control settings */ 328 void camd_defaults (double Control [ ]) ; 329 void camd_l_defaults (double Control [ ]) ; 330 331 /* camd_control: prints the control settings */ 332 void camd_control (double Control [ ]) ; 333 void camd_l_control (double Control [ ]) ; 334 335 /* camd_info: prints the statistics */ 336 void camd_info (double Info [ ]) ; 337 void camd_l_info (double Info [ ]) ; 338 339 #define CAMD_CONTROL 5 /* size of Control array */ 340 #define CAMD_INFO 20 /* size of Info array */ 341 342 /* contents of Control */ 343 #define CAMD_DENSE 0 /* "dense" if degree > Control [0] * sqrt (n) */ 344 #define CAMD_AGGRESSIVE 1 /* do aggressive absorption if Control [1] != 0 */ 345 346 /* default Control settings */ 347 #define CAMD_DEFAULT_DENSE 10.0 /* default "dense" degree 10*sqrt(n) */ 348 #define CAMD_DEFAULT_AGGRESSIVE 1 /* do aggressive absorption by default */ 349 350 /* contents of Info */ 351 #define CAMD_STATUS 0 /* return value of camd_order and camd_l_order */ 352 #define CAMD_N 1 /* A is n-by-n */ 353 #define CAMD_NZ 2 /* number of nonzeros in A */ 354 #define CAMD_SYMMETRY 3 /* symmetry of pattern (1 is sym., 0 is unsym.) */ 355 #define CAMD_NZDIAG 4 /* # of entries on diagonal */ 356 #define CAMD_NZ_A_PLUS_AT 5 /* nz in A+A' */ 357 #define CAMD_NDENSE 6 /* number of "dense" rows/columns in A */ 358 #define CAMD_MEMORY 7 /* amount of memory used by CAMD */ 359 #define CAMD_NCMPA 8 /* number of garbage collections in CAMD */ 360 #define CAMD_LNZ 9 /* approx. nz in L, excluding the diagonal */ 361 #define CAMD_NDIV 10 /* number of fl. point divides for LU and LDL' */ 362 #define CAMD_NMULTSUBS_LDL 11 /* number of fl. point (*,-) pairs for LDL' */ 363 #define CAMD_NMULTSUBS_LU 12 /* number of fl. point (*,-) pairs for LU */ 364 #define CAMD_DMAX 13 /* max nz. in any column of L, incl. diagonal */ 365 366 /* ------------------------------------------------------------------------- */ 367 /* return values of CAMD */ 368 /* ------------------------------------------------------------------------- */ 369 370 #define CAMD_OK 0 /* success */ 371 #define CAMD_OUT_OF_MEMORY -1 /* malloc failed, or problem too large */ 372 #define CAMD_INVALID -2 /* input arguments are not valid */ 373 #define CAMD_OK_BUT_JUMBLED 1 /* input matrix is OK for camd_order, but 374 * columns were not sorted, and/or duplicate entries were present. CAMD had 375 * to do extra work before ordering the matrix. This is a warning, not an 376 * error. */ 377 378 /* ========================================================================== */ 379 /* === CAMD version ========================================================= */ 380 /* ========================================================================== */ 381 382 /* 383 * As an example, to test if the version you are using is 1.2 or later: 384 * 385 * if (CAMD_VERSION >= CAMD_VERSION_CODE (1,2)) ... 386 * 387 * This also works during compile-time: 388 * 389 * #if (CAMD_VERSION >= CAMD_VERSION_CODE (1,2)) 390 * printf ("This is version 1.2 or later\n") ; 391 * #else 392 * printf ("This is an early version\n") ; 393 * #endif 394 */ 395 396 #define CAMD_DATE "May 4, 2016" 397 #define CAMD_VERSION_CODE(main,sub) ((main) * 1000 + (sub)) 398 #define CAMD_MAIN_VERSION 2 399 #define CAMD_SUB_VERSION 4 400 #define CAMD_SUBSUB_VERSION 6 401 #define CAMD_VERSION CAMD_VERSION_CODE(CAMD_MAIN_VERSION,CAMD_SUB_VERSION) 402 403 #ifdef __cplusplus 404 } 405 #endif 406 407 #endif 408