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