1
/* ========================================================================== */
2
/* === umfpack_symbolic ===================================================== */
3
/* ========================================================================== */
5
/* -------------------------------------------------------------------------- */
6
/* UMFPACK Version 4.1 (Apr. 30, 2003), Copyright (c) 2003 by Timothy A. */
7
/* Davis. All Rights Reserved. See ../README for License. */
8
/* email: davis@cise.ufl.edu CISE Department, Univ. of Florida. */
9
/* web: http://www.cise.ufl.edu/research/sparse/umfpack */
10
/* -------------------------------------------------------------------------- */
12
int umfpack_di_symbolic
20
const double Control [UMFPACK_CONTROL],
21
double Info [UMFPACK_INFO]
24
long umfpack_dl_symbolic
32
const double Control [UMFPACK_CONTROL],
33
double Info [UMFPACK_INFO]
36
int umfpack_zi_symbolic
42
const double Ax [ ], const double Az [ ],
44
const double Control [UMFPACK_CONTROL],
45
double Info [UMFPACK_INFO]
48
long umfpack_zl_symbolic
54
const double Ax [ ], const double Az [ ],
56
const double Control [UMFPACK_CONTROL],
57
double Info [UMFPACK_INFO]
65
int n_row, n_col, *Ap, *Ai, status ;
66
double Control [UMFPACK_CONTROL], Info [UMFPACK_INFO], *Ax ;
67
status = umfpack_di_symbolic (n_row, n_col, Ap, Ai, Ax,
68
&Symbolic, Control, Info) ;
74
long n_row, n_col, *Ap, *Ai, status ;
75
double Control [UMFPACK_CONTROL], Info [UMFPACK_INFO], *Ax ;
76
status = umfpack_dl_symbolic (n_row, n_col, Ap, Ai, Ax,
77
&Symbolic, Control, Info) ;
83
int n_row, n_col, *Ap, *Ai, status ;
84
double Control [UMFPACK_CONTROL], Info [UMFPACK_INFO], *Ax, *Az ;
85
status = umfpack_zi_symbolic (n_row, n_col, Ap, Ai, Ax, Az,
86
&Symbolic, Control, Info) ;
92
long n_row, n_col, *Ap, *Ai, status ;
93
double Control [UMFPACK_CONTROL], Info [UMFPACK_INFO], *Ax, *Az ;
94
status = umfpack_zl_symbolic (n_row, n_col, Ap, Ai, Ax, Az,
95
&Symbolic, Control, Info) ;
99
Given nonzero pattern of a sparse matrix A in column-oriented form,
100
umfpack_*_symbolic performs a column pre-ordering to reduce fill-in
101
(using COLAMD or AMD) and a symbolic factorization. This is required
102
before the matrix can be numerically factorized with umfpack_*_numeric.
103
If you wish to bypass the COLAMD or AMD pre-ordering and provide your own
104
ordering, use umfpack_*_qsymbolic instead.
106
Since umfpack_*_symbolic and umfpack_*_qsymbolic are very similar, options
107
for both routines are discussed below.
109
For the following discussion, let S be the submatrix of A obtained after
110
eliminating all pivots of zero Markowitz cost. S has dimension
111
(n_row-n1-nempty_row) -by- (n_col-n1-nempty_col), where
112
n1 = Info [UMFPACK_COL_SINGLETONS] + Info [UMFPACK_ROW_SINGLETONS],
113
nempty_row = Info [UMFPACK_NEMPTY_ROW] and
114
nempty_col = Info [UMFPACK_NEMPTY_COL].
118
The status code is returned. See Info [UMFPACK_STATUS], below.
122
Int n_row ; Input argument, not modified.
123
Int n_col ; Input argument, not modified.
125
A is an n_row-by-n_col matrix. Restriction: n_row > 0 and n_col > 0.
127
Int Ap [n_col+1] ; Input argument, not modified.
129
Ap is an integer array of size n_col+1. On input, it holds the
130
"pointers" for the column form of the sparse matrix A. Column j of
131
the matrix A is held in Ai [(Ap [j]) ... (Ap [j+1]-1)]. The first
132
entry, Ap [0], must be zero, and Ap [j] <= Ap [j+1] must hold for all
133
j in the range 0 to n_col-1. The value nz = Ap [n_col] is thus the
134
total number of entries in the pattern of the matrix A. nz must be
135
greater than or equal to zero.
137
Int Ai [nz] ; Input argument, not modified, of size nz = Ap [n_col].
139
The nonzero pattern (row indices) for column j is stored in
140
Ai [(Ap [j]) ... (Ap [j+1]-1)]. The row indices in a given column j
141
must be in ascending order, and no duplicate row indices may be present.
142
Row indices must be in the range 0 to n_row-1 (the matrix is 0-based).
143
See umfpack_*_triplet_to_col for how to sort the columns of a matrix
144
and sum up the duplicate entries. See umfpack_*_report_matrix for how
145
to print the matrix A.
147
double Ax [nz] ; Optional input argument, not modified.
149
The numerical values of the sparse matrix A. The nonzero pattern (row
150
indices) for column j is stored in Ai [(Ap [j]) ... (Ap [j+1]-1)], and
151
the corresponding numerical values are stored in
152
Ax [(Ap [j]) ... (Ap [j+1]-1)]. Used only by the 2-by-2 strategy to
153
determine whether entries are "large" or "small". You do not have to
154
pass the same numerical values to umfpack_*_numeric. If Ax is not
155
present (a (double *) NULL pointer), then any entry in A is assumed to
158
double Az [nz] ; Optional input argument, not modified, for complex
161
For the complex versions, this holds the imaginary part of A. The
162
imaginary part of column j is held in Az [(Ap [j]) ... (Ap [j+1]-1)].
164
Future complex version: if Ax is present and Az is NULL, then both real
165
and imaginary parts will be contained in Ax[0..2*nz-1], with Ax[2*k]
166
and Ax[2*k+1] being the real and imaginary part of the kth entry.
168
Used by the 2-by-2 strategy only. See the description of Ax, above.
170
void **Symbolic ; Output argument.
172
**Symbolic is the address of a (void *) pointer variable in the user's
173
calling routine (see Syntax, above). On input, the contents of this
174
variable are not defined. On output, this variable holds a (void *)
175
pointer to the Symbolic object (if successful), or (void *) NULL if
178
double Control [UMFPACK_CONTROL] ; Input argument, not modified.
180
If a (double *) NULL pointer is passed, then the default control
181
settings are used (the defaults are suitable for all matrices,
182
ranging from those with highly unsymmetric nonzero pattern, to
183
symmetric matrices). Otherwise, the settings are determined from the
184
Control array. See umfpack_*_defaults on how to fill the Control
185
array with the default settings. If Control contains NaN's, the
186
defaults are used. The following Control parameters are used:
188
Control [UMFPACK_STRATEGY]: This is the most important control
189
parameter. It determines what kind of ordering and pivoting
190
strategy that UMFPACK should use. It is new to Version 4.1
193
UMFPACK_STRATEGY_AUTO: This is the default. The input matrix is
194
analyzed to determine how symmetric the nonzero pattern is, and
195
how many entries there are on the diagonal. It then selects one
196
of the following strategies. Refer to the User Guide for a
197
description of how the strategy is automatically selected.
199
UMFPACK_STRATEGY_UNSYMMETRIC: Use the unsymmetric strategy. COLAMD
200
is used to order the columns of A, followed by a postorder of
201
the column elimination tree. No attempt is made to perform
202
diagonal pivoting. The column ordering is refined during
203
factorization. This strategy was the only one provided with
206
In the numerical factorization, the
207
Control [UMFPACK_SYM_PIVOT_TOLERANCE] parameter is ignored. A
208
pivot is selected if its magnitude is >=
209
Control [UMFPACK_PIVOT_TOLERANCE] (default 0.1) times the
210
largest entry in its column.
212
UMFPACK_STRATEGY_SYMMETRIC: Use the symmetric strategy (new to
213
Version 4.1). In this method, the approximate minimum degree
214
ordering (AMD) is applied to A+A', followed by a postorder of
215
the elimination tree of A+A'. UMFPACK attempts to perform
216
diagonal pivoting during numerical factorization. No refinement
217
of the column pre-ordering is performed during factorization.
219
In the numerical factorization, a nonzero entry on the diagonal
220
is selected as the pivot if its magnitude is >= Control
221
[UMFPACK_SYM_PIVOT_TOLERANCE] (default 0.001) times the largest
222
entry in its column. If this is not acceptable, then an
223
off-diagonal pivot is selected with magnitude >= Control
224
[UMFPACK_PIVOT_TOLERANCE] (default 0.1) times the largest entry
227
UMFPACK_STRATEGY_2BY2: a row permutation P2 is found that places
228
large entries on the diagonal. The matrix P2*A is then
229
factorized using the symmetric strategy, described above.
230
Refer to the User Guide for more information.
232
Control [UMFPACK_DENSE_COL]:
233
If COLAMD is used, columns with more than
234
max (16, Control [UMFPACK_DENSE_COL] * 16 * sqrt (n_row)) entries
235
are placed placed last in the column pre-ordering. Default: 0.2.
237
Control [UMFPACK_DENSE_ROW]:
238
Rows with more than max (16, Control [UMFPACK_DENSE_ROW] * 16 *
239
sqrt (n_col)) entries are treated differently in the COLAMD
240
pre-ordering, and in the internal data structures during the
241
subsequent numeric factorization. Default: 0.2.
243
Control [UMFPACK_AMD_DENSE]: rows/columns in A+A' with more than
244
max (16, Control [UMFPACK_AMD_DENSE] * sqrt (n)) entries
245
(where n = n_row = n_col) are ignored in the AMD pre-ordering.
248
Control [UMFPACK_BLOCK_SIZE]: the block size to use for Level-3 BLAS
249
in the subsequent numerical factorization (umfpack_*_numeric).
250
A value less than 1 is treated as 1. Default: 32. Modifying this
251
parameter affects when updates are applied to the working frontal
252
matrix, and can indirectly affect fill-in and operation count.
253
As long as the block size is large enough (8 or so), this parameter
254
has a modest effect on performance.
256
Control [UMFPACK_2BY2_TOLERANCE]: a diagonal entry S (k,k) is
257
considered "small" if it is < tol * max (abs (S (:,k))), where S a
258
submatrix of the scaled input matrix, with pivots of zero Markowitz
261
Control [UMFPACK_SCALE]: This parameter is new to V4.1. See
262
umfpack_numeric.h for a description. Only affects the 2-by-2
263
strategy. Default: UMFPACK_SCALE_SUM.
265
Control [UMFPACK_FIXQ]: If > 0, then the pre-ordering Q is not modified
266
during numeric factorization. If < 0, then Q may be modified. If
267
zero, then this is controlled automatically (the unsymmetric
268
strategy modifies Q, the others do not). Default: 0.
270
Control [UMFPACK_AGGRESSIVE]: If nonzero, aggressive absorption is used
271
in COLAMD and AMD. Default: 1.
273
double Info [UMFPACK_INFO] ; Output argument, not defined on input.
275
Contains statistics about the symbolic analysis. If a (double *) NULL
276
pointer is passed, then no statistics are returned in Info (this is not
277
an error condition). The entire Info array is cleared (all entries set
278
to -1) and then the following statistics are computed:
280
Info [UMFPACK_STATUS]: status code. This is also the return value,
281
whether or not Info is present.
285
Each column of the input matrix contained row indices
286
in increasing order, with no duplicates. Only in this case
287
does umfpack_*_symbolic compute a valid symbolic factorization.
288
For the other cases below, no Symbolic object is created
289
(*Symbolic is (void *) NULL).
291
UMFPACK_ERROR_n_nonpositive
293
n is less than or equal to zero.
295
UMFPACK_ERROR_invalid_matrix
297
Number of entries in the matrix is negative, Ap [0] is nonzero,
298
a column has a negative number of entries, a row index is out of
299
bounds, or the columns of input matrix were jumbled (unsorted
300
columns or duplicate entries).
302
UMFPACK_ERROR_out_of_memory
304
Insufficient memory to perform the symbolic analysis. If the
305
analysis requires more than 2GB of memory and you are using
306
the 32-bit ("int") version of UMFPACK, then you are guaranteed
307
to run out of memory. Try using the 64-bit version of UMFPACK.
309
UMFPACK_ERROR_argument_missing
311
One or more required arguments is missing.
313
UMFPACK_ERROR_internal_error
315
Something very serious went wrong. This is a bug.
316
Please contact the author (davis@cise.ufl.edu).
318
Note that the UMFPACK_ERROR_problem_too_large error code is no
319
longer returned (it was in Version 4.0).
321
Info [UMFPACK_NROW]: the value of the input argument n_row.
323
Info [UMFPACK_NCOL]: the value of the input argument n_col.
325
Info [UMFPACK_NZ]: the number of entries in the input matrix
328
Info [UMFPACK_SIZE_OF_UNIT]: the number of bytes in a Unit,
329
for memory usage statistics below.
331
Info [UMFPACK_SIZE_OF_INT]: the number of bytes in an int.
333
Info [UMFPACK_SIZE_OF_LONG]: the number of bytes in a long.
335
Info [UMFPACK_SIZE_OF_POINTER]: the number of bytes in a void *
338
Info [UMFPACK_SIZE_OF_ENTRY]: the number of bytes in a numerical entry.
340
Info [UMFPACK_NDENSE_ROW]: number of "dense" rows in A. These rows are
341
ignored when the column pre-ordering is computed in COLAMD. They
342
are also treated differently during numeric factorization. If > 0,
343
then the matrix had to be re-analyzed by UMF_analyze, which does
344
not ignore these rows.
346
Info [UMFPACK_NEMPTY_ROW]: number of "empty" rows in A, as determined
347
These are rows that either have no entries, or whose entries are
348
all in pivot columns of zero-Markowitz-cost pivots.
350
Info [UMFPACK_NDENSE_COL]: number of "dense" columns in A. COLAMD
351
orders these columns are ordered last in the factorization, but
352
before "empty" columns.
354
Info [UMFPACK_NEMPTY_COL]: number of "empty" columns in A. These are
355
columns that either have no entries, or whose entries are all in
356
pivot rows of zero-Markowitz-cost pivots. These columns are
357
ordered last in the factorization, to the right of "dense" columns.
359
Info [UMFPACK_SYMBOLIC_DEFRAG]: number of garbage collections
360
performed during ordering and symbolic pre-analysis.
362
Info [UMFPACK_SYMBOLIC_PEAK_MEMORY]: the amount of memory (in Units)
363
required for umfpack_*_symbolic to complete. This count includes
364
the size of the Symbolic object itself, which is also reported in
365
Info [UMFPACK_SYMBOLIC_SIZE].
367
Info [UMFPACK_SYMBOLIC_SIZE]: the final size of the Symbolic object (in
368
Units). This is fairly small, roughly 2*n to 13*n integers,
369
depending on the matrix.
371
Info [UMFPACK_VARIABLE_INIT_ESTIMATE]: the Numeric object contains two
372
parts. The first is fixed in size (O (n_row+n_col)). The
373
second part holds the sparse LU factors and the contribution blocks
374
from factorized frontal matrices. This part changes in size during
375
factorization. Info [UMFPACK_VARIABLE_INIT_ESTIMATE] is the exact
376
size (in Units) required for this second variable-sized part in
377
order for the numerical factorization to start.
379
Info [UMFPACK_VARIABLE_PEAK_ESTIMATE]: the estimated peak size (in
380
Units) of the variable-sized part of the Numeric object. This is
381
usually an upper bound, but that is not guaranteed.
383
Info [UMFPACK_VARIABLE_FINAL_ESTIMATE]: the estimated final size (in
384
Units) of the variable-sized part of the Numeric object. This is
385
usually an upper bound, but that is not guaranteed. It holds just
386
the sparse LU factors.
388
Info [UMFPACK_NUMERIC_SIZE_ESTIMATE]: an estimate of the final size (in
389
Units) of the entire Numeric object (both fixed-size and variable-
390
sized parts), which holds the LU factorization (including the L, U,
393
Info [UMFPACK_PEAK_MEMORY_ESTIMATE]: an estimate of the total amount of
394
memory (in Units) required by umfpack_*_symbolic and
395
umfpack_*_numeric to perform both the symbolic and numeric
396
factorization. This is the larger of the amount of memory needed
397
in umfpack_*_numeric itself, and the amount of memory needed in
398
umfpack_*_symbolic (Info [UMFPACK_SYMBOLIC_PEAK_MEMORY]). The
399
count includes the size of both the Symbolic and Numeric objects
400
themselves. It can be a very loose upper bound, particularly when
401
the symmetric or 2-by-2 strategies are used.
403
Info [UMFPACK_FLOPS_ESTIMATE]: an estimate of the total floating-point
404
operations required to factorize the matrix. This is a "true"
405
theoretical estimate of the number of flops that would be performed
406
by a flop-parsimonious sparse LU algorithm. It assumes that no
407
extra flops are performed except for what is strictly required to
408
compute the LU factorization. It ignores, for example, the flops
409
performed by umfpack_di_numeric to add contribution blocks of
410
frontal matrices together. If L and U are the upper bound on the
411
pattern of the factors, then this flop count estimate can be
412
represented in MATLAB (for real matrices, not complex) as:
414
Lnz = full (sum (spones (L))) - 1 ; % nz in each col of L
415
Unz = full (sum (spones (U')))' - 1 ; % nz in each row of U
416
flops = 2*Lnz*Unz + sum (Lnz) ;
418
The actual "true flop" count found by umfpack_*_numeric will be
419
less than this estimate.
421
For the real version, only (+ - * /) are counted. For the complex
422
version, the following counts are used:
429
Info [UMFPACK_LNZ_ESTIMATE]: an estimate of the number of nonzeros in
430
L, including the diagonal. Since L is unit-diagonal, the diagonal
431
of L is not stored. This estimate is a strict upper bound on the
432
actual nonzeros in L to be computed by umfpack_*_numeric.
434
Info [UMFPACK_UNZ_ESTIMATE]: an estimate of the number of nonzeros in
435
U, including the diagonal. This estimate is a strict upper bound on
436
the actual nonzeros in U to be computed by umfpack_*_numeric.
438
Info [UMFPACK_MAX_FRONT_SIZE_ESTIMATE]: estimate of the size of the
439
largest frontal matrix (# of entries), for arbitrary partial
440
pivoting during numerical factorization.
442
Info [UMFPACK_SYMBOLIC_TIME]: The CPU time taken, in seconds.
444
------------------------------------------------------------------------
445
The rest of the statistics are new to Version 4.1:
446
------------------------------------------------------------------------
448
Info [UMFPACK_SYMBOLIC_WALLTIME]: The wallclock time taken, in seconds.
450
Info [UMFPACK_STRATEGY_USED]: The ordering strategy used:
451
UMFPACK_STRATEGY_SYMMETRIC, UMFPACK_STRATEGY_UNSYMMETRIC, or
452
UMFPACK_STRATEGY_2BY2.
454
Info [UMFPACK_ORDERING_USED]: The ordering method used:
455
UMFPACK_ORDERING_COLAMD or UMFPACK_ORDERING_AMD. It can be
456
UMFPACK_ORDERING_GIVEN for umfpack_*_qsymbolic.
458
Info [UMFPACK_QFIXED]: 1 if the column pre-ordering will be refined
459
during numerical factorization, 0 if not.
461
Info [UMFPACK_DIAG_PREFERED]: 1 if diagonal pivoting will be attempted,
464
Info [UMFPACK_COL_SINGLETONS]: the matrix A is analyzed by first
465
eliminating all pivots with zero Markowitz cost. This count is the
466
number of these pivots with exactly one nonzero in their pivot
469
Info [UMFPACK_ROW_SINGLETONS]: the number of zero-Markowitz-cost
470
pivots with exactly one nonzero in their pivot row.
472
Info [UMFPACK_PATTERN_SYMMETRY]: the symmetry of the pattern of S.
474
Info [UMFPACK_NZ_A_PLUS_AT]: the number of off-diagonal entries in S+S'.
476
Info [UMFPACK_NZDIAG]: the number of entries on the diagonal of S.
478
Info [UMFPACK_N2]: if S is square, and nempty_row = nempty_col, this
479
is equal to n_row - n1 - nempty_row.
481
Info [UMFPACK_S_SYMMETRIC]: 1 if S is square and its diagonal has been
482
preserved, 0 otherwise.
485
Info [UMFPACK_MAX_FRONT_NROWS_ESTIMATE]: estimate of the max number of
486
rows in any frontal matrix, for arbitrary partial pivoting.
488
Info [UMFPACK_MAX_FRONT_NCOLS_ESTIMATE]: estimate of the max number of
489
columns in any frontal matrix, for arbitrary partial pivoting.
491
------------------------------------------------------------------------
492
The next four statistics are computed only if AMD is used:
493
------------------------------------------------------------------------
495
Info [UMFPACK_SYMMETRIC_LUNZ]: The number of nonzeros in L and U,
496
assuming no pivoting during numerical factorization, and assuming a
497
zero-free diagonal of U. Excludes the entries on the diagonal of
498
L. If the matrix has a purely symmetric nonzero pattern, this is
499
often a lower bound on the nonzeros in the actual L and U computed
500
in the numerical factorization, for matrices that fit the criteria
501
for the "symmetric" strategy.
503
Info [UMFPACK_SYMMETRIC_FLOPS]: The floating-point operation count in
504
the numerical factorization phase, assuming no pivoting. If the
505
pattern of the matrix is symmetric, this is normally a lower bound
506
on the floating-point operation count in the actual numerical
507
factorization, for matrices that fit the criteria for the symmetric
510
Info [UMFPACK_SYMMETRIC_NDENSE]: The number of "dense" rows/columns of
511
S+S' that were ignored during the AMD ordering. These are placed
512
last in the output order. If > 0, then the
513
Info [UMFPACK_SYMMETRIC_*] statistics, above are rough upper bounds.
515
Info [UMFPACK_SYMMETRIC_DMAX]: The maximum number of nonzeros in any
516
column of L, if no pivoting is performed during numerical
517
factorization. Excludes the part of the LU factorization for
518
pivots with zero Markowitz cost.
520
------------------------------------------------------------------------
521
The following statistics are computed only if the 2-by-2 strategy is
523
------------------------------------------------------------------------
525
Info [UMFPACK_2BY2_NWEAK]: the number of small diagonal entries in S.
527
Info [UMFPACK_2BY2_UNMATCHED]: the number of small diagonal entries
530
Info [UMFPACK_2BY2_PATTERN_SYMMETRY]: the symmetry of P2*S.
532
Info [UMFPACK_2BY2_NZ_PA_PLUS_AT]: the number of off-diagonal entries
535
Info [UMFPACK_2BY2_NZDIAG]: the number of nonzero entries on the
539
At the start of umfpack_*_symbolic, all of Info is set of -1, and then
540
after that only the above listed Info [...] entries are accessed.
541
Future versions might modify different parts of Info.
added
removed
Lib/sandbox/pysparse/umfpack/umfpack_symbolic.h
