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