1 /* ========================================================================== */
2 /* === UMF_init_front ======================================================= */
3 /* ========================================================================== */
4
5 /* -------------------------------------------------------------------------- */
6 /* Copyright (c) 2005-2012 by Timothy A. Davis, http://www.suitesparse.com. */
7 /* All Rights Reserved. See ../Doc/License.txt for License. */
8 /* -------------------------------------------------------------------------- */
9
10 #include "umf_internal.h"
11 #include "umf_init_front.h"
12 #include "umf_grow_front.h"
13
14 /* ========================================================================== */
15 /* === zero_init_front ====================================================== */
16 /* ========================================================================== */
17
18 /* Set the initial frontal matrix to zero. */
19
zero_init_front(Int m,Int n,Entry * Fcblock,Int d)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
UMF_init_front(NumericType * Numeric,WorkType * Work)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, 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 }
268