amd.h

数学算法的实现库。可以实现常见的线性计算。

 *	Info [AMD_NCMPA]: the number of garbage collections performed.
 *
 *	Info [AMD_LNZ]: the number of nonzeros in L (excluding the diagonal).
 *	    This is a slight upper bound because mass elimination is combined
 *	    with the approximate degree update.  It is a rough upper bound if
 *	    there are many "dense" rows/columns.  The rest of the statistics,
 *	    below, are also slight or rough upper bounds, for the same reasons.
 *	    The post-ordering of the assembly tree might also not exactly
 *	    correspond to a true elimination tree postordering.
 *
 *	Info [AMD_NDIV]: the number of divide operations for a subsequent LDL'
 *	    or LU factorization of the permuted matrix A (P,P).
 *
 *	Info [AMD_NMULTSUBS_LDL]:  the number of multiply-subtract pairs for a
 *	    subsequent LDL' factorization of A (P,P).
 *
 *	Info [AMD_NMULTSUBS_LU]:  the number of multiply-subtract pairs for a
 *	    subsequent LU factorization of A (P,P), assuming that no numerical
 *	    pivoting is required.
 *
 *	Info [AMD_DMAX]:  the maximum number of nonzeros in any column of L,
 *	    including the diagonal.
 *
 *	Info [14..19] are not used in the current version, but may be used in
 *	    future versions.
 */    

/* ------------------------------------------------------------------------- */
/* AMD preprocess */
/* ------------------------------------------------------------------------- */

/* amd_preprocess: sorts, removes duplicate entries, and transposes the
 * nonzero pattern of a column-form matrix A, to obtain the matrix R.
 *
 * Alternatively, you can consider this routine as constructing a row-form
 * matrix from a column-form matrix.  Duplicate entries are allowed in A (and
 * removed in R). The columns of R are sorted.  Checks its input A for errors.
 *
 * On input, A can have unsorted columns, and can have duplicate entries.
 * Ap [0] must still be zero, and Ap must be monotonically nondecreasing.
 * Row indices must be in the range 0 to n-1.
 *
 * On output, if this routine returns AMD_OK, then the matrix R is a valid
 * input matrix for AMD_order.  It has sorted columns, with no duplicate
 * entries in each column.  Since AMD_order operates on the matrix A+A', it
 * can just as easily use A or A', so the transpose has no significant effect
 * (except for minor tie-breaking, which can lead to a minor effect in the
 * quality of the ordering).  As an example, compare the output of amd_demo.c
 * and amd_demo2.c.
 *
 * This routine transposes A to get R because that's the simplest way to
 * sort and remove duplicate entries from a matrix.
 *
 * Allocates 2*n integer work arrays, and free's them when done.
 *
 * If you wish to call amd_order, but do not know if your matrix has unsorted
 * columns or duplicate entries, then you can use the following code, which is
 * fairly efficient.  amd_order will not allocate any internal matrix until
 * it checks that the input matrix is valid, so the method below is memory-
 * efficient as well.  This code snippet assumes that Rp and Ri are already
 * allocated, and are the same size as Ap and Ai respectively.

    result = amd_order (n, p, Ap, Ai, Control, Info) ;
    if (result == AMD_INVALID)
    {
	if (amd_preprocess (n, Ap, Ai, Rp, Ri) == AMD_OK)
	{
	    result = amd_order (n, p, Rp, Ri, Control, Info) ;
	}
    }

 * amd_preprocess will still return AMD_INVALID if any row index in Ai is out
 * of range or if the Ap array is invalid.  These errors are not corrected by
 * amd_preprocess since they represent a more serious error that should be
 * flagged with the AMD_INVALID error code.
 */ 

int amd_preprocess
(
    int n,
    const int Ap [ ],
    const int Ai [ ],
    int Rp [ ],
    int Ri [ ]
) ;

long amd_l_preprocess
(
    long n,
    const long Ap [ ],
    const long Ai [ ],
    long Rp [ ],
    long Ri [ ]
) ;

/* Input arguments (not modified):
 *
 *	n: the matrix A is n-by-n.
 *	Ap: an int/long array of size n+1, containing the column pointers of A.
 *	Ai: an int/long array of size nz, containing the row indices of A,
 *	    where nz = Ap [n].
 *	The nonzero pattern of column j of A is in Ai [Ap [j] ... Ap [j+1]-1].
 *	Ap [0] must be zero, and Ap [j] <= Ap [j+1] must hold for all j in the
 *	range 0 to n-1.  Row indices in Ai must be in the range 0 to n-1.
 *	The row indices in any one column need not be sorted, and duplicates
 *	may exist.
 *
 * Output arguments (not defined on input):
 *
 *	Rp: an int/long array of size n+1, containing the column pointers of R.
 *	Ri: an int/long array of size rnz, containing the row indices of R,
 *	    where rnz = Rp [n].  Note that Rp [n] will be less than Ap [n] if
 *	    duplicates appear in A.  In general, Rp [n] <= Ap [n].
 *      The data structure for R is the same as A, except that each column of
 *      R contains sorted row indices, and no duplicates appear in any column.
 *
 * amd_preprocess returns:
 *
 *	AMD_OK if the matrix A is valid and sufficient memory can be allocated
 *	    to perform the preprocessing.
 *
 *	AMD_OUT_OF_MEMORY if not enough memory can be allocated.
 *
 *	AMD_INVALID if the input arguments n, Ap, Ai are invalid, or if Rp or
 *	    Ri are NULL.
 */

/* ------------------------------------------------------------------------- */
/* AMD Control and Info arrays */
/* ------------------------------------------------------------------------- */

/* amd_defaults:  sets the default control settings */
void amd_defaults   (double Control [ ]) ;
void amd_l_defaults (double Control [ ]) ;

/* amd_control: prints the control settings */
void amd_control    (double Control [ ]) ;
void amd_l_control  (double Control [ ]) ;

/* amd_info: prints the statistics */
void amd_info       (double Info [ ]) ;
void amd_l_info     (double Info [ ]) ;

#define AMD_CONTROL 5	    /* size of Control array */
#define AMD_INFO 20	    /* size of Info array */

/* contents of Control */
#define AMD_DENSE 0	    /* "dense" if degree > Control [0] * sqrt (n) */
#define AMD_AGGRESSIVE 1    /* do aggressive absorption if Control [1] != 0 */

/* default Control settings */
#define AMD_DEFAULT_DENSE 10.0	    /* default "dense" degree 10*sqrt(n) */
#define AMD_DEFAULT_AGGRESSIVE 1    /* do aggressive absorption by default */

/* contents of Info */
#define AMD_STATUS 0	    /* return value of amd_order and amd_l_order */
#define AMD_N 1		    /* A is n-by-n */
#define AMD_NZ 2	    /* number of nonzeros in A */ 
#define AMD_SYMMETRY 3	    /* symmetry of pattern (1 is sym., 0 is unsym.) */
#define AMD_NZDIAG 4	    /* # of entries on diagonal */
#define AMD_NZ_A_PLUS_AT 5  /* nz in A+A' */
#define AMD_NDENSE 6	    /* number of "dense" rows/columns in A */
#define AMD_MEMORY 7	    /* amount of memory used by AMD */
#define AMD_NCMPA 8	    /* number of garbage collections in AMD */
#define AMD_LNZ 9	    /* approx. nz in L, excluding the diagonal */
#define AMD_NDIV 10	    /* number of fl. point divides for LU and LDL' */
#define AMD_NMULTSUBS_LDL 11 /* number of fl. point (*,-) pairs for LDL' */
#define AMD_NMULTSUBS_LU 12  /* number of fl. point (*,-) pairs for LU */
#define AMD_DMAX 13	     /* max nz. in any column of L, incl. diagonal */

/* ------------------------------------------------------------------------- */
/* return values of AMD */
/* ------------------------------------------------------------------------- */

#define AMD_OK 0		/* success */
#define AMD_OUT_OF_MEMORY -1	/* malloc failed */
#define AMD_INVALID -2		/* input arguments are not valid */

#endif