5164
|
1 /* ========================================================================== */ |
|
2 /* === umfpack_get_symbolic ================================================= */ |
|
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 int umfpack_di_get_symbolic |
|
12 ( |
|
13 int *n_row, |
|
14 int *n_col, |
|
15 int *n1, |
|
16 int *nz, |
|
17 int *nfr, |
|
18 int *nchains, |
|
19 int P [ ], |
|
20 int Q [ ], |
|
21 int Front_npivcol [ ], |
|
22 int Front_parent [ ], |
|
23 int Front_1strow [ ], |
|
24 int Front_leftmostdesc [ ], |
|
25 int Chain_start [ ], |
|
26 int Chain_maxrows [ ], |
|
27 int Chain_maxcols [ ], |
|
28 void *Symbolic |
|
29 ) ; |
|
30 |
|
31 long umfpack_dl_get_symbolic |
|
32 ( |
|
33 long *n_row, |
|
34 long *n_col, |
|
35 long *n1, |
|
36 long *nz, |
|
37 long *nfr, |
|
38 long *nchains, |
|
39 long P [ ], |
|
40 long Q [ ], |
|
41 long Front_npivcol [ ], |
|
42 long Front_parent [ ], |
|
43 long Front_1strow [ ], |
|
44 long Front_leftmostdesc [ ], |
|
45 long Chain_start [ ], |
|
46 long Chain_maxrows [ ], |
|
47 long Chain_maxcols [ ], |
|
48 void *Symbolic |
|
49 ) ; |
|
50 |
|
51 int umfpack_zi_get_symbolic |
|
52 ( |
|
53 int *n_row, |
|
54 int *n_col, |
|
55 int *n1, |
|
56 int *nz, |
|
57 int *nfr, |
|
58 int *nchains, |
|
59 int P [ ], |
|
60 int Q [ ], |
|
61 int Front_npivcol [ ], |
|
62 int Front_parent [ ], |
|
63 int Front_1strow [ ], |
|
64 int Front_leftmostdesc [ ], |
|
65 int Chain_start [ ], |
|
66 int Chain_maxrows [ ], |
|
67 int Chain_maxcols [ ], |
|
68 void *Symbolic |
|
69 ) ; |
|
70 |
|
71 long umfpack_zl_get_symbolic |
|
72 ( |
|
73 long *n_row, |
|
74 long *n_col, |
|
75 long *n1, |
|
76 long *nz, |
|
77 long *nfr, |
|
78 long *nchains, |
|
79 long P [ ], |
|
80 long Q [ ], |
|
81 long Front_npivcol [ ], |
|
82 long Front_parent [ ], |
|
83 long Front_1strow [ ], |
|
84 long Front_leftmostdesc [ ], |
|
85 long Chain_start [ ], |
|
86 long Chain_maxrows [ ], |
|
87 long Chain_maxcols [ ], |
|
88 void *Symbolic |
|
89 ) ; |
|
90 |
|
91 /* |
|
92 |
|
93 double int Syntax: |
|
94 |
|
95 #include "umfpack.h" |
|
96 int status, n_row, n_col, nz, nfr, nchains, *P, *Q, |
|
97 *Front_npivcol, *Front_parent, *Front_1strow, *Front_leftmostdesc, |
|
98 *Chain_start, *Chain_maxrows, *Chain_maxcols ; |
|
99 void *Symbolic ; |
|
100 status = umfpack_di_get_symbolic (&n_row, &n_col, &nz, &nfr, &nchains, |
|
101 P, Q, Front_npivcol, Front_parent, Front_1strow, |
|
102 Front_leftmostdesc, Chain_start, Chain_maxrows, Chain_maxcols, |
|
103 Symbolic) ; |
|
104 |
|
105 double long Syntax: |
|
106 |
|
107 #include "umfpack.h" |
|
108 long status, n_row, n_col, nz, nfr, nchains, *P, *Q, |
|
109 *Front_npivcol, *Front_parent, *Front_1strow, *Front_leftmostdesc, |
|
110 *Chain_start, *Chain_maxrows, *Chain_maxcols ; |
|
111 void *Symbolic ; |
|
112 status = umfpack_dl_get_symbolic (&n_row, &n_col, &nz, &nfr, &nchains, |
|
113 P, Q, Front_npivcol, Front_parent, Front_1strow, |
|
114 Front_leftmostdesc, Chain_start, Chain_maxrows, Chain_maxcols, |
|
115 Symbolic) ; |
|
116 |
|
117 complex int Syntax: |
|
118 |
|
119 #include "umfpack.h" |
|
120 int status, n_row, n_col, nz, nfr, nchains, *P, *Q, |
|
121 *Front_npivcol, *Front_parent, *Front_1strow, *Front_leftmostdesc, |
|
122 *Chain_start, *Chain_maxrows, *Chain_maxcols ; |
|
123 void *Symbolic ; |
|
124 status = umfpack_zi_get_symbolic (&n_row, &n_col, &nz, &nfr, &nchains, |
|
125 P, Q, Front_npivcol, Front_parent, Front_1strow, |
|
126 Front_leftmostdesc, Chain_start, Chain_maxrows, Chain_maxcols, |
|
127 Symbolic) ; |
|
128 |
|
129 complex long Syntax: |
|
130 |
|
131 #include "umfpack.h" |
|
132 long status, n_row, n_col, nz, nfr, nchains, *P, *Q, |
|
133 *Front_npivcol, *Front_parent, *Front_1strow, *Front_leftmostdesc, |
|
134 *Chain_start, *Chain_maxrows, *Chain_maxcols ; |
|
135 void *Symbolic ; |
|
136 status = umfpack_zl_get_symbolic (&n_row, &n_col, &nz, &nfr, &nchains, |
|
137 P, Q, Front_npivcol, Front_parent, Front_1strow, |
|
138 Front_leftmostdesc, Chain_start, Chain_maxrows, Chain_maxcols, |
|
139 Symbolic) ; |
|
140 |
|
141 Purpose: |
|
142 |
|
143 Copies the contents of the Symbolic object into simple integer arrays |
|
144 accessible to the user. This routine is not needed to factorize and/or |
|
145 solve a sparse linear system using UMFPACK. Note that the output arrays |
|
146 P, Q, Front_npivcol, Front_parent, Front_1strow, Front_leftmostdesc, |
|
147 Chain_start, Chain_maxrows, and Chain_maxcols are not allocated by |
|
148 umfpack_*_get_symbolic; they must exist on input. |
|
149 |
|
150 All output arguments are optional. If any of them are NULL |
|
151 on input, then that part of the symbolic analysis is not copied. You can |
|
152 use this routine to extract just the parts of the symbolic analysis that |
|
153 you want. For example, to retrieve just the column permutation Q, use: |
|
154 |
|
155 #define noI (int *) NULL |
|
156 status = umfpack_di_get_symbolic (noI, noI, noI, noI, noI, noI, noI, |
|
157 Q, noI, noI, noI, noI, noI, noI, noI, Symbolic) ; |
|
158 |
|
159 The only required argument the last one, the pointer to the Symbolic object. |
|
160 |
|
161 The Symbolic object is small. Its size for an n-by-n square matrix varies |
|
162 from 4*n to 13*n, depending on the matrix. The object holds the initial |
|
163 column permutation, the supernodal column elimination tree, and information |
|
164 about each frontal matrix. You can print it with umfpack_*_report_symbolic. |
|
165 |
|
166 Returns: |
|
167 |
|
168 Returns UMFPACK_OK if successful, UMFPACK_ERROR_invalid_Symbolic_object |
|
169 if Symbolic is an invalid object. |
|
170 |
|
171 Arguments: |
|
172 |
|
173 Int *n_row ; Output argument. |
|
174 Int *n_col ; Output argument. |
|
175 |
|
176 The dimensions of the matrix A analyzed by the call to |
|
177 umfpack_*_symbolic that generated the Symbolic object. |
|
178 |
|
179 Int *n1 ; Output argument. |
|
180 |
|
181 The number of pivots with zero Markowitz cost (they have just one entry |
|
182 in the pivot row, or the pivot column, or both). These appear first in |
|
183 the output permutations P and Q. |
|
184 |
|
185 Int *nz ; Output argument. |
|
186 |
|
187 The number of nonzeros in A. |
|
188 |
|
189 Int *nfr ; Output argument. |
|
190 |
|
191 The number of frontal matrices that will be used by umfpack_*_numeric |
|
192 to factorize the matrix A. It is in the range 0 to n_col. |
|
193 |
|
194 Int *nchains ; Output argument. |
|
195 |
|
196 The frontal matrices are related to one another by the supernodal |
|
197 column elimination tree. Each node in this tree is one frontal matrix. |
|
198 The tree is partitioned into a set of disjoint paths, and a frontal |
|
199 matrix chain is one path in this tree. Each chain is factorized using |
|
200 a unifrontal technique, with a single working array that holds each |
|
201 frontal matrix in the chain, one at a time. nchains is in the range |
|
202 0 to nfr. |
|
203 |
|
204 Int P [n_row] ; Output argument. |
|
205 |
|
206 The initial row permutation. If P [k] = i, then this means that |
|
207 row i is the kth row in the pre-ordered matrix. In general, this P is |
|
208 not the same as the final row permutation computed by umfpack_*_numeric. |
|
209 |
|
210 For the unsymmetric strategy, P defines the row-merge order. Let j be |
|
211 the column index of the leftmost nonzero entry in row i of A*Q. Then |
|
212 P defines a sort of the rows according to this value. A row can appear |
|
213 earlier in this ordering if it is aggressively absorbed before it can |
|
214 become a pivot row. If P [k] = i, row i typically will not be the kth |
|
215 pivot row. |
|
216 |
|
217 For the symmetric strategy, P = Q. For the 2-by-2 strategy, P is the |
|
218 row permutation that places large entries on the diagonal of P*A*Q. |
|
219 If no pivoting occurs during numerical factorization, P [k] = i also |
|
220 defines the final permutation of umfpack_*_numeric, for either the |
|
221 symmetric or 2-by-2 strategies. |
|
222 |
|
223 Int Q [n_col] ; Output argument. |
|
224 |
|
225 The initial column permutation. If Q [k] = j, then this means that |
|
226 column j is the kth pivot column in the pre-ordered matrix. Q is |
|
227 not necessarily the same as the final column permutation Q, computed by |
|
228 umfpack_*_numeric. The numeric factorization may reorder the pivot |
|
229 columns within each frontal matrix to reduce fill-in. If the matrix is |
|
230 structurally singular, and if the symmetric or 2-by-2 strategies or |
|
231 used (or if Control [UMFPACK_FIXQ] > 0), then this Q will be the same |
|
232 as the final column permutation computed in umfpack_*_numeric. |
|
233 |
|
234 Int Front_npivcol [n_col+1] ; Output argument. |
|
235 |
|
236 This array should be of size at least n_col+1, in order to guarantee |
|
237 that it will be large enough to hold the output. Only the first nfr+1 |
|
238 entries are used, however. |
|
239 |
|
240 The kth frontal matrix holds Front_npivcol [k] pivot columns. Thus, the |
|
241 first frontal matrix, front 0, is used to factorize the first |
|
242 Front_npivcol [0] columns; these correspond to the original columns |
|
243 Q [0] through Q [Front_npivcol [0]-1]. The next frontal matrix |
|
244 is used to factorize the next Front_npivcol [1] columns, which are thus |
|
245 the original columns Q [Front_npivcol [0]] through |
|
246 Q [Front_npivcol [0] + Front_npivcol [1] - 1], and so on. Columns |
|
247 with no entries at all are put in a placeholder "front", |
|
248 Front_npivcol [nfr]. The sum of Front_npivcol [0..nfr] is equal to |
|
249 n_col. |
|
250 |
|
251 Any modifications that umfpack_*_numeric makes to the initial column |
|
252 permutation are constrained to within each frontal matrix. Thus, for |
|
253 the first frontal matrix, Q [0] through Q [Front_npivcol [0]-1] is some |
|
254 permutation of the columns Q [0] through |
|
255 Q [Front_npivcol [0]-1]. For second frontal matrix, |
|
256 Q [Front_npivcol [0]] through Q [Front_npivcol [0] + Front_npivcol[1]-1] |
|
257 is some permutation of the same portion of Q, and so on. All pivot |
|
258 columns are numerically factorized within the frontal matrix originally |
|
259 determined by the symbolic factorization; there is no delayed pivoting |
|
260 across frontal matrices. |
|
261 |
|
262 Int Front_parent [n_col+1] ; Output argument. |
|
263 |
|
264 This array should be of size at least n_col+1, in order to guarantee |
|
265 that it will be large enough to hold the output. Only the first nfr+1 |
|
266 entries are used, however. |
|
267 |
|
268 Front_parent [0..nfr] holds the supernodal column elimination tree |
|
269 (including the placeholder front nfr, which may be empty). Each node in |
|
270 the tree corresponds to a single frontal matrix. The parent of node f |
|
271 is Front_parent [f]. |
|
272 |
|
273 Int Front_1strow [n_col+1] ; Output argument. |
|
274 |
|
275 This array should be of size at least n_col+1, in order to guarantee |
|
276 that it will be large enough to hold the output. Only the first nfr+1 |
|
277 entries are used, however. |
|
278 |
|
279 Front_1strow [k] is the row index of the first row in A (P,Q) |
|
280 whose leftmost entry is in a pivot column for the kth front. This is |
|
281 necessary only to properly factorize singular matrices. Rows in the |
|
282 range Front_1strow [k] to Front_1strow [k+1]-1 first become pivot row |
|
283 candidates at the kth front. Any rows not eliminated in the kth front |
|
284 may be selected as pivot rows in the parent of k (Front_parent [k]) |
|
285 and so on up the tree. |
|
286 |
|
287 Int Front_leftmostdesc [n_col+1] ; Output argument. |
|
288 |
|
289 This array should be of size at least n_col+1, in order to guarantee |
|
290 that it will be large enough to hold the output. Only the first nfr+1 |
|
291 entries are used, however. |
|
292 |
|
293 Front_leftmostdesc [k] is the leftmost descendant of front k, or k |
|
294 if the front has no children in the tree. Since the rows and columns |
|
295 (P and Q) have been post-ordered via a depth-first-search of |
|
296 the tree, rows in the range Front_1strow [Front_leftmostdesc [k]] to |
|
297 Front_1strow [k+1]-1 form the entire set of candidate pivot rows for |
|
298 the kth front (some of these will typically have already been selected |
|
299 by fronts in the range Front_leftmostdesc [k] to front k-1, before |
|
300 the factorization reaches front k). |
|
301 |
|
302 Chain_start [n_col+1] ; Output argument. |
|
303 |
|
304 This array should be of size at least n_col+1, in order to guarantee |
|
305 that it will be large enough to hold the output. Only the first |
|
306 nchains+1 entries are used, however. |
|
307 |
|
308 The kth frontal matrix chain consists of frontal matrices Chain_start[k] |
|
309 through Chain_start [k+1]-1. Thus, Chain_start [0] is always 0, and |
|
310 Chain_start [nchains] is the total number of frontal matrices, nfr. For |
|
311 two adjacent fronts f and f+1 within a single chain, f+1 is always the |
|
312 parent of f (that is, Front_parent [f] = f+1). |
|
313 |
|
314 Int Chain_maxrows [n_col+1] ; Output argument. |
|
315 Int Chain_maxcols [n_col+1] ; Output argument. |
|
316 |
|
317 These arrays should be of size at least n_col+1, in order to guarantee |
|
318 that they will be large enough to hold the output. Only the first |
|
319 nchains entries are used, however. |
|
320 |
|
321 The kth frontal matrix chain requires a single working array of |
|
322 dimension Chain_maxrows [k] by Chain_maxcols [k], for the unifrontal |
|
323 technique that factorizes the frontal matrix chain. Since the symbolic |
|
324 factorization only provides an upper bound on the size of each frontal |
|
325 matrix, not all of the working array is necessarily used during the |
|
326 numerical factorization. |
|
327 |
|
328 Note that the upper bound on the number of rows and columns of each |
|
329 frontal matrix is computed by umfpack_*_symbolic, but all that is |
|
330 required by umfpack_*_numeric is the maximum of these two sets of |
|
331 values for each frontal matrix chain. Thus, the size of each |
|
332 individual frontal matrix is not preserved in the Symbolic object. |
|
333 |
|
334 void *Symbolic ; Input argument, not modified. |
|
335 |
|
336 The Symbolic object, which holds the symbolic factorization computed by |
|
337 umfpack_*_symbolic. The Symbolic object is not modified by |
|
338 umfpack_*_get_symbolic. |
|
339 */ |