superlu_dist_2.0.tar.gz_LU_superlu_trilinos_稀疏分解_稀疏矩阵 LU

/* ========================================================================== */ /* === colamd - a sparse matrix column ordering algorithm =================== */ /* ========================================================================== */ /* colamd: An approximate minimum degree column ordering algorithm. Purpose: Colamd computes a permutation Q such that the Cholesky factorization of (AQ)'(AQ) has less fill-in and requires fewer floating point operations than A'A. This also provides a good ordering for sparse partial pivoting methods, P(AQ) = LU, where Q is computed prior to numerical factorization, and P is computed during numerical factorization via conventional partial pivoting with row interchanges. Colamd is the column ordering method used in SuperLU, part of the ScaLAPACK library. It is also available as user-contributed software for Matlab 5.2, available from MathWorks, Inc. (http://www.mathworks.com). This routine can be used in place of COLMMD in Matlab. By default, the \ and / operators in Matlab perform a column ordering (using COLMMD) prior to LU factorization using sparse partial pivoting, in the built-in Matlab LU(A) routine. Authors: The authors of the code itself are Stefan I. Larimore and Timothy A. Davis ([email protected]), University of Florida. The algorithm was developed in collaboration with John Gilbert, Xerox PARC, and Esmond Ng, Oak Ridge National Laboratory. Date: August 3, 1998. Version 1.0. Acknowledgements: This work was supported by the National Science Foundation, under grants DMS-9504974 and DMS-9803599. Notice: Copyright (c) 1998 by the University of Florida. All Rights Reserved. THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED OR IMPLIED. ANY USE IS AT YOUR OWN RISK. Permission is hereby granted to use or copy this program for any purpose, provided the above notices are retained on all copies. User documentation of any code that uses this code must cite the Authors, the Copyright, and "Used by permission." If this code is accessible from within Matlab, then typing "help colamd" or "colamd" (with no arguments) must cite the Authors. Permission to modify the code and to distribute modified code is granted, provided the above notices are retained, and a notice that the code was modified is included with the above copyright notice. You must also retain the Availability information below, of the original version. This software is provided free of charge. Availability: This file is located at http://www.cise.ufl.edu/~davis/colamd/colamd.c The colamd.h file is required, located in the same directory. The colamdmex.c file provides a Matlab interface for colamd. The symamdmex.c file provides a Matlab interface for symamd, which is a symmetric ordering based on this code, colamd.c. All codes are purely ANSI C compliant (they use no Unix-specific routines, include files, etc.). */ /* ========================================================================== */ /* === Description of user-callable routines ================================ */ /* ========================================================================== */ /* Each user-callable routine (declared as PUBLIC) is briefly described below. Refer to the comments preceding each routine for more details. ---------------------------------------------------------------------------- colamd_recommended: ---------------------------------------------------------------------------- Usage: Alen = colamd_recommended (nnz, n_row, n_col) ; Purpose: Returns recommended value of Alen for use by colamd. Returns -1 if any input argument is negative. Arguments: int nnz ; Number of nonzeros in the matrix A. This must be the same value as p [n_col] in the call to colamd - otherwise you will get a wrong value of the recommended memory to use. int n_row ; Number of rows in the matrix A. int n_col ; Number of columns in the matrix A. ---------------------------------------------------------------------------- colamd_set_defaults: ---------------------------------------------------------------------------- Usage: colamd_set_defaults (knobs) ; Purpose: Sets the default parameters. Arguments: double knobs [COLAMD_KNOBS] ; Output only. Rows with more than (knobs [COLAMD_DENSE_ROW] * n_col) entries are removed prior to ordering. Columns with more than (knobs [COLAMD_DENSE_COL] * n_row) entries are removed prior to ordering, and placed last in the output column ordering. Default values of these two knobs are both 0.5. Currently, only knobs [0] and knobs [1] are used, but future versions may use more knobs. If so, they will be properly set to their defaults by the future version of colamd_set_defaults, so that the code that calls colamd will not need to change, assuming that you either use colamd_set_defaults, or pass a (double *) NULL pointer as the knobs array to colamd. ---------------------------------------------------------------------------- colamd: ---------------------------------------------------------------------------- Usage: colamd (n_row, n_col, Alen, A, p, knobs) ; Purpose: Computes a column ordering (Q) of A such that P(AQ)=LU or (AQ)'AQ=LL' have less fill-in and require fewer floating point operations than factorizing the unpermuted matrix A or A'A, respectively. Arguments: int n_row ; Number of rows in the matrix A. Restriction: n_row >= 0. Colamd returns FALSE if n_row is negative. int n_col ; Number of columns in the matrix A. Restriction: n_col >= 0. Colamd returns FALSE if n_col is negative. int Alen ; Restriction (see note): Alen >= 2*nnz + 6*(n_col+1) + 4*(n_row+1) + n_col + COLAMD_STATS Colamd returns FALSE if these conditions are not met. Note: this restriction makes an modest assumption regarding the size of the two typedef'd structures, below. We do, however, guarantee that Alen >= colamd_recommended (nnz, n_row, n_col) will be sufficient. int A [Alen] ; Input argument, stats on output. A is an integer array of size Alen. Alen must be at least as large as the bare minimum value given above, but this is very low, and can result in excessive run time. For best performance, we recommend that Alen be greater than or equal to colamd_recommended (nnz, n_row, n_col), which adds nnz/5 to the bare minimum value given above. On input, the row indices of the entries in column c of the matrix are held in A [(p [c]) ... (p [c+1]-1)]. The row indices in a given column c need not be in ascending order, and duplicate row indices may be be present. However, colamd will work a little faster if both of these conditions are met (Colamd puts the matrix into this format, if it finds that the the conditions are not met). The matrix is 0-based. That is, rows are in the range 0 to n_row-1, and columns are in the range 0 to n_col-1. Colamd returns FALSE if any row index is out of range. The contents of A are modified during ordering, and are thus undefined on output with the exception of a few statistics about the ordering (A [0..COLAMD_STATS-1]): A [0]: number of dense or empty rows ignored. A [1]: number of dense or empty columns ignored (and ordered last in the output permutation p) A [2]: number of garbage collections performed. A [3]: 0, if all row indices in each column were in sorted order, and no duplicates were present. 1, otherwise (in which case colamd had to do more work) Note that a row can become "empty" if it contains only "dense" and/or "empty" columns, and similarly a column can become "empty" if it only contains "dense" and/or "empty" rows. Future versions may return more statistics in A, but the usage of these 4 entries in A wi