|
alpar@1
|
1 |
/* ========================================================================= */
|
|
alpar@1
|
2 |
/* === AMD_preprocess ====================================================== */
|
|
alpar@1
|
3 |
/* ========================================================================= */
|
|
alpar@1
|
4 |
|
|
alpar@1
|
5 |
/* ------------------------------------------------------------------------- */
|
|
alpar@1
|
6 |
/* AMD, Copyright (c) Timothy A. Davis, */
|
|
alpar@1
|
7 |
/* Patrick R. Amestoy, and Iain S. Duff. See ../README.txt for License. */
|
|
alpar@1
|
8 |
/* email: davis at cise.ufl.edu CISE Department, Univ. of Florida. */
|
|
alpar@1
|
9 |
/* web: http://www.cise.ufl.edu/research/sparse/amd */
|
|
alpar@1
|
10 |
/* ------------------------------------------------------------------------- */
|
|
alpar@1
|
11 |
|
|
alpar@1
|
12 |
/* Sorts, removes duplicate entries, and transposes from the nonzero pattern of
|
|
alpar@1
|
13 |
* a column-form matrix A, to obtain the matrix R. The input matrix can have
|
|
alpar@1
|
14 |
* duplicate entries and/or unsorted columns (AMD_valid (n,Ap,Ai) must not be
|
|
alpar@1
|
15 |
* AMD_INVALID).
|
|
alpar@1
|
16 |
*
|
|
alpar@1
|
17 |
* This input condition is NOT checked. This routine is not user-callable.
|
|
alpar@1
|
18 |
*/
|
|
alpar@1
|
19 |
|
|
alpar@1
|
20 |
#include "amd_internal.h"
|
|
alpar@1
|
21 |
|
|
alpar@1
|
22 |
/* ========================================================================= */
|
|
alpar@1
|
23 |
/* === AMD_preprocess ====================================================== */
|
|
alpar@1
|
24 |
/* ========================================================================= */
|
|
alpar@1
|
25 |
|
|
alpar@1
|
26 |
/* AMD_preprocess does not check its input for errors or allocate workspace.
|
|
alpar@1
|
27 |
* On input, the condition (AMD_valid (n,n,Ap,Ai) != AMD_INVALID) must hold.
|
|
alpar@1
|
28 |
*/
|
|
alpar@1
|
29 |
|
|
alpar@1
|
30 |
GLOBAL void AMD_preprocess
|
|
alpar@1
|
31 |
(
|
|
alpar@1
|
32 |
Int n, /* input matrix: A is n-by-n */
|
|
alpar@1
|
33 |
const Int Ap [ ], /* size n+1 */
|
|
alpar@1
|
34 |
const Int Ai [ ], /* size nz = Ap [n] */
|
|
alpar@1
|
35 |
|
|
alpar@1
|
36 |
/* output matrix R: */
|
|
alpar@1
|
37 |
Int Rp [ ], /* size n+1 */
|
|
alpar@1
|
38 |
Int Ri [ ], /* size nz (or less, if duplicates present) */
|
|
alpar@1
|
39 |
|
|
alpar@1
|
40 |
Int W [ ], /* workspace of size n */
|
|
alpar@1
|
41 |
Int Flag [ ] /* workspace of size n */
|
|
alpar@1
|
42 |
)
|
|
alpar@1
|
43 |
{
|
|
alpar@1
|
44 |
|
|
alpar@1
|
45 |
/* --------------------------------------------------------------------- */
|
|
alpar@1
|
46 |
/* local variables */
|
|
alpar@1
|
47 |
/* --------------------------------------------------------------------- */
|
|
alpar@1
|
48 |
|
|
alpar@1
|
49 |
Int i, j, p, p2 ;
|
|
alpar@1
|
50 |
|
|
alpar@1
|
51 |
ASSERT (AMD_valid (n, n, Ap, Ai) != AMD_INVALID) ;
|
|
alpar@1
|
52 |
|
|
alpar@1
|
53 |
/* --------------------------------------------------------------------- */
|
|
alpar@1
|
54 |
/* count the entries in each row of A (excluding duplicates) */
|
|
alpar@1
|
55 |
/* --------------------------------------------------------------------- */
|
|
alpar@1
|
56 |
|
|
alpar@1
|
57 |
for (i = 0 ; i < n ; i++)
|
|
alpar@1
|
58 |
{
|
|
alpar@1
|
59 |
W [i] = 0 ; /* # of nonzeros in row i (excl duplicates) */
|
|
alpar@1
|
60 |
Flag [i] = EMPTY ; /* Flag [i] = j if i appears in column j */
|
|
alpar@1
|
61 |
}
|
|
alpar@1
|
62 |
for (j = 0 ; j < n ; j++)
|
|
alpar@1
|
63 |
{
|
|
alpar@1
|
64 |
p2 = Ap [j+1] ;
|
|
alpar@1
|
65 |
for (p = Ap [j] ; p < p2 ; p++)
|
|
alpar@1
|
66 |
{
|
|
alpar@1
|
67 |
i = Ai [p] ;
|
|
alpar@1
|
68 |
if (Flag [i] != j)
|
|
alpar@1
|
69 |
{
|
|
alpar@1
|
70 |
/* row index i has not yet appeared in column j */
|
|
alpar@1
|
71 |
W [i]++ ; /* one more entry in row i */
|
|
alpar@1
|
72 |
Flag [i] = j ; /* flag row index i as appearing in col j*/
|
|
alpar@1
|
73 |
}
|
|
alpar@1
|
74 |
}
|
|
alpar@1
|
75 |
}
|
|
alpar@1
|
76 |
|
|
alpar@1
|
77 |
/* --------------------------------------------------------------------- */
|
|
alpar@1
|
78 |
/* compute the row pointers for R */
|
|
alpar@1
|
79 |
/* --------------------------------------------------------------------- */
|
|
alpar@1
|
80 |
|
|
alpar@1
|
81 |
Rp [0] = 0 ;
|
|
alpar@1
|
82 |
for (i = 0 ; i < n ; i++)
|
|
alpar@1
|
83 |
{
|
|
alpar@1
|
84 |
Rp [i+1] = Rp [i] + W [i] ;
|
|
alpar@1
|
85 |
}
|
|
alpar@1
|
86 |
for (i = 0 ; i < n ; i++)
|
|
alpar@1
|
87 |
{
|
|
alpar@1
|
88 |
W [i] = Rp [i] ;
|
|
alpar@1
|
89 |
Flag [i] = EMPTY ;
|
|
alpar@1
|
90 |
}
|
|
alpar@1
|
91 |
|
|
alpar@1
|
92 |
/* --------------------------------------------------------------------- */
|
|
alpar@1
|
93 |
/* construct the row form matrix R */
|
|
alpar@1
|
94 |
/* --------------------------------------------------------------------- */
|
|
alpar@1
|
95 |
|
|
alpar@1
|
96 |
/* R = row form of pattern of A */
|
|
alpar@1
|
97 |
for (j = 0 ; j < n ; j++)
|
|
alpar@1
|
98 |
{
|
|
alpar@1
|
99 |
p2 = Ap [j+1] ;
|
|
alpar@1
|
100 |
for (p = Ap [j] ; p < p2 ; p++)
|
|
alpar@1
|
101 |
{
|
|
alpar@1
|
102 |
i = Ai [p] ;
|
|
alpar@1
|
103 |
if (Flag [i] != j)
|
|
alpar@1
|
104 |
{
|
|
alpar@1
|
105 |
/* row index i has not yet appeared in column j */
|
|
alpar@1
|
106 |
Ri [W [i]++] = j ; /* put col j in row i */
|
|
alpar@1
|
107 |
Flag [i] = j ; /* flag row index i as appearing in col j*/
|
|
alpar@1
|
108 |
}
|
|
alpar@1
|
109 |
}
|
|
alpar@1
|
110 |
}
|
|
alpar@1
|
111 |
|
|
alpar@1
|
112 |
#ifndef NDEBUG
|
|
alpar@1
|
113 |
ASSERT (AMD_valid (n, n, Rp, Ri) == AMD_OK) ;
|
|
alpar@1
|
114 |
for (j = 0 ; j < n ; j++)
|
|
alpar@1
|
115 |
{
|
|
alpar@1
|
116 |
ASSERT (W [j] == Rp [j+1]) ;
|
|
alpar@1
|
117 |
}
|
|
alpar@1
|
118 |
#endif
|
|
alpar@1
|
119 |
}
|