1 /*! \file 2 Copyright (c) 2003, The Regents of the University of California, through 3 Lawrence Berkeley National Laboratory (subject to receipt of any required 4 approvals from U.S. Dept. of Energy) 5 6 All rights reserved. 7 8 The source code is distributed under BSD license, see the file License.txt 9 at the top-level directory. 10 */ 11 /*! @file colamd.h 12 \brief Colamd prototypes and definitions 13 14 <pre> 15 ========================================================================== 16 === colamd/symamd prototypes and definitions ============================= 17 ========================================================================== 18 19 You must include this file (colamd.h) in any routine that uses colamd, 20 symamd, or the related macros and definitions. 21 22 Authors: 23 24 The authors of the code itself are Stefan I. Larimore and Timothy A. 25 Davis (davis@cise.ufl.edu), University of Florida. The algorithm was 26 developed in collaboration with John Gilbert, Xerox PARC, and Esmond 27 Ng, Oak Ridge National Laboratory. 28 29 Date: 30 31 September 8, 2003. Version 2.3. 32 33 Acknowledgements: 34 35 This work was supported by the National Science Foundation, under 36 grants DMS-9504974 and DMS-9803599. 37 38 Notice: 39 40 Copyright (c) 1998-2003 by the University of Florida. 41 All Rights Reserved. 42 43 THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY 44 EXPRESSED OR IMPLIED. ANY USE IS AT YOUR OWN RISK. 45 46 Permission is hereby granted to use, copy, modify, and/or distribute 47 this program, provided that the Copyright, this License, and the 48 Availability of the original version is retained on all copies and made 49 accessible to the end-user of any code or package that includes COLAMD 50 or any modified version of COLAMD. 51 52 Availability: 53 54 The colamd/symamd library is available at 55 56 http://www.cise.ufl.edu/research/sparse/colamd/ 57 58 This is the http://www.cise.ufl.edu/research/sparse/colamd/colamd.h 59 file. It is required by the colamd.c, colamdmex.c, and symamdmex.c 60 files, and by any C code that calls the routines whose prototypes are 61 listed below, or that uses the colamd/symamd definitions listed below. 62 </pre> 63 */ 64 65 #ifndef COLAMD_H 66 #define COLAMD_H 67 68 /* ========================================================================== */ 69 /* === Include files ======================================================== */ 70 /* ========================================================================== */ 71 72 #include <stdlib.h> 73 74 /* ========================================================================== */ 75 /* === Knob and statistics definitions ====================================== */ 76 /* ========================================================================== */ 77 78 /* size of the knobs [ ] array. Only knobs [0..1] are currently used. */ 79 #define COLAMD_KNOBS 20 80 81 /* number of output statistics. Only stats [0..6] are currently used. */ 82 #define COLAMD_STATS 20 83 84 /* knobs [0] and stats [0]: dense row knob and output statistic. */ 85 #define COLAMD_DENSE_ROW 0 86 87 /* knobs [1] and stats [1]: dense column knob and output statistic. */ 88 #define COLAMD_DENSE_COL 1 89 90 /* stats [2]: memory defragmentation count output statistic */ 91 #define COLAMD_DEFRAG_COUNT 2 92 93 /* stats [3]: colamd status: zero OK, > 0 warning or notice, < 0 error */ 94 #define COLAMD_STATUS 3 95 96 /* stats [4..6]: error info, or info on jumbled columns */ 97 #define COLAMD_INFO1 4 98 #define COLAMD_INFO2 5 99 #define COLAMD_INFO3 6 100 101 /* error codes returned in stats [3]: */ 102 #define COLAMD_OK (0) 103 #define COLAMD_OK_BUT_JUMBLED (1) 104 #define COLAMD_ERROR_A_not_present (-1) 105 #define COLAMD_ERROR_p_not_present (-2) 106 #define COLAMD_ERROR_nrow_negative (-3) 107 #define COLAMD_ERROR_ncol_negative (-4) 108 #define COLAMD_ERROR_nnz_negative (-5) 109 #define COLAMD_ERROR_p0_nonzero (-6) 110 #define COLAMD_ERROR_A_too_small (-7) 111 #define COLAMD_ERROR_col_length_negative (-8) 112 #define COLAMD_ERROR_row_index_out_of_bounds (-9) 113 #define COLAMD_ERROR_out_of_memory (-10) 114 #define COLAMD_ERROR_internal_error (-999) 115 116 /* ========================================================================== */ 117 /* === Row and Column structures ============================================ */ 118 /* ========================================================================== */ 119 120 /* User code that makes use of the colamd/symamd routines need not directly */ 121 /* reference these structures. They are used only for the COLAMD_RECOMMENDED */ 122 /* macro. */ 123 124 typedef struct Colamd_Col_struct 125 { 126 int start ; /* index for A of first row in this column, or DEAD */ 127 /* if column is dead */ 128 int length ; /* number of rows in this column */ 129 union 130 { 131 int thickness ; /* number of original columns represented by this */ 132 /* col, if the column is alive */ 133 int parent ; /* parent in parent tree super-column structure, if */ 134 /* the column is dead */ 135 } shared1 ; 136 union 137 { 138 int score ; /* the score used to maintain heap, if col is alive */ 139 int order ; /* pivot ordering of this column, if col is dead */ 140 } shared2 ; 141 union 142 { 143 int headhash ; /* head of a hash bucket, if col is at the head of */ 144 /* a degree list */ 145 int hash ; /* hash value, if col is not in a degree list */ 146 int prev ; /* previous column in degree list, if col is in a */ 147 /* degree list (but not at the head of a degree list) */ 148 } shared3 ; 149 union 150 { 151 int degree_next ; /* next column, if col is in a degree list */ 152 int hash_next ; /* next column, if col is in a hash list */ 153 } shared4 ; 154 155 } Colamd_Col ; 156 157 typedef struct Colamd_Row_struct 158 { 159 int start ; /* index for A of first col in this row */ 160 int length ; /* number of principal columns in this row */ 161 union 162 { 163 int degree ; /* number of principal & non-principal columns in row */ 164 int p ; /* used as a row pointer in init_rows_cols () */ 165 } shared1 ; 166 union 167 { 168 int mark ; /* for computing set differences and marking dead rows*/ 169 int first_column ;/* first column in row (used in garbage collection) */ 170 } shared2 ; 171 172 } Colamd_Row ; 173 174 /* ========================================================================== */ 175 /* === Colamd recommended memory size ======================================= */ 176 /* ========================================================================== */ 177 178 /* 179 The recommended length Alen of the array A passed to colamd is given by 180 the COLAMD_RECOMMENDED (nnz, n_row, n_col) macro. It returns -1 if any 181 argument is negative. 2*nnz space is required for the row and column 182 indices of the matrix. COLAMD_C (n_col) + COLAMD_R (n_row) space is 183 required for the Col and Row arrays, respectively, which are internal to 184 colamd. An additional n_col space is the minimal amount of "elbow room", 185 and nnz/5 more space is recommended for run time efficiency. 186 187 This macro is not needed when using symamd. 188 189 Explicit typecast to int added Sept. 23, 2002, COLAMD version 2.2, to avoid 190 gcc -pedantic warning messages. 191 */ 192 193 #define COLAMD_C(n_col) ((int) (((n_col) + 1) * sizeof (Colamd_Col) / sizeof (int))) 194 #define COLAMD_R(n_row) ((int) (((n_row) + 1) * sizeof (Colamd_Row) / sizeof (int))) 195 196 #define COLAMD_RECOMMENDED(nnz, n_row, n_col) \ 197 ( \ 198 ((nnz) < 0 || (n_row) < 0 || (n_col) < 0) \ 199 ? \ 200 (-1) \ 201 : \ 202 (2 * (nnz) + COLAMD_C (n_col) + COLAMD_R (n_row) + (n_col) + ((nnz) / 5)) \ 203 ) 204 205 /* ========================================================================== */ 206 /* === Prototypes of user-callable routines ================================= */ 207 /* ========================================================================== */ 208 209 int colamd_recommended /* returns recommended value of Alen, */ 210 /* or (-1) if input arguments are erroneous */ 211 ( 212 int nnz, /* nonzeros in A */ 213 int n_row, /* number of rows in A */ 214 int n_col /* number of columns in A */ 215 ) ; 216 217 void colamd_set_defaults /* sets default parameters */ 218 ( /* knobs argument is modified on output */ 219 double knobs [COLAMD_KNOBS] /* parameter settings for colamd */ 220 ) ; 221 222 int colamd /* returns (1) if successful, (0) otherwise*/ 223 ( /* A and p arguments are modified on output */ 224 int n_row, /* number of rows in A */ 225 int n_col, /* number of columns in A */ 226 int Alen, /* size of the array A */ 227 int A [], /* row indices of A, of size Alen */ 228 int p [], /* column pointers of A, of size n_col+1 */ 229 double knobs [COLAMD_KNOBS],/* parameter settings for colamd */ 230 int stats [COLAMD_STATS] /* colamd output statistics and error codes */ 231 ) ; 232 233 int symamd /* return (1) if OK, (0) otherwise */ 234 ( 235 int n, /* number of rows and columns of A */ 236 int A [], /* row indices of A */ 237 int p [], /* column pointers of A */ 238 int perm [], /* output permutation, size n_col+1 */ 239 double knobs [COLAMD_KNOBS], /* parameters (uses defaults if NULL) */ 240 int stats [COLAMD_STATS], /* output statistics and error codes */ 241 void * (*allocate) (size_t, size_t), 242 /* pointer to calloc (ANSI C) or */ 243 /* mxCalloc (for MATLAB mexFunction) */ 244 void (*release) (void *) 245 /* pointer to free (ANSI C) or */ 246 /* mxFree (for MATLAB mexFunction) */ 247 ) ; 248 249 void colamd_report 250 ( 251 int stats [COLAMD_STATS] 252 ) ; 253 254 void symamd_report 255 ( 256 int stats [COLAMD_STATS] 257 ) ; 258 259 #endif /* COLAMD_H */ 260