1 /* ========================================================================= */
2 /* === AMD_preprocess ====================================================== */
3 /* ========================================================================= */
5 /* ------------------------------------------------------------------------- */
6 /* AMD, Copyright (c) Timothy A. Davis, */
7 /* Patrick R. Amestoy, and Iain S. Duff. See ../README.txt for License. */
8 /* email: davis at cise.ufl.edu CISE Department, Univ. of Florida. */
9 /* web: http://www.cise.ufl.edu/research/sparse/amd */
10 /* ------------------------------------------------------------------------- */
12 /* Sorts, removes duplicate entries, and transposes from the nonzero pattern of
13 * a column-form matrix A, to obtain the matrix R. The input matrix can have
14 * duplicate entries and/or unsorted columns (AMD_valid (n,Ap,Ai) must not be
17 * This input condition is NOT checked. This routine is not user-callable.
20 #include "amd_internal.h"
22 /* ========================================================================= */
23 /* === AMD_preprocess ====================================================== */
24 /* ========================================================================= */
26 /* AMD_preprocess does not check its input for errors or allocate workspace.
27 * On input, the condition (AMD_valid (n,n,Ap,Ai) != AMD_INVALID) must hold.
30 GLOBAL void AMD_preprocess
32 Int n, /* input matrix: A is n-by-n */
33 const Int Ap [ ], /* size n+1 */
34 const Int Ai [ ], /* size nz = Ap [n] */
36 /* output matrix R: */
37 Int Rp [ ], /* size n+1 */
38 Int Ri [ ], /* size nz (or less, if duplicates present) */
40 Int W [ ], /* workspace of size n */
41 Int Flag [ ] /* workspace of size n */
45 /* --------------------------------------------------------------------- */
47 /* --------------------------------------------------------------------- */
51 ASSERT (AMD_valid (n, n, Ap, Ai) != AMD_INVALID) ;
53 /* --------------------------------------------------------------------- */
54 /* count the entries in each row of A (excluding duplicates) */
55 /* --------------------------------------------------------------------- */
57 for (i = 0 ; i < n ; i++)
59 W [i] = 0 ; /* # of nonzeros in row i (excl duplicates) */
60 Flag [i] = EMPTY ; /* Flag [i] = j if i appears in column j */
62 for (j = 0 ; j < n ; j++)
65 for (p = Ap [j] ; p < p2 ; p++)
70 /* row index i has not yet appeared in column j */
71 W [i]++ ; /* one more entry in row i */
72 Flag [i] = j ; /* flag row index i as appearing in col j*/
77 /* --------------------------------------------------------------------- */
78 /* compute the row pointers for R */
79 /* --------------------------------------------------------------------- */
82 for (i = 0 ; i < n ; i++)
84 Rp [i+1] = Rp [i] + W [i] ;
86 for (i = 0 ; i < n ; i++)
92 /* --------------------------------------------------------------------- */
93 /* construct the row form matrix R */
94 /* --------------------------------------------------------------------- */
96 /* R = row form of pattern of A */
97 for (j = 0 ; j < n ; j++)
100 for (p = Ap [j] ; p < p2 ; p++)
105 /* row index i has not yet appeared in column j */
106 Ri [W [i]++] = j ; /* put col j in row i */
107 Flag [i] = j ; /* flag row index i as appearing in col j*/
113 ASSERT (AMD_valid (n, n, Rp, Ri) == AMD_OK) ;
114 for (j = 0 ; j < n ; j++)
116 ASSERT (W [j] == Rp [j+1]) ;