Mercurial > octave-nkf
diff liboctave/UMFPACK/UMFPACK/Include/umfpack_symbolic.h @ 5164:57077d0ddc8e
[project @ 2005-02-25 19:55:24 by jwe]
author | jwe |
---|---|
date | Fri, 25 Feb 2005 19:55:28 +0000 |
parents | |
children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/liboctave/UMFPACK/UMFPACK/Include/umfpack_symbolic.h Fri Feb 25 19:55:28 2005 +0000 @@ -0,0 +1,536 @@ +/* ========================================================================== */ +/* === umfpack_symbolic ===================================================== */ +/* ========================================================================== */ + +/* -------------------------------------------------------------------------- */ +/* UMFPACK Version 4.4, Copyright (c) 2005 by Timothy A. Davis. CISE Dept, */ +/* Univ. of Florida. All Rights Reserved. See ../Doc/License for License. */ +/* web: http://www.cise.ufl.edu/research/sparse/umfpack */ +/* -------------------------------------------------------------------------- */ + +int umfpack_di_symbolic +( + int n_row, + int n_col, + const int Ap [ ], + const int Ai [ ], + const double Ax [ ], + void **Symbolic, + const double Control [UMFPACK_CONTROL], + double Info [UMFPACK_INFO] +) ; + +long umfpack_dl_symbolic +( + long n_row, + long n_col, + const long Ap [ ], + const long Ai [ ], + const double Ax [ ], + void **Symbolic, + const double Control [UMFPACK_CONTROL], + double Info [UMFPACK_INFO] +) ; + +int umfpack_zi_symbolic +( + int n_row, + int n_col, + const int Ap [ ], + const int Ai [ ], + const double Ax [ ], const double Az [ ], + void **Symbolic, + const double Control [UMFPACK_CONTROL], + double Info [UMFPACK_INFO] +) ; + +long umfpack_zl_symbolic +( + long n_row, + long n_col, + const long Ap [ ], + const long Ai [ ], + const double Ax [ ], const double Az [ ], + void **Symbolic, + const double Control [UMFPACK_CONTROL], + double Info [UMFPACK_INFO] +) ; + +/* +double int Syntax: + + #include "umfpack.h" + void *Symbolic ; + int n_row, n_col, *Ap, *Ai, status ; + double Control [UMFPACK_CONTROL], Info [UMFPACK_INFO], *Ax ; + status = umfpack_di_symbolic (n_row, n_col, Ap, Ai, Ax, + &Symbolic, Control, Info) ; + +double long Syntax: + + #include "umfpack.h" + void *Symbolic ; + long n_row, n_col, *Ap, *Ai, status ; + double Control [UMFPACK_CONTROL], Info [UMFPACK_INFO], *Ax ; + status = umfpack_dl_symbolic (n_row, n_col, Ap, Ai, Ax, + &Symbolic, Control, Info) ; + +complex int Syntax: + + #include "umfpack.h" + void *Symbolic ; + int n_row, n_col, *Ap, *Ai, status ; + double Control [UMFPACK_CONTROL], Info [UMFPACK_INFO], *Ax, *Az ; + status = umfpack_zi_symbolic (n_row, n_col, Ap, Ai, Ax, Az, + &Symbolic, Control, Info) ; + +complex long Syntax: + + #include "umfpack.h" + void *Symbolic ; + long n_row, n_col, *Ap, *Ai, status ; + double Control [UMFPACK_CONTROL], Info [UMFPACK_INFO], *Ax, *Az ; + status = umfpack_zl_symbolic (n_row, n_col, Ap, Ai, Ax, Az, + &Symbolic, Control, Info) ; + +packed complex Syntax: + + Same as above, except Az is NULL. + +Purpose: + + Given nonzero pattern of a sparse matrix A in column-oriented form, + umfpack_*_symbolic performs a column pre-ordering to reduce fill-in + (using COLAMD or AMD) and a symbolic factorization. This is required + before the matrix can be numerically factorized with umfpack_*_numeric. + If you wish to bypass the COLAMD or AMD pre-ordering and provide your own + ordering, use umfpack_*_qsymbolic instead. + + Since umfpack_*_symbolic and umfpack_*_qsymbolic are very similar, options + for both routines are discussed below. + + For the following discussion, let S be the submatrix of A obtained after + eliminating all pivots of zero Markowitz cost. S has dimension + (n_row-n1-nempty_row) -by- (n_col-n1-nempty_col), where + n1 = Info [UMFPACK_COL_SINGLETONS] + Info [UMFPACK_ROW_SINGLETONS], + nempty_row = Info [UMFPACK_NEMPTY_ROW] and + nempty_col = Info [UMFPACK_NEMPTY_COL]. + +Returns: + + The status code is returned. See Info [UMFPACK_STATUS], below. + +Arguments: + + Int n_row ; Input argument, not modified. + Int n_col ; Input argument, not modified. + + A is an n_row-by-n_col matrix. Restriction: n_row > 0 and n_col > 0. + + Int Ap [n_col+1] ; Input argument, not modified. + + Ap is an integer array of size n_col+1. On input, it holds the + "pointers" for the column form of the sparse matrix A. Column j of + the matrix A is held in Ai [(Ap [j]) ... (Ap [j+1]-1)]. The first + entry, Ap [0], must be zero, and Ap [j] <= Ap [j+1] must hold for all + j in the range 0 to n_col-1. The value nz = Ap [n_col] is thus the + total number of entries in the pattern of the matrix A. nz must be + greater than or equal to zero. + + Int Ai [nz] ; Input argument, not modified, of size nz = Ap [n_col]. + + The nonzero pattern (row indices) for column j is stored in + Ai [(Ap [j]) ... (Ap [j+1]-1)]. The row indices in a given column j + must be in ascending order, and no duplicate row indices may be present. + Row indices must be in the range 0 to n_row-1 (the matrix is 0-based). + See umfpack_*_triplet_to_col for how to sort the columns of a matrix + and sum up the duplicate entries. See umfpack_*_report_matrix for how + to print the matrix A. + + double Ax [nz] ; Optional input argument, not modified. + Size 2*nz for packed complex case. + + The numerical values of the sparse matrix A. The nonzero pattern (row + indices) for column j is stored in Ai [(Ap [j]) ... (Ap [j+1]-1)], and + the corresponding numerical values are stored in + Ax [(Ap [j]) ... (Ap [j+1]-1)]. Used only by the 2-by-2 strategy to + determine whether entries are "large" or "small". You do not have to + pass the same numerical values to umfpack_*_numeric. If Ax is not + present (a (double *) NULL pointer), then any entry in A is assumed to + be "large". + + double Az [nz] ; Optional input argument, not modified, for complex + versions. + + For the complex versions, this holds the imaginary part of A. The + imaginary part of column j is held in Az [(Ap [j]) ... (Ap [j+1]-1)]. + + If Az is NULL, then both real + and imaginary parts are contained in Ax[0..2*nz-1], with Ax[2*k] + and Ax[2*k+1] being the real and imaginary part of the kth entry. + + Used by the 2-by-2 strategy only. See the description of Ax, above. + + void **Symbolic ; Output argument. + + **Symbolic is the address of a (void *) pointer variable in the user's + calling routine (see Syntax, above). On input, the contents of this + variable are not defined. On output, this variable holds a (void *) + pointer to the Symbolic object (if successful), or (void *) NULL if + a failure occurred. + + double Control [UMFPACK_CONTROL] ; Input argument, not modified. + + If a (double *) NULL pointer is passed, then the default control + settings are used (the defaults are suitable for all matrices, + ranging from those with highly unsymmetric nonzero pattern, to + symmetric matrices). Otherwise, the settings are determined from the + Control array. See umfpack_*_defaults on how to fill the Control + array with the default settings. If Control contains NaN's, the + defaults are used. The following Control parameters are used: + + Control [UMFPACK_STRATEGY]: This is the most important control + parameter. It determines what kind of ordering and pivoting + strategy that UMFPACK should use. There are 4 options: + + UMFPACK_STRATEGY_AUTO: This is the default. The input matrix is + analyzed to determine how symmetric the nonzero pattern is, and + how many entries there are on the diagonal. It then selects one + of the following strategies. Refer to the User Guide for a + description of how the strategy is automatically selected. + + UMFPACK_STRATEGY_UNSYMMETRIC: Use the unsymmetric strategy. COLAMD + is used to order the columns of A, followed by a postorder of + the column elimination tree. No attempt is made to perform + diagonal pivoting. The column ordering is refined during + factorization. + + In the numerical factorization, the + Control [UMFPACK_SYM_PIVOT_TOLERANCE] parameter is ignored. A + pivot is selected if its magnitude is >= + Control [UMFPACK_PIVOT_TOLERANCE] (default 0.1) times the + largest entry in its column. + + UMFPACK_STRATEGY_SYMMETRIC: Use the symmetric strategy + In this method, the approximate minimum degree + ordering (AMD) is applied to A+A', followed by a postorder of + the elimination tree of A+A'. UMFPACK attempts to perform + diagonal pivoting during numerical factorization. No refinement + of the column pre-ordering is performed during factorization. + + In the numerical factorization, a nonzero entry on the diagonal + is selected as the pivot if its magnitude is >= Control + [UMFPACK_SYM_PIVOT_TOLERANCE] (default 0.001) times the largest + entry in its column. If this is not acceptable, then an + off-diagonal pivot is selected with magnitude >= Control + [UMFPACK_PIVOT_TOLERANCE] (default 0.1) times the largest entry + in its column. + + UMFPACK_STRATEGY_2BY2: a row permutation P2 is found that places + large entries on the diagonal. The matrix P2*A is then + factorized using the symmetric strategy, described above. + Refer to the User Guide for more information. + + Control [UMFPACK_DENSE_COL]: + If COLAMD is used, columns with more than + max (16, Control [UMFPACK_DENSE_COL] * 16 * sqrt (n_row)) entries + are placed placed last in the column pre-ordering. Default: 0.2. + + Control [UMFPACK_DENSE_ROW]: + Rows with more than max (16, Control [UMFPACK_DENSE_ROW] * 16 * + sqrt (n_col)) entries are treated differently in the COLAMD + pre-ordering, and in the internal data structures during the + subsequent numeric factorization. Default: 0.2. + + Control [UMFPACK_AMD_DENSE]: rows/columns in A+A' with more than + max (16, Control [UMFPACK_AMD_DENSE] * sqrt (n)) entries + (where n = n_row = n_col) are ignored in the AMD pre-ordering. + Default: 10. + + Control [UMFPACK_BLOCK_SIZE]: the block size to use for Level-3 BLAS + in the subsequent numerical factorization (umfpack_*_numeric). + A value less than 1 is treated as 1. Default: 32. Modifying this + parameter affects when updates are applied to the working frontal + matrix, and can indirectly affect fill-in and operation count. + As long as the block size is large enough (8 or so), this parameter + has a modest effect on performance. + + Control [UMFPACK_2BY2_TOLERANCE]: a diagonal entry S (k,k) is + considered "small" if it is < tol * max (abs (S (:,k))), where S a + submatrix of the scaled input matrix, with pivots of zero Markowitz + cost removed. + + Control [UMFPACK_SCALE]: See umfpack_numeric.h for a description. + Only affects the 2-by-2 strategy. Default: UMFPACK_SCALE_SUM. + + Control [UMFPACK_FIXQ]: If > 0, then the pre-ordering Q is not modified + during numeric factorization. If < 0, then Q may be modified. If + zero, then this is controlled automatically (the unsymmetric + strategy modifies Q, the others do not). Default: 0. + + Control [UMFPACK_AGGRESSIVE]: If nonzero, aggressive absorption is used + in COLAMD and AMD. Default: 1. + + double Info [UMFPACK_INFO] ; Output argument, not defined on input. + + Contains statistics about the symbolic analysis. If a (double *) NULL + pointer is passed, then no statistics are returned in Info (this is not + an error condition). The entire Info array is cleared (all entries set + to -1) and then the following statistics are computed: + + Info [UMFPACK_STATUS]: status code. This is also the return value, + whether or not Info is present. + + UMFPACK_OK + + Each column of the input matrix contained row indices + in increasing order, with no duplicates. Only in this case + does umfpack_*_symbolic compute a valid symbolic factorization. + For the other cases below, no Symbolic object is created + (*Symbolic is (void *) NULL). + + UMFPACK_ERROR_n_nonpositive + + n is less than or equal to zero. + + UMFPACK_ERROR_invalid_matrix + + Number of entries in the matrix is negative, Ap [0] is nonzero, + a column has a negative number of entries, a row index is out of + bounds, or the columns of input matrix were jumbled (unsorted + columns or duplicate entries). + + UMFPACK_ERROR_out_of_memory + + Insufficient memory to perform the symbolic analysis. If the + analysis requires more than 2GB of memory and you are using + the 32-bit ("int") version of UMFPACK, then you are guaranteed + to run out of memory. Try using the 64-bit version of UMFPACK. + + UMFPACK_ERROR_argument_missing + + One or more required arguments is missing. + + UMFPACK_ERROR_internal_error + + Something very serious went wrong. This is a bug. + Please contact the author (davis@cise.ufl.edu). + + Info [UMFPACK_NROW]: the value of the input argument n_row. + + Info [UMFPACK_NCOL]: the value of the input argument n_col. + + Info [UMFPACK_NZ]: the number of entries in the input matrix + (Ap [n_col]). + + Info [UMFPACK_SIZE_OF_UNIT]: the number of bytes in a Unit, + for memory usage statistics below. + + Info [UMFPACK_SIZE_OF_INT]: the number of bytes in an int. + + Info [UMFPACK_SIZE_OF_LONG]: the number of bytes in a long. + + Info [UMFPACK_SIZE_OF_POINTER]: the number of bytes in a void * + pointer. + + Info [UMFPACK_SIZE_OF_ENTRY]: the number of bytes in a numerical entry. + + Info [UMFPACK_NDENSE_ROW]: number of "dense" rows in A. These rows are + ignored when the column pre-ordering is computed in COLAMD. They + are also treated differently during numeric factorization. If > 0, + then the matrix had to be re-analyzed by UMF_analyze, which does + not ignore these rows. + + Info [UMFPACK_NEMPTY_ROW]: number of "empty" rows in A, as determined + These are rows that either have no entries, or whose entries are + all in pivot columns of zero-Markowitz-cost pivots. + + Info [UMFPACK_NDENSE_COL]: number of "dense" columns in A. COLAMD + orders these columns are ordered last in the factorization, but + before "empty" columns. + + Info [UMFPACK_NEMPTY_COL]: number of "empty" columns in A. These are + columns that either have no entries, or whose entries are all in + pivot rows of zero-Markowitz-cost pivots. These columns are + ordered last in the factorization, to the right of "dense" columns. + + Info [UMFPACK_SYMBOLIC_DEFRAG]: number of garbage collections + performed during ordering and symbolic pre-analysis. + + Info [UMFPACK_SYMBOLIC_PEAK_MEMORY]: the amount of memory (in Units) + required for umfpack_*_symbolic to complete. This count includes + the size of the Symbolic object itself, which is also reported in + Info [UMFPACK_SYMBOLIC_SIZE]. + + Info [UMFPACK_SYMBOLIC_SIZE]: the final size of the Symbolic object (in + Units). This is fairly small, roughly 2*n to 13*n integers, + depending on the matrix. + + Info [UMFPACK_VARIABLE_INIT_ESTIMATE]: the Numeric object contains two + parts. The first is fixed in size (O (n_row+n_col)). The + second part holds the sparse LU factors and the contribution blocks + from factorized frontal matrices. This part changes in size during + factorization. Info [UMFPACK_VARIABLE_INIT_ESTIMATE] is the exact + size (in Units) required for this second variable-sized part in + order for the numerical factorization to start. + + Info [UMFPACK_VARIABLE_PEAK_ESTIMATE]: the estimated peak size (in + Units) of the variable-sized part of the Numeric object. This is + usually an upper bound, but that is not guaranteed. + + Info [UMFPACK_VARIABLE_FINAL_ESTIMATE]: the estimated final size (in + Units) of the variable-sized part of the Numeric object. This is + usually an upper bound, but that is not guaranteed. It holds just + the sparse LU factors. + + Info [UMFPACK_NUMERIC_SIZE_ESTIMATE]: an estimate of the final size (in + Units) of the entire Numeric object (both fixed-size and variable- + sized parts), which holds the LU factorization (including the L, U, + P and Q matrices). + + Info [UMFPACK_PEAK_MEMORY_ESTIMATE]: an estimate of the total amount of + memory (in Units) required by umfpack_*_symbolic and + umfpack_*_numeric to perform both the symbolic and numeric + factorization. This is the larger of the amount of memory needed + in umfpack_*_numeric itself, and the amount of memory needed in + umfpack_*_symbolic (Info [UMFPACK_SYMBOLIC_PEAK_MEMORY]). The + count includes the size of both the Symbolic and Numeric objects + themselves. It can be a very loose upper bound, particularly when + the symmetric or 2-by-2 strategies are used. + + Info [UMFPACK_FLOPS_ESTIMATE]: an estimate of the total floating-point + operations required to factorize the matrix. This is a "true" + theoretical estimate of the number of flops that would be performed + by a flop-parsimonious sparse LU algorithm. It assumes that no + extra flops are performed except for what is strictly required to + compute the LU factorization. It ignores, for example, the flops + performed by umfpack_di_numeric to add contribution blocks of + frontal matrices together. If L and U are the upper bound on the + pattern of the factors, then this flop count estimate can be + represented in MATLAB (for real matrices, not complex) as: + + Lnz = full (sum (spones (L))) - 1 ; % nz in each col of L + Unz = full (sum (spones (U')))' - 1 ; % nz in each row of U + flops = 2*Lnz*Unz + sum (Lnz) ; + + The actual "true flop" count found by umfpack_*_numeric will be + less than this estimate. + + For the real version, only (+ - * /) are counted. For the complex + version, the following counts are used: + + operation flops + c = 1/b 6 + c = a*b 6 + c -= a*b 8 + + Info [UMFPACK_LNZ_ESTIMATE]: an estimate of the number of nonzeros in + L, including the diagonal. Since L is unit-diagonal, the diagonal + of L is not stored. This estimate is a strict upper bound on the + actual nonzeros in L to be computed by umfpack_*_numeric. + + Info [UMFPACK_UNZ_ESTIMATE]: an estimate of the number of nonzeros in + U, including the diagonal. This estimate is a strict upper bound on + the actual nonzeros in U to be computed by umfpack_*_numeric. + + Info [UMFPACK_MAX_FRONT_SIZE_ESTIMATE]: estimate of the size of the + largest frontal matrix (# of entries), for arbitrary partial + pivoting during numerical factorization. + + Info [UMFPACK_SYMBOLIC_TIME]: The CPU time taken, in seconds. + + Info [UMFPACK_SYMBOLIC_WALLTIME]: The wallclock time taken, in seconds. + + Info [UMFPACK_STRATEGY_USED]: The ordering strategy used: + UMFPACK_STRATEGY_SYMMETRIC, UMFPACK_STRATEGY_UNSYMMETRIC, or + UMFPACK_STRATEGY_2BY2. + + Info [UMFPACK_ORDERING_USED]: The ordering method used: + UMFPACK_ORDERING_COLAMD or UMFPACK_ORDERING_AMD. It can be + UMFPACK_ORDERING_GIVEN for umfpack_*_qsymbolic. + + Info [UMFPACK_QFIXED]: 1 if the column pre-ordering will be refined + during numerical factorization, 0 if not. + + Info [UMFPACK_DIAG_PREFERED]: 1 if diagonal pivoting will be attempted, + 0 if not. + + Info [UMFPACK_COL_SINGLETONS]: the matrix A is analyzed by first + eliminating all pivots with zero Markowitz cost. This count is the + number of these pivots with exactly one nonzero in their pivot + column. + + Info [UMFPACK_ROW_SINGLETONS]: the number of zero-Markowitz-cost + pivots with exactly one nonzero in their pivot row. + + Info [UMFPACK_PATTERN_SYMMETRY]: the symmetry of the pattern of S. + + Info [UMFPACK_NZ_A_PLUS_AT]: the number of off-diagonal entries in S+S'. + + Info [UMFPACK_NZDIAG]: the number of entries on the diagonal of S. + + Info [UMFPACK_N2]: if S is square, and nempty_row = nempty_col, this + is equal to n_row - n1 - nempty_row. + + Info [UMFPACK_S_SYMMETRIC]: 1 if S is square and its diagonal has been + preserved, 0 otherwise. + + + Info [UMFPACK_MAX_FRONT_NROWS_ESTIMATE]: estimate of the max number of + rows in any frontal matrix, for arbitrary partial pivoting. + + Info [UMFPACK_MAX_FRONT_NCOLS_ESTIMATE]: estimate of the max number of + columns in any frontal matrix, for arbitrary partial pivoting. + + ------------------------------------------------------------------------ + The next four statistics are computed only if AMD is used: + ------------------------------------------------------------------------ + + Info [UMFPACK_SYMMETRIC_LUNZ]: The number of nonzeros in L and U, + assuming no pivoting during numerical factorization, and assuming a + zero-free diagonal of U. Excludes the entries on the diagonal of + L. If the matrix has a purely symmetric nonzero pattern, this is + often a lower bound on the nonzeros in the actual L and U computed + in the numerical factorization, for matrices that fit the criteria + for the "symmetric" strategy. + + Info [UMFPACK_SYMMETRIC_FLOPS]: The floating-point operation count in + the numerical factorization phase, assuming no pivoting. If the + pattern of the matrix is symmetric, this is normally a lower bound + on the floating-point operation count in the actual numerical + factorization, for matrices that fit the criteria for the symmetric + or 2-by-2 strategies + + Info [UMFPACK_SYMMETRIC_NDENSE]: The number of "dense" rows/columns of + S+S' that were ignored during the AMD ordering. These are placed + last in the output order. If > 0, then the + Info [UMFPACK_SYMMETRIC_*] statistics, above are rough upper bounds. + + Info [UMFPACK_SYMMETRIC_DMAX]: The maximum number of nonzeros in any + column of L, if no pivoting is performed during numerical + factorization. Excludes the part of the LU factorization for + pivots with zero Markowitz cost. + + ------------------------------------------------------------------------ + The following statistics are computed only if the 2-by-2 strategy is + used or attempted: + ------------------------------------------------------------------------ + + Info [UMFPACK_2BY2_NWEAK]: the number of small diagonal entries in S. + + Info [UMFPACK_2BY2_UNMATCHED]: the number of small diagonal entries + in P2*S. + + Info [UMFPACK_2BY2_PATTERN_SYMMETRY]: the symmetry of P2*S. + + Info [UMFPACK_2BY2_NZ_PA_PLUS_AT]: the number of off-diagonal entries + in (P2*S)+(P2*S)'. + + Info [UMFPACK_2BY2_NZDIAG]: the number of nonzero entries on the + diagonal of P2*S. + + + At the start of umfpack_*_symbolic, all of Info is set of -1, and then + after that only the above listed Info [...] entries are accessed. + Future versions might modify different parts of Info. +*/