|
1 /* ========================================================================= */ |
|
2 /* === AMD_preprocess ====================================================== */ |
|
3 /* ========================================================================= */ |
|
4 |
|
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 /* ------------------------------------------------------------------------- */ |
|
11 |
|
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 |
|
15 * AMD_INVALID). |
|
16 * |
|
17 * This input condition is NOT checked. This routine is not user-callable. |
|
18 */ |
|
19 |
|
20 #include "amd_internal.h" |
|
21 |
|
22 /* ========================================================================= */ |
|
23 /* === AMD_preprocess ====================================================== */ |
|
24 /* ========================================================================= */ |
|
25 |
|
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. |
|
28 */ |
|
29 |
|
30 GLOBAL void AMD_preprocess |
|
31 ( |
|
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] */ |
|
35 |
|
36 /* output matrix R: */ |
|
37 Int Rp [ ], /* size n+1 */ |
|
38 Int Ri [ ], /* size nz (or less, if duplicates present) */ |
|
39 |
|
40 Int W [ ], /* workspace of size n */ |
|
41 Int Flag [ ] /* workspace of size n */ |
|
42 ) |
|
43 { |
|
44 |
|
45 /* --------------------------------------------------------------------- */ |
|
46 /* local variables */ |
|
47 /* --------------------------------------------------------------------- */ |
|
48 |
|
49 Int i, j, p, p2 ; |
|
50 |
|
51 ASSERT (AMD_valid (n, n, Ap, Ai) != AMD_INVALID) ; |
|
52 |
|
53 /* --------------------------------------------------------------------- */ |
|
54 /* count the entries in each row of A (excluding duplicates) */ |
|
55 /* --------------------------------------------------------------------- */ |
|
56 |
|
57 for (i = 0 ; i < n ; i++) |
|
58 { |
|
59 W [i] = 0 ; /* # of nonzeros in row i (excl duplicates) */ |
|
60 Flag [i] = EMPTY ; /* Flag [i] = j if i appears in column j */ |
|
61 } |
|
62 for (j = 0 ; j < n ; j++) |
|
63 { |
|
64 p2 = Ap [j+1] ; |
|
65 for (p = Ap [j] ; p < p2 ; p++) |
|
66 { |
|
67 i = Ai [p] ; |
|
68 if (Flag [i] != j) |
|
69 { |
|
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*/ |
|
73 } |
|
74 } |
|
75 } |
|
76 |
|
77 /* --------------------------------------------------------------------- */ |
|
78 /* compute the row pointers for R */ |
|
79 /* --------------------------------------------------------------------- */ |
|
80 |
|
81 Rp [0] = 0 ; |
|
82 for (i = 0 ; i < n ; i++) |
|
83 { |
|
84 Rp [i+1] = Rp [i] + W [i] ; |
|
85 } |
|
86 for (i = 0 ; i < n ; i++) |
|
87 { |
|
88 W [i] = Rp [i] ; |
|
89 Flag [i] = EMPTY ; |
|
90 } |
|
91 |
|
92 /* --------------------------------------------------------------------- */ |
|
93 /* construct the row form matrix R */ |
|
94 /* --------------------------------------------------------------------- */ |
|
95 |
|
96 /* R = row form of pattern of A */ |
|
97 for (j = 0 ; j < n ; j++) |
|
98 { |
|
99 p2 = Ap [j+1] ; |
|
100 for (p = Ap [j] ; p < p2 ; p++) |
|
101 { |
|
102 i = Ai [p] ; |
|
103 if (Flag [i] != j) |
|
104 { |
|
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*/ |
|
108 } |
|
109 } |
|
110 } |
|
111 |
|
112 #ifndef NDEBUG |
|
113 ASSERT (AMD_valid (n, n, Rp, Ri) == AMD_OK) ; |
|
114 for (j = 0 ; j < n ; j++) |
|
115 { |
|
116 ASSERT (W [j] == Rp [j+1]) ; |
|
117 } |
|
118 #endif |
|
119 } |