Amesos Package Browser (Single Doxygen Collection) Development
amesos_camd_order.c
Go to the documentation of this file.
00001 /* ========================================================================= */
00002 /* === CAMD_order ========================================================== */
00003 /* ========================================================================= */
00004 
00005 /* ------------------------------------------------------------------------- */
00006 /* CAMD, Copyright (c) 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 /* User-callable CAMD minimum degree ordering routine.  See camd.h for
00013  * documentation.
00014  */
00015 
00016 #include "amesos_camd_internal.h"
00017 
00018 /* ========================================================================= */
00019 /* === CAMD_order ========================================================== */
00020 /* ========================================================================= */
00021 
00022 GLOBAL Int CAMD_order
00023 (
00024     Int n,
00025     const Int Ap [ ],
00026     const Int Ai [ ],
00027     Int P [ ],
00028     double Control [ ],
00029     double Info [ ],
00030     const Int C [ ]
00031 )
00032 {
00033     Int *Len, *S, nz, i, *Pinv, info, status, *Rp, *Ri, *Cp, *Ci, ok ;
00034     size_t nzaat, slen ;
00035     double mem = 0 ;
00036 
00037 #ifndef NDEBUG
00038     CAMD_debug_init ("camd") ;
00039 #endif
00040 
00041     /* clear the Info array, if it exists */
00042     info = Info != (double *) NULL ;
00043     if (info)
00044     {
00045   for (i = 0 ; i < CAMD_INFO ; i++)
00046   {
00047       Info [i] = EMPTY ;
00048   }
00049   Info [CAMD_N] = n ;
00050   Info [CAMD_STATUS] = CAMD_OK ;
00051     }
00052 
00053     /* make sure inputs exist and n is >= 0 */
00054     if (Ai == (Int *) NULL || Ap == (Int *) NULL || P == (Int *) NULL || n < 0)
00055     {
00056   if (info) Info [CAMD_STATUS] = CAMD_INVALID ;
00057   return (CAMD_INVALID) ;     /* arguments are invalid */
00058     }
00059 
00060     if (n == 0)
00061     {
00062   return (CAMD_OK) ;      /* n is 0 so there's nothing to do */
00063     }
00064 
00065     nz = Ap [n] ;
00066     if (info)
00067     {
00068   Info [CAMD_NZ] = nz ;
00069     }
00070     if (nz < 0)
00071     {
00072   if (info) Info [CAMD_STATUS] = CAMD_INVALID ;
00073   return (CAMD_INVALID) ;
00074     }
00075 
00076     /* check if n or nz will cause size_t overflow */
00077     if ((size_t) n >= SIZE_T_MAX / sizeof (Int)
00078      || (size_t) nz >= SIZE_T_MAX / sizeof (Int))
00079     {
00080   if (info) Info [CAMD_STATUS] = CAMD_OUT_OF_MEMORY ;
00081   return (CAMD_OUT_OF_MEMORY) ;     /* problem too large */
00082     }
00083 
00084     /* check the input matrix:  CAMD_OK, CAMD_INVALID, or CAMD_OK_BUT_JUMBLED */
00085     status = CAMD_valid (n, n, Ap, Ai) ;
00086 
00087     if (status == CAMD_INVALID)
00088     {
00089   if (info) Info [CAMD_STATUS] = CAMD_INVALID ;
00090   return (CAMD_INVALID) ;     /* matrix is invalid */
00091     }
00092 
00093     /* allocate two size-n integer workspaces */
00094     Len = amesos_camd_malloc (n * sizeof (Int)) ;
00095     Pinv = amesos_camd_malloc (n * sizeof (Int)) ;
00096     mem += n ;
00097     mem += n ;
00098     if (!Len || !Pinv)
00099     {
00100   /* :: out of memory :: */
00101   amesos_camd_free (Len) ;
00102   amesos_camd_free (Pinv) ;
00103   if (info) Info [CAMD_STATUS] = CAMD_OUT_OF_MEMORY ;
00104   return (CAMD_OUT_OF_MEMORY) ;
00105     }
00106 
00107     if (status == CAMD_OK_BUT_JUMBLED)
00108     {
00109   /* sort the input matrix and remove duplicate entries */
00110   CAMD_DEBUG1 (("Matrix is jumbled\n")) ;
00111   Rp = amesos_camd_malloc ((n+1) * sizeof (Int)) ;
00112   Ri = amesos_camd_malloc (MAX (nz,1) * sizeof (Int)) ;
00113   mem += (n+1) ;
00114   mem += MAX (nz,1) ;
00115   if (!Rp || !Ri)
00116   {
00117       /* :: out of memory :: */
00118       amesos_camd_free (Rp) ;
00119       amesos_camd_free (Ri) ;
00120       amesos_camd_free (Len) ;
00121       amesos_camd_free (Pinv) ;
00122       if (info) Info [CAMD_STATUS] = CAMD_OUT_OF_MEMORY ;
00123       return (CAMD_OUT_OF_MEMORY) ;
00124   }
00125   /* use Len and Pinv as workspace to create R = A' */
00126   CAMD_preprocess (n, Ap, Ai, Rp, Ri, Len, Pinv) ;
00127   Cp = Rp ;
00128   Ci = Ri ;
00129     }
00130     else
00131     {
00132   /* order the input matrix as-is.  No need to compute R = A' first */
00133   Rp = NULL ;
00134   Ri = NULL ;
00135   Cp = (Int *) Ap ;
00136   Ci = (Int *) Ai ;
00137     }
00138 
00139     /* --------------------------------------------------------------------- */
00140     /* determine the symmetry and count off-diagonal nonzeros in A+A' */
00141     /* --------------------------------------------------------------------- */
00142 
00143     nzaat = CAMD_aat (n, Cp, Ci, Len, P, Info) ;
00144     CAMD_DEBUG1 (("nzaat: %g\n", (double) nzaat)) ;
00145     ASSERT ((MAX (nz-n, 0) <= nzaat) && (nzaat <= 2 * (size_t) nz)) ;
00146 
00147     /* --------------------------------------------------------------------- */
00148     /* allocate workspace for matrix, elbow room, and 7 size-n vectors */
00149     /* --------------------------------------------------------------------- */
00150 
00151     S = NULL ;
00152     slen = nzaat ;      /* space for matrix */
00153     ok = ((slen + nzaat/5) >= slen) ; /* check for size_t overflow */
00154     slen += nzaat/5 ;     /* add elbow room */
00155     for (i = 0 ; ok && i < 8 ; i++)
00156     {
00157   ok = ((slen + n+1) > slen) ;  /* check for size_t overflow */
00158   slen += (n+1) ;   /* size-n elbow room, 7 size-(n+1) workspace */
00159     }
00160     mem += slen ;
00161     ok = ok && (slen < SIZE_T_MAX / sizeof (Int)) ; /* check for overflow */
00162     ok = ok && (slen < Int_MAX) ; /* S[i] for Int i must be OK */
00163     if (ok)
00164     {
00165   S = amesos_camd_malloc (slen * sizeof (Int)) ;
00166     }
00167     CAMD_DEBUG1 (("slen %g\n", (double) slen)) ;
00168     if (!S)
00169     {
00170   /* :: out of memory :: (or problem too large) */
00171   amesos_camd_free (Rp) ;
00172   amesos_camd_free (Ri) ;
00173   amesos_camd_free (Len) ;
00174   amesos_camd_free (Pinv) ;
00175   if (info) Info [CAMD_STATUS] = CAMD_OUT_OF_MEMORY ;
00176   return (CAMD_OUT_OF_MEMORY) ;
00177     }
00178     if (info)
00179     {
00180   /* memory usage, in bytes. */
00181   Info [CAMD_MEMORY] = mem * sizeof (Int) ;
00182     }
00183 
00184     /* --------------------------------------------------------------------- */
00185     /* order the matrix */
00186     /* --------------------------------------------------------------------- */
00187 
00188     CAMD_1 (n, Cp, Ci, P, Pinv, Len, slen, S, Control, Info, C) ;
00189 
00190     /* --------------------------------------------------------------------- */
00191     /* free the workspace */
00192     /* --------------------------------------------------------------------- */
00193 
00194     amesos_camd_free (Rp) ;
00195     amesos_camd_free (Ri) ;
00196     amesos_camd_free (Len) ;
00197     amesos_camd_free (Pinv) ;
00198     amesos_camd_free (S) ;
00199     if (info) Info [CAMD_STATUS] = status ;
00200     return (status) ;     /* successful ordering */
00201 }
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines