Mercurial > octave-nkf
comparison liboctave/UMFPACK/UMFPACK/Source/umf_init_front.c @ 5164:57077d0ddc8e
[project @ 2005-02-25 19:55:24 by jwe]
author | jwe |
---|---|
date | Fri, 25 Feb 2005 19:55:28 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
5163:9f3299378193 | 5164:57077d0ddc8e |
---|---|
1 /* ========================================================================== */ | |
2 /* === UMF_init_front ======================================================= */ | |
3 /* ========================================================================== */ | |
4 | |
5 /* -------------------------------------------------------------------------- */ | |
6 /* UMFPACK Version 4.4, Copyright (c) 2005 by Timothy A. Davis. CISE Dept, */ | |
7 /* Univ. of Florida. All Rights Reserved. See ../Doc/License for License. */ | |
8 /* web: http://www.cise.ufl.edu/research/sparse/umfpack */ | |
9 /* -------------------------------------------------------------------------- */ | |
10 | |
11 #include "umf_internal.h" | |
12 #include "umf_grow_front.h" | |
13 | |
14 /* ========================================================================== */ | |
15 /* === zero_init_front ====================================================== */ | |
16 /* ========================================================================== */ | |
17 | |
18 /* Set the initial frontal matrix to zero. */ | |
19 | |
20 PRIVATE void zero_init_front (Int m, Int n, Entry *Fcblock, Int d) | |
21 { | |
22 Int i, j ; | |
23 Entry *F, *Fj = Fcblock ; | |
24 for (j = 0 ; j < m ; j++) | |
25 { | |
26 F = Fj ; | |
27 Fj += d ; | |
28 for (i = 0 ; i < n ; i++) | |
29 { | |
30 /* CLEAR (Fcblock [i + j*d]) ; */ | |
31 CLEAR (*F) ; | |
32 F++ ; | |
33 } | |
34 } | |
35 } | |
36 | |
37 /* ========================================================================== */ | |
38 /* === UMF_init_front ======================================================= */ | |
39 /* ========================================================================== */ | |
40 | |
41 GLOBAL Int UMF_init_front | |
42 ( | |
43 NumericType *Numeric, | |
44 WorkType *Work | |
45 ) | |
46 { | |
47 /* ---------------------------------------------------------------------- */ | |
48 /* local variables */ | |
49 /* ---------------------------------------------------------------------- */ | |
50 | |
51 Int i, j, fnr_curr, row, col, *Frows, *Fcols, | |
52 *Fcpos, *Frpos, fncols, fnrows, *Wrow, fnr2, fnc2, rrdeg, ccdeg, *Wm, | |
53 fnrows_extended ; | |
54 Entry *Fcblock, *Fl, *Wy, *Wx ; | |
55 | |
56 /* ---------------------------------------------------------------------- */ | |
57 /* get current frontal matrix and check for frontal growth */ | |
58 /* ---------------------------------------------------------------------- */ | |
59 | |
60 #ifndef NDEBUG | |
61 DEBUG0 (("INIT FRONT\n")) ; | |
62 DEBUG1 (("CURR before init:\n")) ; | |
63 UMF_dump_current_front (Numeric, Work, FALSE) ; | |
64 #endif | |
65 if (Work->do_grow) | |
66 { | |
67 fnr2 = UMF_FRONTAL_GROWTH * Work->fnrows_new + 2 ; | |
68 fnc2 = UMF_FRONTAL_GROWTH * Work->fncols_new + 2 ; | |
69 if (!UMF_grow_front (Numeric, fnr2, fnc2, Work, | |
70 Work->pivrow_in_front ? 2 : 0)) | |
71 { | |
72 /* :: out of memory in umf_init_front :: */ | |
73 DEBUGm4 (("out of memory: init front\n")) ; | |
74 return (FALSE) ; | |
75 } | |
76 } | |
77 #ifndef NDEBUG | |
78 DEBUG1 (("CURR after grow:\n")) ; | |
79 UMF_dump_current_front (Numeric, Work, FALSE) ; | |
80 DEBUG1 (("fnrows new "ID" fncols new "ID"\n", | |
81 Work->fnrows_new, Work->fncols_new)) ; | |
82 #endif | |
83 ASSERT (Work->fnpiv == 0) ; | |
84 fnr_curr = Work->fnr_curr ; | |
85 ASSERT (Work->fnrows_new + 1 <= fnr_curr) ; | |
86 ASSERT (Work->fncols_new + 1 <= Work->fnc_curr) ; | |
87 ASSERT (fnr_curr >= 0) ; | |
88 ASSERT (fnr_curr % 2 == 1) ; | |
89 | |
90 /* ---------------------------------------------------------------------- */ | |
91 /* get parameters */ | |
92 /* ---------------------------------------------------------------------- */ | |
93 | |
94 /* current front is defined by pivot row and column */ | |
95 | |
96 Frows = Work->Frows ; | |
97 Fcols = Work->Fcols ; | |
98 Frpos = Work->Frpos ; | |
99 Fcpos = Work->Fcpos ; | |
100 | |
101 Work->fnzeros = 0 ; | |
102 | |
103 ccdeg = Work->ccdeg ; | |
104 rrdeg = Work->rrdeg ; | |
105 | |
106 fnrows = Work->fnrows ; | |
107 fncols = Work->fncols ; | |
108 | |
109 /* if both pivrow and pivcol are in front, then we extend the old one */ | |
110 /* in UMF_extend_front, rather than starting a new one here. */ | |
111 ASSERT (! (Work->pivrow_in_front && Work->pivcol_in_front)) ; | |
112 | |
113 /* ---------------------------------------------------------------------- */ | |
114 /* place pivot column pattern in frontal matrix */ | |
115 /* ---------------------------------------------------------------------- */ | |
116 | |
117 Fl = Work->Flblock ; | |
118 | |
119 if (Work->pivcol_in_front) | |
120 { | |
121 /* Append the pivot column extension. | |
122 * Note that all we need to do is increment the size, since the | |
123 * candidate pivot column pattern is already in place in | |
124 * Frows [0 ... fnrows-1] (the old pattern), and | |
125 * Frows [fnrows ... fnrows + Work->ccdeg - 1] (the new | |
126 * pattern). Frpos is also properly defined. */ | |
127 /* make a list of the new rows to scan */ | |
128 Work->fscan_row = fnrows ; /* only scan the new rows */ | |
129 Work->NewRows = Work->Wrp ; | |
130 Wy = Work->Wy ; | |
131 for (i = 0 ; i < fnrows ; i++) | |
132 { | |
133 Fl [i] = Wy [i] ; | |
134 } | |
135 fnrows_extended = fnrows + ccdeg ; | |
136 for (i = fnrows ; i < fnrows_extended ; i++) | |
137 { | |
138 Fl [i] = Wy [i] ; | |
139 /* flip the row index, since Wrp must be < 0 */ | |
140 row = Frows [i] ; | |
141 Work->NewRows [i] = FLIP (row) ; | |
142 } | |
143 fnrows = fnrows_extended ; | |
144 } | |
145 else | |
146 { | |
147 /* this is a completely new column */ | |
148 Work->fscan_row = 0 ; /* scan all the rows */ | |
149 Work->NewRows = Frows ; | |
150 Wm = Work->Wm ; | |
151 Wx = Work->Wx ; | |
152 for (i = 0 ; i < ccdeg ; i++) | |
153 { | |
154 Fl [i] = Wx [i] ; | |
155 row = Wm [i] ; | |
156 Frows [i] = row ; | |
157 Frpos [row] = i ; | |
158 } | |
159 fnrows = ccdeg ; | |
160 } | |
161 | |
162 Work->fnrows = fnrows ; | |
163 | |
164 #ifndef NDEBUG | |
165 DEBUG3 (("New Pivot col "ID" now in front, length "ID"\n", | |
166 Work->pivcol, fnrows)) ; | |
167 for (i = 0 ; i < fnrows ; i++) | |
168 { | |
169 DEBUG4 ((" "ID": row "ID"\n", i, Frows [i])) ; | |
170 ASSERT (Frpos [Frows [i]] == i) ; | |
171 } | |
172 #endif | |
173 | |
174 /* ---------------------------------------------------------------------- */ | |
175 /* place pivot row pattern in frontal matrix */ | |
176 /* ---------------------------------------------------------------------- */ | |
177 | |
178 Wrow = Work->Wrow ; | |
179 if (Work->pivrow_in_front) | |
180 { | |
181 /* append the pivot row extension */ | |
182 Work->fscan_col = fncols ; /* only scan the new columns */ | |
183 Work->NewCols = Work->Wp ; | |
184 #ifndef NDEBUG | |
185 for (j = 0 ; j < fncols ; j++) | |
186 { | |
187 col = Fcols [j] ; | |
188 ASSERT (col >= 0 && col < Work->n_col) ; | |
189 ASSERT (Fcpos [col] == j * fnr_curr) ; | |
190 } | |
191 #endif | |
192 /* Wrow == Fcol for the IN_IN case, and for the OUT_IN case when | |
193 * the pivrow [IN][IN] happens to be the same as pivrow [OUT][IN]. | |
194 * See UMF_local_search for more details. */ | |
195 ASSERT (IMPLIES (Work->pivcol_in_front, Wrow == Fcols)) ; | |
196 if (Wrow == Fcols) | |
197 { | |
198 for (j = fncols ; j < rrdeg ; j++) | |
199 { | |
200 col = Wrow [j] ; | |
201 /* Fcols [j] = col ; not needed */ | |
202 /* flip the col index, since Wp must be < 0 */ | |
203 Work->NewCols [j] = FLIP (col) ; | |
204 Fcpos [col] = j * fnr_curr ; | |
205 } | |
206 } | |
207 else | |
208 { | |
209 for (j = fncols ; j < rrdeg ; j++) | |
210 { | |
211 col = Wrow [j] ; | |
212 Fcols [j] = col ; | |
213 /* flip the col index, since Wp must be < 0 */ | |
214 Work->NewCols [j] = FLIP (col) ; | |
215 Fcpos [col] = j * fnr_curr ; | |
216 } | |
217 } | |
218 } | |
219 else | |
220 { | |
221 /* this is a completely new row */ | |
222 Work->fscan_col = 0 ; /* scan all the columns */ | |
223 Work->NewCols = Fcols ; | |
224 for (j = 0 ; j < rrdeg ; j++) | |
225 { | |
226 col = Wrow [j] ; | |
227 Fcols [j] = col ; | |
228 Fcpos [col] = j * fnr_curr ; | |
229 } | |
230 } | |
231 | |
232 DEBUGm1 (("rrdeg "ID" fncols "ID"\n", rrdeg, fncols)) ; | |
233 fncols = rrdeg ; | |
234 Work->fncols = fncols ; | |
235 | |
236 /* ---------------------------------------------------------------------- */ | |
237 /* clear the frontal matrix */ | |
238 /* ---------------------------------------------------------------------- */ | |
239 | |
240 ASSERT (fnrows == Work->fnrows_new + 1) ; | |
241 ASSERT (fncols == Work->fncols_new + 1) ; | |
242 | |
243 Fcblock = Work->Fcblock ; | |
244 ASSERT (Fcblock != (Entry *) NULL) ; | |
245 | |
246 zero_init_front (fncols, fnrows, Fcblock, fnr_curr) ; | |
247 | |
248 #ifndef NDEBUG | |
249 DEBUG3 (("New Pivot row "ID" now in front, length "ID" fnr_curr "ID"\n", | |
250 Work->pivrow, fncols, fnr_curr)) ; | |
251 for (j = 0 ; j < fncols ; j++) | |
252 { | |
253 DEBUG4 (("col "ID" position "ID"\n", j, Fcols [j])) ; | |
254 ASSERT (Fcpos [Fcols [j]] == j * fnr_curr) ; | |
255 } | |
256 #endif | |
257 | |
258 /* ---------------------------------------------------------------------- */ | |
259 /* current workspace usage: */ | |
260 /* ---------------------------------------------------------------------- */ | |
261 | |
262 /* Fcblock [0..fnr_curr-1, 0..fnc_curr-1]: space for the new frontal | |
263 * matrix. Fcblock (i,j) is located at Fcblock [i+j*fnr_curr] */ | |
264 | |
265 return (TRUE) ; | |
266 | |
267 } |