Amesos Package Browser (Single Doxygen Collection) Development
amesos_amd_preprocess.c
Go to the documentation of this file.
00001 /* ========================================================================= */
00002 /* === AMD_preprocess ====================================================== */
00003 /* ========================================================================= */
00004 
00005 /* ------------------------------------------------------------------------- */
00006 /* AMD, Copyright (c) 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 /* Sorts, removes duplicate entries, and transposes from the nonzero pattern of
00013  * a column-form matrix A, to obtain the matrix R.  The input matrix can have
00014  * duplicate entries and/or unsorted columns (AMD_valid (n,Ap,Ai) must not be
00015  * AMD_INVALID).
00016  *
00017  * This input condition is NOT checked.  This routine is not user-callable.
00018  */
00019 
00020 #include "amesos_amd_internal.h"
00021 
00022 /* ========================================================================= */
00023 /* === AMD_preprocess ====================================================== */
00024 /* ========================================================================= */
00025 
00026 /* AMD_preprocess does not check its input for errors or allocate workspace.
00027  * On input, the condition (AMD_valid (n,n,Ap,Ai) != AMD_INVALID) must hold.
00028  */
00029 
00030 GLOBAL void AMD_preprocess
00031 (
00032     Int n,    /* input matrix: A is n-by-n */
00033     const Int Ap [ ], /* size n+1 */
00034     const Int Ai [ ], /* size nz = Ap [n] */
00035 
00036     /* output matrix R: */
00037     Int Rp [ ],   /* size n+1 */
00038     Int Ri [ ],   /* size nz (or less, if duplicates present) */
00039 
00040     Int W [ ],    /* workspace of size n */
00041     Int Flag [ ]  /* workspace of size n */
00042 )
00043 {
00044 
00045     /* --------------------------------------------------------------------- */
00046     /* local variables */
00047     /* --------------------------------------------------------------------- */
00048 
00049     Int i, j, p, p2 ;
00050 
00051     ASSERT (AMD_valid (n, n, Ap, Ai) != AMD_INVALID) ;
00052 
00053     /* --------------------------------------------------------------------- */
00054     /* count the entries in each row of A (excluding duplicates) */
00055     /* --------------------------------------------------------------------- */
00056 
00057     for (i = 0 ; i < n ; i++)
00058     {
00059   W [i] = 0 ;   /* # of nonzeros in row i (excl duplicates) */
00060   Flag [i] = EMPTY ;  /* Flag [i] = j if i appears in column j */
00061     }
00062     for (j = 0 ; j < n ; j++)
00063     {
00064   p2 = Ap [j+1] ;
00065   for (p = Ap [j] ; p < p2 ; p++)
00066   {
00067       i = Ai [p] ;
00068       if (Flag [i] != j)
00069       {
00070     /* row index i has not yet appeared in column j */
00071     W [i]++ ;     /* one more entry in row i */
00072     Flag [i] = j ;      /* flag row index i as appearing in col j*/
00073       }
00074   }
00075     }
00076 
00077     /* --------------------------------------------------------------------- */
00078     /* compute the row pointers for R */
00079     /* --------------------------------------------------------------------- */
00080 
00081     Rp [0] = 0 ;
00082     for (i = 0 ; i < n ; i++)
00083     {
00084   Rp [i+1] = Rp [i] + W [i] ;
00085     }
00086     for (i = 0 ; i < n ; i++)
00087     {
00088   W [i] = Rp [i] ;
00089   Flag [i] = EMPTY ;
00090     }
00091 
00092     /* --------------------------------------------------------------------- */
00093     /* construct the row form matrix R */
00094     /* --------------------------------------------------------------------- */
00095 
00096     /* R = row form of pattern of A */
00097     for (j = 0 ; j < n ; j++)
00098     {
00099   p2 = Ap [j+1] ;
00100   for (p = Ap [j] ; p < p2 ; p++)
00101   {
00102       i = Ai [p] ;
00103       if (Flag [i] != j)
00104       {
00105     /* row index i has not yet appeared in column j */
00106     Ri [W [i]++] = j ;  /* put col j in row i */
00107     Flag [i] = j ;      /* flag row index i as appearing in col j*/
00108       }
00109   }
00110     }
00111 
00112 #ifndef NDEBUG
00113     ASSERT (AMD_valid (n, n, Rp, Ri) == AMD_OK) ;
00114     for (j = 0 ; j < n ; j++)
00115     {
00116   ASSERT (W [j] == Rp [j+1]) ;
00117     }
00118 #endif
00119 }
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines