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