|
5164
|
1 /* ========================================================================= */ |
|
|
2 /* === AMD_order =========================================================== */ |
|
|
3 /* ========================================================================= */ |
|
|
4 |
|
|
5 /* ------------------------------------------------------------------------- */ |
|
|
6 /* AMD Version 1.1 (Jan. 21, 2004), Copyright (c) 2004 by Timothy A. Davis, */ |
|
|
7 /* Patrick R. Amestoy, and Iain S. Duff. See ../README for License. */ |
|
|
8 /* email: davis@cise.ufl.edu CISE Department, Univ. of Florida. */ |
|
|
9 /* web: http://www.cise.ufl.edu/research/sparse/amd */ |
|
|
10 /* ------------------------------------------------------------------------- */ |
|
|
11 |
|
|
12 /* User-callable AMD minimum degree ordering routine. See amd.h for |
|
|
13 * documentation. |
|
|
14 */ |
|
|
15 |
|
|
16 #include "amd_internal.h" |
|
|
17 |
|
|
18 GLOBAL Int AMD_order |
|
|
19 ( |
|
|
20 Int n, |
|
|
21 const Int Ap [ ], |
|
|
22 const Int Ai [ ], |
|
|
23 Int P [ ], |
|
|
24 double Control [ ], |
|
|
25 double Info [ ] |
|
|
26 ) |
|
|
27 { |
|
|
28 Int slen, *Len, *S, nz, nzaat, i, *Pinv, info ; |
|
|
29 |
|
|
30 #ifndef NDEBUG |
|
|
31 AMD_debug_init ("amd") ; |
|
|
32 #endif |
|
|
33 |
|
|
34 /* clear the Info array, if it exists */ |
|
|
35 info = Info != (double *) NULL ; |
|
|
36 if (info) |
|
|
37 { |
|
|
38 for (i = 0 ; i < AMD_INFO ; i++) |
|
|
39 { |
|
|
40 Info [i] = EMPTY ; |
|
|
41 } |
|
|
42 Info [AMD_N] = n ; |
|
|
43 Info [AMD_STATUS] = AMD_OK ; |
|
|
44 } |
|
|
45 |
|
|
46 /* make sure inputs exist and n is >= 0 */ |
|
|
47 if (Ai == (Int *) NULL || Ap == (Int *) NULL || P == (Int *) NULL || n < 0) |
|
|
48 { |
|
|
49 if (info) Info [AMD_STATUS] = AMD_INVALID ; |
|
|
50 return (AMD_INVALID) ; /* arguments are invalid */ |
|
|
51 } |
|
|
52 |
|
|
53 if (n == 0) |
|
|
54 { |
|
|
55 return (AMD_OK) ; /* n is 0 so there's nothing to do */ |
|
|
56 } |
|
|
57 |
|
|
58 nz = Ap [n] ; |
|
|
59 if (info) |
|
|
60 { |
|
|
61 Info [AMD_NZ] = nz ; |
|
|
62 } |
|
|
63 if (nz < 0) |
|
|
64 { |
|
|
65 if (info) Info [AMD_STATUS] = AMD_INVALID ; |
|
|
66 return (AMD_INVALID) ; |
|
|
67 } |
|
|
68 |
|
|
69 /* Avoid integer overflow in memory size calculations. The space required |
|
|
70 * by AMD is at most 2.4nz + 8n for S, and n for Len. |
|
|
71 * Note nz - n <= nzaat <= 2*nz, below. */ |
|
|
72 if ((2.4 * (double) nz + 8 * (double) n) > (double) Int_MAX / sizeof (Int)) |
|
|
73 { |
|
|
74 /* :: int overflow :: */ |
|
|
75 if (info) Info [AMD_STATUS] = AMD_OUT_OF_MEMORY ; |
|
|
76 return (AMD_OUT_OF_MEMORY) ; |
|
|
77 } |
|
|
78 |
|
|
79 if (!AMD_valid (n, n, Ap, Ai)) |
|
|
80 { |
|
|
81 if (info) Info [AMD_STATUS] = AMD_INVALID ; |
|
|
82 return (AMD_INVALID) ; /* matrix is invalid */ |
|
|
83 } |
|
|
84 |
|
|
85 /* --------------------------------------------------------------------- */ |
|
|
86 /* determine the symmetry and count off-diagonal nonzeros in A+A' */ |
|
|
87 /* --------------------------------------------------------------------- */ |
|
|
88 |
|
|
89 /* allocate size-n integer workspace */ |
|
|
90 Len = (Int *) ALLOCATE (n * sizeof (Int)) ; |
|
|
91 if (!Len) |
|
|
92 { |
|
|
93 /* :: out of memory :: */ |
|
|
94 if (info) Info [AMD_STATUS] = AMD_OUT_OF_MEMORY ; |
|
|
95 return (AMD_OUT_OF_MEMORY) ; |
|
|
96 } |
|
|
97 nzaat = AMD_aat (n, Ap, Ai, Len, P, Info) ; |
|
|
98 AMD_DEBUG1 (("nzaat: "ID"\n", nzaat)) ; |
|
|
99 ASSERT (nz-n <= nzaat && nzaat <= 2*nz) ; |
|
|
100 |
|
|
101 /* --------------------------------------------------------------------- */ |
|
|
102 /* allocate workspace for matrix, elbow room, and 7 size-n vectors */ |
|
|
103 /* --------------------------------------------------------------------- */ |
|
|
104 |
|
|
105 slen = (nzaat + nzaat/5 + n) + 7*n ; |
|
|
106 if (info) |
|
|
107 { |
|
|
108 /* memory usage (Len and S), in bytes. */ |
|
|
109 Info [AMD_MEMORY] = ((double) slen + n) * sizeof (Int) ; |
|
|
110 } |
|
|
111 S = (Int *) ALLOCATE (slen * sizeof (Int)) ; |
|
|
112 AMD_DEBUG1 ((" S "ID" Len "ID" n "ID" nzaat "ID" slen "ID"\n", |
|
|
113 (Int) S, (Int) Len, n, nzaat, slen)) ; |
|
|
114 if (S == (Int *) NULL) |
|
|
115 { |
|
|
116 /* :: out of memory :: */ |
|
|
117 FREE (Len) ; |
|
|
118 if (Info != (double *) NULL) Info [AMD_STATUS] = AMD_OUT_OF_MEMORY ; |
|
|
119 return (AMD_OUT_OF_MEMORY) ; |
|
|
120 } |
|
|
121 |
|
|
122 /* allocate space from S for Pinv */ |
|
|
123 Pinv = S + slen - n ; |
|
|
124 slen -= n ; |
|
|
125 |
|
|
126 /* --------------------------------------------------------------------- */ |
|
|
127 /* order the matrix */ |
|
|
128 /* --------------------------------------------------------------------- */ |
|
|
129 |
|
|
130 AMD_1 (n, Ap, Ai, P, Pinv, Len, slen, S, Control, Info) ; |
|
|
131 |
|
|
132 /* --------------------------------------------------------------------- */ |
|
|
133 /* free the workspace */ |
|
|
134 /* --------------------------------------------------------------------- */ |
|
|
135 |
|
|
136 FREE (Len) ; |
|
|
137 FREE (S) ; |
|
|
138 return (AMD_OK) ; /* successful ordering */ |
|
|
139 } |
