Amesos Package Browser (Single Doxygen Collection) Development
amesos_camd.h
Go to the documentation of this file.
00001 /* ========================================================================= */
00002 /* === CAMD:  approximate minimum degree ordering ========================== */
00003 /* ========================================================================= */
00004 
00005 /* ------------------------------------------------------------------------- */
00006 /* CAMD Version 2.2, Copyright (c) 2007 by Timothy A. Davis, Yanqing Chen,   */
00007 /* Patrick R. Amestoy, and Iain S. Duff.  See ../README.txt for License.     */
00008 /* email: davis at cise.ufl.edu    CISE Department, Univ. of Florida.        */
00009 /* web: http://www.cise.ufl.edu/research/sparse/camd                         */
00010 /* ------------------------------------------------------------------------- */
00011 
00012 /* CAMD finds a symmetric ordering P of a matrix A so that the Cholesky
00013  * factorization of P*A*P' has fewer nonzeros and takes less work than the
00014  * Cholesky factorization of A.  If A is not symmetric, then it performs its
00015  * ordering on the matrix A+A'.  Two sets of user-callable routines are
00016  * provided, one for int integers and the other for UF_long integers.
00017  *
00018  * The method is based on the approximate minimum degree algorithm, discussed
00019  * in Amestoy, Davis, and Duff, "An approximate degree ordering algorithm",
00020  * SIAM Journal of Matrix Analysis and Applications, vol. 17, no. 4, pp.
00021  * 886-905, 1996.
00022  */
00023 
00024 #ifndef AMESOS_CAMD_H
00025 #define AMESOS_CAMD_H
00026 
00027 /* make it easy for C++ programs to include CAMD */
00028 #ifdef __cplusplus
00029 extern "C" {
00030 #endif
00031 
00032 /* get the definition of size_t: */
00033 #include <stddef.h>
00034 
00035 /* define UF_long */
00036 #include "amesos_UFconfig.h"
00037 
00038 int amesos_camd_order       /* returns CAMD_OK, CAMD_OK_BUT_JUMBLED,
00039            * CAMD_INVALID, or CAMD_OUT_OF_MEMORY */
00040 (
00041     int n,        /* A is n-by-n.  n must be >= 0. */
00042     const int Ap [ ],     /* column pointers for A, of size n+1 */
00043     const int Ai [ ],     /* row indices of A, of size nz = Ap [n] */
00044     int P [ ],        /* output permutation, of size n */
00045     double Control [ ],     /* input Control settings, of size CAMD_CONTROL */
00046     double Info [ ],      /* output Info statistics, of size CAMD_INFO */
00047     const int C [ ]     /* Constraint set of A, of size n; can be NULL */
00048 ) ;
00049 
00050 UF_long amesos_camd_l_order     /* see above for description of arguments */
00051 (
00052     UF_long n,
00053     const UF_long Ap [ ],
00054     const UF_long Ai [ ],
00055     UF_long P [ ],
00056     double Control [ ],
00057     double Info [ ],
00058     const UF_long C [ ]
00059 ) ;
00060 
00061 /* Input arguments (not modified):
00062  *
00063  *  n: the matrix A is n-by-n.
00064  *  Ap: an int/UF_long array of size n+1, containing column pointers of A.
00065  *  Ai: an int/UF_long array of size nz, containing the row indices of A,
00066  *      where nz = Ap [n].
00067  *  Control:  a double array of size CAMD_CONTROL, containing control
00068  *      parameters.  Defaults are used if Control is NULL.
00069  *
00070  * Output arguments (not defined on input):
00071  *
00072  *  P: an int/UF_long array of size n, containing the output permutation. If
00073  *      row i is the kth pivot row, then P [k] = i.  In MATLAB notation,
00074  *      the reordered matrix is A (P,P).
00075  *  Info: a double array of size CAMD_INFO, containing statistical
00076  *      information.  Ignored if Info is NULL.
00077  *
00078  * On input, the matrix A is stored in column-oriented form.  The row indices
00079  * of nonzero entries in column j are stored in Ai [Ap [j] ... Ap [j+1]-1].
00080  *
00081  * If the row indices appear in ascending order in each column, and there
00082  * are no duplicate entries, then camd_order is slightly more efficient in
00083  * terms of time and memory usage.  If this condition does not hold, a copy
00084  * of the matrix is created (where these conditions do hold), and the copy is
00085  * ordered.
00086  *
00087  * Row indices must be in the range 0 to
00088  * n-1.  Ap [0] must be zero, and thus nz = Ap [n] is the number of nonzeros
00089  * in A.  The array Ap is of size n+1, and the array Ai is of size nz = Ap [n].
00090  * The matrix does not need to be symmetric, and the diagonal does not need to
00091  * be present (if diagonal entries are present, they are ignored except for
00092  * the output statistic Info [CAMD_NZDIAG]).  The arrays Ai and Ap are not
00093  * modified.  This form of the Ap and Ai arrays to represent the nonzero
00094  * pattern of the matrix A is the same as that used internally by MATLAB.
00095  * If you wish to use a more flexible input structure, please see the
00096  * umfpack_*_triplet_to_col routines in the UMFPACK package, at
00097  * http://www.cise.ufl.edu/research/sparse/umfpack.
00098  *
00099  * Restrictions:  n >= 0.  Ap [0] = 0.  Ap [j] <= Ap [j+1] for all j in the
00100  *  range 0 to n-1.  nz = Ap [n] >= 0.  Ai [0..nz-1] must be in the range 0
00101  *  to n-1.  Finally, Ai, Ap, and P must not be NULL.  If any of these
00102  *  restrictions are not met, CAMD returns CAMD_INVALID.
00103  *
00104  * CAMD returns:
00105  *
00106  *  CAMD_OK if the matrix is valid and sufficient memory can be allocated to
00107  *      perform the ordering.
00108  *
00109  *  CAMD_OUT_OF_MEMORY if not enough memory can be allocated.
00110  *
00111  *  CAMD_INVALID if the input arguments n, Ap, Ai are invalid, or if P is
00112  *      NULL.
00113  *
00114  *  CAMD_OK_BUT_JUMBLED if the matrix had unsorted columns, and/or duplicate
00115  *      entries, but was otherwise valid.
00116  *
00117  * The CAMD routine first forms the pattern of the matrix A+A', and then
00118  * computes a fill-reducing ordering, P.  If P [k] = i, then row/column i of
00119  * the original is the kth pivotal row.  In MATLAB notation, the permuted
00120  * matrix is A (P,P), except that 0-based indexing is used instead of the
00121  * 1-based indexing in MATLAB.
00122  *
00123  * The Control array is used to set various parameters for CAMD.  If a NULL
00124  * pointer is passed, default values are used.  The Control array is not
00125  * modified.
00126  *
00127  *  Control [CAMD_DENSE]:  controls the threshold for "dense" rows/columns.
00128  *      A dense row/column in A+A' can cause CAMD to spend a lot of time in
00129  *      ordering the matrix.  If Control [CAMD_DENSE] >= 0, rows/columns
00130  *      with more than Control [CAMD_DENSE] * sqrt (n) entries are ignored
00131  *      during the ordering, and placed last in the output order.  The
00132  *      default value of Control [CAMD_DENSE] is 10.  If negative, no
00133  *      rows/columns are treated as "dense".  Rows/columns with 16 or
00134  *      fewer off-diagonal entries are never considered "dense".
00135  *
00136  *  Control [CAMD_AGGRESSIVE]: controls whether or not to use aggressive
00137  *      absorption, in which a prior element is absorbed into the current
00138  *      element if is a subset of the current element, even if it is not
00139  *      adjacent to the current pivot element (refer to Amestoy, Davis,
00140  *      & Duff, 1996, for more details).  The default value is nonzero,
00141  *      which means to perform aggressive absorption.  This nearly always
00142  *      leads to a better ordering (because the approximate degrees are
00143  *      more accurate) and a lower execution time.  There are cases where
00144  *      it can lead to a slightly worse ordering, however.  To turn it off,
00145  *      set Control [CAMD_AGGRESSIVE] to 0.
00146  *
00147  *  Control [2..4] are not used in the current version, but may be used in
00148  *      future versions.
00149  *
00150  * The Info array provides statistics about the ordering on output.  If it is
00151  * not present, the statistics are not returned.  This is not an error
00152  * condition.
00153  * 
00154  *  Info [CAMD_STATUS]:  the return value of CAMD, either CAMD_OK,
00155  *      CAMD_OK_BUT_JUMBLED, CAMD_OUT_OF_MEMORY, or CAMD_INVALID.
00156  *
00157  *  Info [CAMD_N]: n, the size of the input matrix
00158  *
00159  *  Info [CAMD_NZ]: the number of nonzeros in A, nz = Ap [n]
00160  *
00161  *  Info [CAMD_SYMMETRY]:  the symmetry of the matrix A.  It is the number
00162  *      of "matched" off-diagonal entries divided by the total number of
00163  *      off-diagonal entries.  An entry A(i,j) is matched if A(j,i) is also
00164  *      an entry, for any pair (i,j) for which i != j.  In MATLAB notation,
00165  *    S = spones (A) ;
00166  *    B = tril (S, -1) + triu (S, 1) ;
00167  *    symmetry = nnz (B & B') / nnz (B) ;
00168  *
00169  *  Info [CAMD_NZDIAG]: the number of entries on the diagonal of A.
00170  *
00171  *  Info [CAMD_NZ_A_PLUS_AT]:  the number of nonzeros in A+A', excluding the
00172  *      diagonal.  If A is perfectly symmetric (Info [CAMD_SYMMETRY] = 1)
00173  *      with a fully nonzero diagonal, then Info [CAMD_NZ_A_PLUS_AT] = nz-n
00174  *      (the smallest possible value).  If A is perfectly unsymmetric
00175  *      (Info [CAMD_SYMMETRY] = 0, for an upper triangular matrix, for
00176  *      example) with no diagonal, then Info [CAMD_NZ_A_PLUS_AT] = 2*nz
00177  *      (the largest possible value).
00178  *
00179  *  Info [CAMD_NDENSE]: the number of "dense" rows/columns of A+A' that were
00180  *      removed from A prior to ordering.  These are placed last in the
00181  *      output order P.
00182  *
00183  *  Info [CAMD_MEMORY]: the amount of memory used by CAMD, in bytes.  In the
00184  *      current version, this is 1.2 * Info  [CAMD_NZ_A_PLUS_AT] + 9*n
00185  *      times the size of an integer.  This is at most 2.4nz + 9n.  This
00186  *      excludes the size of the input arguments Ai, Ap, and P, which have
00187  *      a total size of nz + 2*n + 1 integers.
00188  *
00189  *  Info [CAMD_NCMPA]: the number of garbage collections performed.
00190  *
00191  *  Info [CAMD_LNZ]: the number of nonzeros in L (excluding the diagonal).
00192  *      This is a slight upper bound because mass elimination is combined
00193  *      with the approximate degree update.  It is a rough upper bound if
00194  *      there are many "dense" rows/columns.  The rest of the statistics,
00195  *      below, are also slight or rough upper bounds, for the same reasons.
00196  *      The post-ordering of the assembly tree might also not exactly
00197  *      correspond to a true elimination tree postordering.
00198  *
00199  *  Info [CAMD_NDIV]: the number of divide operations for a subsequent LDL'
00200  *      or LU factorization of the permuted matrix A (P,P).
00201  *
00202  *  Info [CAMD_NMULTSUBS_LDL]:  the number of multiply-subtract pairs for a
00203  *      subsequent LDL' factorization of A (P,P).
00204  *
00205  *  Info [CAMD_NMULTSUBS_LU]:  the number of multiply-subtract pairs for a
00206  *      subsequent LU factorization of A (P,P), assuming that no numerical
00207  *      pivoting is required.
00208  *
00209  *  Info [CAMD_DMAX]:  the maximum number of nonzeros in any column of L,
00210  *      including the diagonal.
00211  *
00212  *  Info [14..19] are not used in the current version, but may be used in
00213  *      future versions.
00214  */    
00215 
00216 /* ------------------------------------------------------------------------- */
00217 /* direct interface to CAMD */
00218 /* ------------------------------------------------------------------------- */
00219 
00220 /* camd_2 is the primary CAMD ordering routine.  It is not meant to be
00221  * user-callable because of its restrictive inputs and because it destroys
00222  * the user's input matrix.  It does not check its inputs for errors, either.
00223  * However, if you can work with these restrictions it can be faster than
00224  * camd_order and use less memory (assuming that you can create your own copy
00225  * of the matrix for CAMD to destroy).  Refer to CAMD/Source/camd_2.c for a
00226  * description of each parameter. */
00227 
00228 void amesos_camd_2
00229 (
00230     int n,
00231     int Pe [ ],
00232     int Iw [ ],
00233     int Len [ ],
00234     int iwlen,
00235     int pfree,
00236     int Nv [ ],
00237     int Next [ ], 
00238     int Last [ ],
00239     int Head [ ],
00240     int Elen [ ],
00241     int Degree [ ],
00242     int W [ ],
00243     double Control [ ],
00244     double Info [ ],
00245     const int C [ ],
00246     int BucketSet [ ] 
00247 ) ;
00248 
00249 void amesos_camd_l2
00250 (
00251     UF_long n,
00252     UF_long Pe [ ],
00253     UF_long Iw [ ],
00254     UF_long Len [ ],
00255     UF_long iwlen,
00256     UF_long pfree,
00257     UF_long Nv [ ],
00258     UF_long Next [ ], 
00259     UF_long Last [ ],
00260     UF_long Head [ ],
00261     UF_long Elen [ ],
00262     UF_long Degree [ ],
00263     UF_long W [ ],
00264     double Control [ ],
00265     double Info [ ],
00266     const UF_long C [ ],
00267     UF_long BucketSet [ ]
00268     
00269 ) ;
00270 
00271 /* ------------------------------------------------------------------------- */
00272 /* camd_valid */
00273 /* ------------------------------------------------------------------------- */
00274 
00275 /* Returns CAMD_OK or CAMD_OK_BUT_JUMBLED if the matrix is valid as input to
00276  * camd_order; the latter is returned if the matrix has unsorted and/or
00277  * duplicate row indices in one or more columns.  Returns CAMD_INVALID if the
00278  * matrix cannot be passed to camd_order.  For camd_order, the matrix must also
00279  * be square.  The first two arguments are the number of rows and the number
00280  * of columns of the matrix.  For its use in CAMD, these must both equal n.
00281  */
00282 
00283 int amesos_camd_valid
00284 (
00285     int n_row,        /* # of rows */
00286     int n_col,        /* # of columns */
00287     const int Ap [ ],     /* column pointers, of size n_col+1 */
00288     const int Ai [ ]      /* row indices, of size Ap [n_col] */
00289 ) ;
00290 
00291 UF_long amesos_camd_l_valid
00292 (
00293     UF_long n_row,
00294     UF_long n_col,
00295     const UF_long Ap [ ],
00296     const UF_long Ai [ ]
00297 ) ;
00298 
00299 /* ------------------------------------------------------------------------- */
00300 /* camd_cvalid */
00301 /* ------------------------------------------------------------------------- */
00302 
00303 /* Returns TRUE if the constraint set is valid as input to camd_order,
00304  * FALSE otherwise. */
00305 
00306 int amesos_camd_cvalid
00307 (
00308    int n,
00309    const int C [ ]
00310 ) ;
00311 
00312 UF_long amesos_camd_l_cvalid
00313 (
00314    UF_long n,
00315    const UF_long C [ ]
00316 ) ;
00317 
00318 /* ------------------------------------------------------------------------- */
00319 /* CAMD memory manager and printf routines */
00320 /* ------------------------------------------------------------------------- */
00321 
00322 /* The user can redefine these to change the malloc, free, and printf routines
00323  * that CAMD uses. */
00324 
00325 #ifndef EXTERN
00326 #define EXTERN extern
00327 #endif
00328 
00329 EXTERN void *(*amesos_camd_malloc) (size_t) ;       /* pointer to malloc */
00330 EXTERN void (*amesos_camd_free) (void *) ;        /* pointer to free */
00331 EXTERN void *(*amesos_camd_realloc) (void *, size_t) ;      /* pointer to realloc */
00332 EXTERN void *(*amesos_camd_calloc) (size_t, size_t) ;     /* pointer to calloc */
00333 EXTERN int (*amesos_camd_printf) (const char *, ...) ;      /* pointer to printf */
00334 
00335 /* ------------------------------------------------------------------------- */
00336 /* CAMD Control and Info arrays */
00337 /* ------------------------------------------------------------------------- */
00338 
00339 /* camd_defaults:  sets the default control settings */
00340 void amesos_camd_defaults   (double Control [ ]) ;
00341 void amesos_camd_l_defaults (double Control [ ]) ;
00342 
00343 /* camd_control: prints the control settings */
00344 void amesos_camd_control    (double Control [ ]) ;
00345 void amesos_camd_l_control  (double Control [ ]) ;
00346 
00347 /* camd_info: prints the statistics */
00348 void amesos_camd_info       (double Info [ ]) ;
00349 void amesos_camd_l_info     (double Info [ ]) ;
00350 
00351 #define CAMD_CONTROL 5      /* size of Control array */
00352 #define CAMD_INFO 20      /* size of Info array */
00353 
00354 /* contents of Control */
00355 #define CAMD_DENSE 0      /* "dense" if degree > Control [0] * sqrt (n) */
00356 #define CAMD_AGGRESSIVE 1    /* do aggressive absorption if Control [1] != 0 */
00357 
00358 /* default Control settings */
00359 #define CAMD_DEFAULT_DENSE 10.0     /* default "dense" degree 10*sqrt(n) */
00360 #define CAMD_DEFAULT_AGGRESSIVE 1    /* do aggressive absorption by default */
00361 
00362 /* contents of Info */
00363 #define CAMD_STATUS 0     /* return value of camd_order and camd_l_order */
00364 #define CAMD_N 1        /* A is n-by-n */
00365 #define CAMD_NZ 2     /* number of nonzeros in A */ 
00366 #define CAMD_SYMMETRY 3     /* symmetry of pattern (1 is sym., 0 is unsym.) */
00367 #define CAMD_NZDIAG 4     /* # of entries on diagonal */
00368 #define CAMD_NZ_A_PLUS_AT 5  /* nz in A+A' */
00369 #define CAMD_NDENSE 6     /* number of "dense" rows/columns in A */
00370 #define CAMD_MEMORY 7     /* amount of memory used by CAMD */
00371 #define CAMD_NCMPA 8      /* number of garbage collections in CAMD */
00372 #define CAMD_LNZ 9      /* approx. nz in L, excluding the diagonal */
00373 #define CAMD_NDIV 10      /* number of fl. point divides for LU and LDL' */
00374 #define CAMD_NMULTSUBS_LDL 11 /* number of fl. point (*,-) pairs for LDL' */
00375 #define CAMD_NMULTSUBS_LU 12  /* number of fl. point (*,-) pairs for LU */
00376 #define CAMD_DMAX 13       /* max nz. in any column of L, incl. diagonal */
00377 
00378 /* ------------------------------------------------------------------------- */
00379 /* return values of CAMD */
00380 /* ------------------------------------------------------------------------- */
00381 
00382 #define CAMD_OK 0   /* success */
00383 #define CAMD_OUT_OF_MEMORY -1 /* malloc failed, or problem too large */
00384 #define CAMD_INVALID -2   /* input arguments are not valid */
00385 #define CAMD_OK_BUT_JUMBLED 1 /* input matrix is OK for camd_order, but
00386     * columns were not sorted, and/or duplicate entries were present.  CAMD had
00387     * to do extra work before ordering the matrix.  This is a warning, not an
00388     * error.  */
00389 
00390 /* ========================================================================== */
00391 /* === CAMD version ========================================================= */
00392 /* ========================================================================== */
00393 
00394 /*
00395  * As an example, to test if the version you are using is 1.2 or later:
00396  *
00397  *  if (CAMD_VERSION >= CAMD_VERSION_CODE (1,2)) ...
00398  *
00399  * This also works during compile-time:
00400  *
00401  *  #if (CAMD_VERSION >= CAMD_VERSION_CODE (1,2))
00402  *      printf ("This is version 1.2 or later\n") ;
00403  *  #else
00404  *      printf ("This is an early version\n") ;
00405  *  #endif
00406  */
00407 
00408 #define CAMD_DATE "May 31, 2007"
00409 #define CAMD_VERSION_CODE(main,sub) ((main) * 1000 + (sub))
00410 #define CAMD_MAIN_VERSION 2
00411 #define CAMD_SUB_VERSION 2
00412 #define CAMD_SUBSUB_VERSION 0
00413 #define CAMD_VERSION CAMD_VERSION_CODE(CAMD_MAIN_VERSION,CAMD_SUB_VERSION)
00414 
00415 #ifdef __cplusplus
00416 }
00417 #endif
00418 
00419 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines