From 22460edb49885a60672f1ab29e71c6dd7f89d197 Mon Sep 17 00:00:00 2001 From: Desire NUENTSA Date: Wed, 20 Mar 2013 16:02:03 +0100 Subject: Use a template Index for COLAMD ordering --- Eigen/src/OrderingMethods/Eigen_Colamd.h | 2087 +++++++++++++++--------------- Eigen/src/OrderingMethods/Ordering.h | 18 +- 2 files changed, 1054 insertions(+), 1051 deletions(-) (limited to 'Eigen/src/OrderingMethods') diff --git a/Eigen/src/OrderingMethods/Eigen_Colamd.h b/Eigen/src/OrderingMethods/Eigen_Colamd.h index 6dc1f280d..6075c5aa5 100644 --- a/Eigen/src/OrderingMethods/Eigen_Colamd.h +++ b/Eigen/src/OrderingMethods/Eigen_Colamd.h @@ -50,6 +50,7 @@ #ifndef EIGEN_COLAMD_H #define EIGEN_COLAMD_H + namespace internal { /* Ensure that debugging is turned off: */ #ifndef COLAMD_NDEBUG @@ -133,107 +134,106 @@ namespace internal { /* === Colamd reporting mechanism =========================================== */ /* ========================================================================== */ - // == Row and Column structures == -typedef struct colamd_col_struct +// == Row and Column structures == +template +struct colamd_col { - int start ; /* index for A of first row in this column, or DEAD */ - /* if column is dead */ - int length ; /* number of rows in this column */ - union - { - int thickness ; /* number of original columns represented by this */ - /* col, if the column is alive */ - int parent ; /* parent in parent tree super-column structure, if */ - /* the column is dead */ - } shared1 ; - union - { - int score ; /* the score used to maintain heap, if col is alive */ - int order ; /* pivot ordering of this column, if col is dead */ - } shared2 ; - union - { - int headhash ; /* head of a hash bucket, if col is at the head of */ - /* a degree list */ - int hash ; /* hash value, if col is not in a degree list */ - int prev ; /* previous column in degree list, if col is in a */ - /* degree list (but not at the head of a degree list) */ - } shared3 ; - union - { - int degree_next ; /* next column, if col is in a degree list */ - int hash_next ; /* next column, if col is in a hash list */ - } shared4 ; - -} colamd_col ; - -typedef struct Colamd_Row_struct + Index start ; /* index for A of first row in this column, or DEAD */ + /* if column is dead */ + Index length ; /* number of rows in this column */ + union + { + Index thickness ; /* number of original columns represented by this */ + /* col, if the column is alive */ + Index parent ; /* parent in parent tree super-column structure, if */ + /* the column is dead */ + } shared1 ; + union + { + Index score ; /* the score used to maintain heap, if col is alive */ + Index order ; /* pivot ordering of this column, if col is dead */ + } shared2 ; + union + { + Index headhash ; /* head of a hash bucket, if col is at the head of */ + /* a degree list */ + Index hash ; /* hash value, if col is not in a degree list */ + Index prev ; /* previous column in degree list, if col is in a */ + /* degree list (but not at the head of a degree list) */ + } shared3 ; + union + { + Index degree_next ; /* next column, if col is in a degree list */ + Index hash_next ; /* next column, if col is in a hash list */ + } shared4 ; + +}; + +template +struct Colamd_Row { - int start ; /* index for A of first col in this row */ - int length ; /* number of principal columns in this row */ - union - { - int degree ; /* number of principal & non-principal columns in row */ - int p ; /* used as a row pointer in init_rows_cols () */ - } shared1 ; - union - { - int mark ; /* for computing set differences and marking dead rows*/ - int first_column ;/* first column in row (used in garbage collection) */ - } shared2 ; - -} Colamd_Row ; - + Index start ; /* index for A of first col in this row */ + Index length ; /* number of principal columns in this row */ + union + { + Index degree ; /* number of principal & non-principal columns in row */ + Index p ; /* used as a row pointer in init_rows_cols () */ + } shared1 ; + union + { + Index mark ; /* for computing set differences and marking dead rows*/ + Index first_column ;/* first column in row (used in garbage collection) */ + } shared2 ; + +}; + /* ========================================================================== */ /* === Colamd recommended memory size ======================================= */ /* ========================================================================== */ - + /* - The recommended length Alen of the array A passed to colamd is given by - the COLAMD_RECOMMENDED (nnz, n_row, n_col) macro. It returns -1 if any - argument is negative. 2*nnz space is required for the row and column - indices of the matrix. colamd_c (n_col) + colamd_r (n_row) space is - required for the Col and Row arrays, respectively, which are internal to - colamd. An additional n_col space is the minimal amount of "elbow room", - and nnz/5 more space is recommended for run time efficiency. - - This macro is not needed when using symamd. - - Explicit typecast to int added Sept. 23, 2002, COLAMD version 2.2, to avoid - gcc -pedantic warning messages. + The recommended length Alen of the array A passed to colamd is given by + the COLAMD_RECOMMENDED (nnz, n_row, n_col) macro. It returns -1 if any + argument is negative. 2*nnz space is required for the row and column + indices of the matrix. colamd_c (n_col) + colamd_r (n_row) space is + required for the Col and Row arrays, respectively, which are internal to + colamd. An additional n_col space is the minimal amount of "elbow room", + and nnz/5 more space is recommended for run time efficiency. + + This macro is not needed when using symamd. + + Explicit typecast to Index added Sept. 23, 2002, COLAMD version 2.2, to avoid + gcc -pedantic warning messages. */ +template +inline Index colamd_c(Index n_col) +{ return Index( ((n_col) + 1) * sizeof (colamd_col) / sizeof (Index) ) ; } -inline int colamd_c(int n_col) -{ return int( ((n_col) + 1) * sizeof (colamd_col) / sizeof (int) ) ; } - -inline int colamd_r(int n_row) -{ return int(((n_row) + 1) * sizeof (Colamd_Row) / sizeof (int)); } - - // Various routines -inline int colamd_recommended (int nnz, int n_row, int n_col) ; - -static inline void colamd_set_defaults (double knobs [COLAMD_KNOBS]) ; +template +inline Index colamd_r(Index n_row) +{ return Index(((n_row) + 1) * sizeof (Colamd_Row) / sizeof (Index)); } -static bool colamd (int n_row, int n_col, int Alen, int A [], int p [], double knobs[COLAMD_KNOBS], int stats [COLAMD_STATS]) ; +// Prototypes of non-user callable routines +template +static Index init_rows_cols (Index n_row, Index n_col, Colamd_Row Row [], colamd_col col [], Index A [], Index p [], Index stats[COLAMD_STATS] ); -static int init_rows_cols (int n_row, int n_col, Colamd_Row Row [], colamd_col col [], int A [], int p [], int stats[COLAMD_STATS] ); +template +static void init_scoring (Index n_row, Index n_col, Colamd_Row Row [], colamd_col Col [], Index A [], Index head [], double knobs[COLAMD_KNOBS], Index *p_n_row2, Index *p_n_col2, Index *p_max_deg); -static void init_scoring (int n_row, int n_col, Colamd_Row Row [], colamd_col Col [], int A [], int head [], double knobs[COLAMD_KNOBS], int *p_n_row2, int *p_n_col2, int *p_max_deg); +template +static Index find_ordering (Index n_row, Index n_col, Index Alen, Colamd_Row Row [], colamd_col Col [], Index A [], Index head [], Index n_col2, Index max_deg, Index pfree); -static int find_ordering (int n_row, int n_col, int Alen, Colamd_Row Row [], colamd_col Col [], int A [], int head [], int n_col2, int max_deg, int pfree); +template +static void order_children (Index n_col, colamd_col Col [], Index p []); -static void order_children (int n_col, colamd_col Col [], int p []); +template +static void detect_super_cols (colamd_col Col [], Index A [], Index head [], Index row_start, Index row_length ) ; -static void detect_super_cols ( - colamd_col Col [], - int A [], - int head [], - int row_start, - int row_length ) ; +template +static Index garbage_collection (Index n_row, Index n_col, Colamd_Row Row [], colamd_col Col [], Index A [], Index *pfree) ; -static int garbage_collection (int n_row, int n_col, Colamd_Row Row [], colamd_col Col [], int A [], int *pfree) ; - -static inline int clear_mark (int n_row, Colamd_Row Row [] ) ; +template +static inline Index clear_mark (Index n_row, Colamd_Row Row [] ) ; /* === No debugging ========================================================= */ @@ -260,7 +260,8 @@ static inline int clear_mark (int n_row, Colamd_Row Row [] ) ; * \param n_col number of columns in A * \return recommended value of Alen for use by colamd */ -inline int colamd_recommended ( int nnz, int n_row, int n_col) +template +inline Index colamd_recommended ( Index nnz, Index n_row, Index n_col) { if ((nnz) < 0 || (n_row) < 0 || (n_col) < 0) return (-1); @@ -288,22 +289,23 @@ inline int colamd_recommended ( int nnz, int n_row, int n_col) * * \param knobs parameter settings for colamd */ + static inline void colamd_set_defaults(double knobs[COLAMD_KNOBS]) { - /* === Local variables ================================================== */ - - int i ; + /* === Local variables ================================================== */ + + int i ; - if (!knobs) - { - return ; /* no knobs to initialize */ - } - for (i = 0 ; i < COLAMD_KNOBS ; i++) - { - knobs [i] = 0 ; - } - knobs [COLAMD_DENSE_ROW] = 0.5 ; /* ignore rows over 50% dense */ - knobs [COLAMD_DENSE_COL] = 0.5 ; /* ignore columns over 50% dense */ + if (!knobs) + { + return ; /* no knobs to initialize */ + } + for (i = 0 ; i < COLAMD_KNOBS ; i++) + { + knobs [i] = 0 ; + } + knobs [COLAMD_DENSE_ROW] = 0.5 ; /* ignore rows over 50% dense */ + knobs [COLAMD_DENSE_COL] = 0.5 ; /* ignore columns over 50% dense */ } /** @@ -323,144 +325,145 @@ static inline void colamd_set_defaults(double knobs[COLAMD_KNOBS]) * \param knobs parameter settings for colamd * \param stats colamd output statistics and error codes */ -static bool colamd(int n_row, int n_col, int Alen, int *A, int *p, double knobs[COLAMD_KNOBS], int stats[COLAMD_STATS]) +template +static bool colamd(Index n_row, Index n_col, Index Alen, Index *A, Index *p, double knobs[COLAMD_KNOBS], Index stats[COLAMD_STATS]) { - /* === Local variables ================================================== */ - - int i ; /* loop index */ - int nnz ; /* nonzeros in A */ - int Row_size ; /* size of Row [], in integers */ - int Col_size ; /* size of Col [], in integers */ - int need ; /* minimum required length of A */ - Colamd_Row *Row ; /* pointer into A of Row [0..n_row] array */ - colamd_col *Col ; /* pointer into A of Col [0..n_col] array */ - int n_col2 ; /* number of non-dense, non-empty columns */ - int n_row2 ; /* number of non-dense, non-empty rows */ - int ngarbage ; /* number of garbage collections performed */ - int max_deg ; /* maximum row degree */ - double default_knobs [COLAMD_KNOBS] ; /* default knobs array */ - - - /* === Check the input arguments ======================================== */ - - if (!stats) - { - COLAMD_DEBUG0 (("colamd: stats not present\n")) ; - return (false) ; - } - for (i = 0 ; i < COLAMD_STATS ; i++) - { - stats [i] = 0 ; - } - stats [COLAMD_STATUS] = COLAMD_OK ; - stats [COLAMD_INFO1] = -1 ; - stats [COLAMD_INFO2] = -1 ; - - if (!A) /* A is not present */ - { - stats [COLAMD_STATUS] = COLAMD_ERROR_A_not_present ; - COLAMD_DEBUG0 (("colamd: A not present\n")) ; - return (false) ; - } - - if (!p) /* p is not present */ - { - stats [COLAMD_STATUS] = COLAMD_ERROR_p_not_present ; - COLAMD_DEBUG0 (("colamd: p not present\n")) ; - return (false) ; - } - - if (n_row < 0) /* n_row must be >= 0 */ - { - stats [COLAMD_STATUS] = COLAMD_ERROR_nrow_negative ; - stats [COLAMD_INFO1] = n_row ; - COLAMD_DEBUG0 (("colamd: nrow negative %d\n", n_row)) ; - return (false) ; - } - - if (n_col < 0) /* n_col must be >= 0 */ - { - stats [COLAMD_STATUS] = COLAMD_ERROR_ncol_negative ; - stats [COLAMD_INFO1] = n_col ; - COLAMD_DEBUG0 (("colamd: ncol negative %d\n", n_col)) ; - return (false) ; - } - - nnz = p [n_col] ; - if (nnz < 0) /* nnz must be >= 0 */ - { - stats [COLAMD_STATUS] = COLAMD_ERROR_nnz_negative ; - stats [COLAMD_INFO1] = nnz ; - COLAMD_DEBUG0 (("colamd: number of entries negative %d\n", nnz)) ; - return (false) ; - } - - if (p [0] != 0) - { - stats [COLAMD_STATUS] = COLAMD_ERROR_p0_nonzero ; - stats [COLAMD_INFO1] = p [0] ; - COLAMD_DEBUG0 (("colamd: p[0] not zero %d\n", p [0])) ; - return (false) ; - } - - /* === If no knobs, set default knobs =================================== */ - - if (!knobs) - { - colamd_set_defaults (default_knobs) ; - knobs = default_knobs ; - } - - /* === Allocate the Row and Col arrays from array A ===================== */ - - Col_size = colamd_c (n_col) ; - Row_size = colamd_r (n_row) ; - need = 2*nnz + n_col + Col_size + Row_size ; - - if (need > Alen) - { - /* not enough space in array A to perform the ordering */ - stats [COLAMD_STATUS] = COLAMD_ERROR_A_too_small ; - stats [COLAMD_INFO1] = need ; - stats [COLAMD_INFO2] = Alen ; - COLAMD_DEBUG0 (("colamd: Need Alen >= %d, given only Alen = %d\n", need,Alen)); - return (false) ; - } - - Alen -= Col_size + Row_size ; - Col = (colamd_col *) &A [Alen] ; - Row = (Colamd_Row *) &A [Alen + Col_size] ; - - /* === Construct the row and column data structures ===================== */ - - if (!init_rows_cols (n_row, n_col, Row, Col, A, p, stats)) - { - /* input matrix is invalid */ - COLAMD_DEBUG0 (("colamd: Matrix invalid\n")) ; - return (false) ; - } - - /* === Initialize scores, kill dense rows/columns ======================= */ - - init_scoring (n_row, n_col, Row, Col, A, p, knobs, - &n_row2, &n_col2, &max_deg) ; - - /* === Order the supercolumns =========================================== */ - - ngarbage = find_ordering (n_row, n_col, Alen, Row, Col, A, p, - n_col2, max_deg, 2*nnz) ; - - /* === Order the non-principal columns ================================== */ - - order_children (n_col, Col, p) ; + /* === Local variables ================================================== */ + + Index i ; /* loop index */ + Index nnz ; /* nonzeros in A */ + Index Row_size ; /* size of Row [], in integers */ + Index Col_size ; /* size of Col [], in integers */ + Index need ; /* minimum required length of A */ + Colamd_Row *Row ; /* pointer into A of Row [0..n_row] array */ + colamd_col *Col ; /* pointer into A of Col [0..n_col] array */ + Index n_col2 ; /* number of non-dense, non-empty columns */ + Index n_row2 ; /* number of non-dense, non-empty rows */ + Index ngarbage ; /* number of garbage collections performed */ + Index max_deg ; /* maximum row degree */ + double default_knobs [COLAMD_KNOBS] ; /* default knobs array */ + + + /* === Check the input arguments ======================================== */ + + if (!stats) + { + COLAMD_DEBUG0 (("colamd: stats not present\n")) ; + return (false) ; + } + for (i = 0 ; i < COLAMD_STATS ; i++) + { + stats [i] = 0 ; + } + stats [COLAMD_STATUS] = COLAMD_OK ; + stats [COLAMD_INFO1] = -1 ; + stats [COLAMD_INFO2] = -1 ; + + if (!A) /* A is not present */ + { + stats [COLAMD_STATUS] = COLAMD_ERROR_A_not_present ; + COLAMD_DEBUG0 (("colamd: A not present\n")) ; + return (false) ; + } + + if (!p) /* p is not present */ + { + stats [COLAMD_STATUS] = COLAMD_ERROR_p_not_present ; + COLAMD_DEBUG0 (("colamd: p not present\n")) ; + return (false) ; + } + + if (n_row < 0) /* n_row must be >= 0 */ + { + stats [COLAMD_STATUS] = COLAMD_ERROR_nrow_negative ; + stats [COLAMD_INFO1] = n_row ; + COLAMD_DEBUG0 (("colamd: nrow negative %d\n", n_row)) ; + return (false) ; + } + + if (n_col < 0) /* n_col must be >= 0 */ + { + stats [COLAMD_STATUS] = COLAMD_ERROR_ncol_negative ; + stats [COLAMD_INFO1] = n_col ; + COLAMD_DEBUG0 (("colamd: ncol negative %d\n", n_col)) ; + return (false) ; + } + + nnz = p [n_col] ; + if (nnz < 0) /* nnz must be >= 0 */ + { + stats [COLAMD_STATUS] = COLAMD_ERROR_nnz_negative ; + stats [COLAMD_INFO1] = nnz ; + COLAMD_DEBUG0 (("colamd: number of entries negative %d\n", nnz)) ; + return (false) ; + } + + if (p [0] != 0) + { + stats [COLAMD_STATUS] = COLAMD_ERROR_p0_nonzero ; + stats [COLAMD_INFO1] = p [0] ; + COLAMD_DEBUG0 (("colamd: p[0] not zero %d\n", p [0])) ; + return (false) ; + } + + /* === If no knobs, set default knobs =================================== */ + + if (!knobs) + { + colamd_set_defaults (default_knobs) ; + knobs = default_knobs ; + } + + /* === Allocate the Row and Col arrays from array A ===================== */ + + Col_size = colamd_c (n_col) ; + Row_size = colamd_r (n_row) ; + need = 2*nnz + n_col + Col_size + Row_size ; + + if (need > Alen) + { + /* not enough space in array A to perform the ordering */ + stats [COLAMD_STATUS] = COLAMD_ERROR_A_too_small ; + stats [COLAMD_INFO1] = need ; + stats [COLAMD_INFO2] = Alen ; + COLAMD_DEBUG0 (("colamd: Need Alen >= %d, given only Alen = %d\n", need,Alen)); + return (false) ; + } + + Alen -= Col_size + Row_size ; + Col = (colamd_col *) &A [Alen] ; + Row = (Colamd_Row *) &A [Alen + Col_size] ; - /* === Return statistics in stats ======================================= */ + /* === Construct the row and column data structures ===================== */ + + if (!init_rows_cols (n_row, n_col, Row, Col, A, p, stats)) + { + /* input matrix is invalid */ + COLAMD_DEBUG0 (("colamd: Matrix invalid\n")) ; + return (false) ; + } + + /* === Initialize scores, kill dense rows/columns ======================= */ - stats [COLAMD_DENSE_ROW] = n_row - n_row2 ; - stats [COLAMD_DENSE_COL] = n_col - n_col2 ; - stats [COLAMD_DEFRAG_COUNT] = ngarbage ; - COLAMD_DEBUG0 (("colamd: done.\n")) ; - return (true) ; + init_scoring (n_row, n_col, Row, Col, A, p, knobs, + &n_row2, &n_col2, &max_deg) ; + + /* === Order the supercolumns =========================================== */ + + ngarbage = find_ordering (n_row, n_col, Alen, Row, Col, A, p, + n_col2, max_deg, 2*nnz) ; + + /* === Order the non-principal columns ================================== */ + + order_children (n_col, Col, p) ; + + /* === Return statistics in stats ======================================= */ + + stats [COLAMD_DENSE_ROW] = n_row - n_row2 ; + stats [COLAMD_DENSE_COL] = n_col - n_col2 ; + stats [COLAMD_DEFRAG_COUNT] = ngarbage ; + COLAMD_DEBUG0 (("colamd: done.\n")) ; + return (true) ; } /* ========================================================================== */ @@ -475,218 +478,218 @@ static bool colamd(int n_row, int n_col, int Alen, int *A, int *p, double knobs[ /* ========================================================================== */ /* - Takes the column form of the matrix in A and creates the row form of the - matrix. Also, row and column attributes are stored in the Col and Row - structs. If the columns are un-sorted or contain duplicate row indices, - this routine will also sort and remove duplicate row indices from the - column form of the matrix. Returns false if the matrix is invalid, - true otherwise. Not user-callable. + Takes the column form of the matrix in A and creates the row form of the + matrix. Also, row and column attributes are stored in the Col and Row + structs. If the columns are un-sorted or contain duplicate row indices, + this routine will also sort and remove duplicate row indices from the + column form of the matrix. Returns false if the matrix is invalid, + true otherwise. Not user-callable. */ - - static int init_rows_cols /* returns true if OK, or false otherwise */ -( +template +static Index init_rows_cols /* returns true if OK, or false otherwise */ + ( /* === Parameters ======================================================= */ - int n_row, /* number of rows of A */ - int n_col, /* number of columns of A */ - Colamd_Row Row [], /* of size n_row+1 */ - colamd_col Col [], /* of size n_col+1 */ - int A [], /* row indices of A, of size Alen */ - int p [], /* pointers to columns in A, of size n_col+1 */ - int stats [COLAMD_STATS] /* colamd statistics */ -) + Index n_row, /* number of rows of A */ + Index n_col, /* number of columns of A */ + Colamd_Row Row [], /* of size n_row+1 */ + colamd_col Col [], /* of size n_col+1 */ + Index A [], /* row indices of A, of size Alen */ + Index p [], /* pointers to columns in A, of size n_col+1 */ + Index stats [COLAMD_STATS] /* colamd statistics */ + ) { - /* === Local variables ================================================== */ + /* === Local variables ================================================== */ - int col ; /* a column index */ - int row ; /* a row index */ - int *cp ; /* a column pointer */ - int *cp_end ; /* a pointer to the end of a column */ - int *rp ; /* a row pointer */ - int *rp_end ; /* a pointer to the end of a row */ - int last_row ; /* previous row */ + Index col ; /* a column index */ + Index row ; /* a row index */ + Index *cp ; /* a column pointer */ + Index *cp_end ; /* a pointer to the end of a column */ + Index *rp ; /* a row pointer */ + Index *rp_end ; /* a pointer to the end of a row */ + Index last_row ; /* previous row */ - /* === Initialize columns, and check column pointers ==================== */ - - for (col = 0 ; col < n_col ; col++) - { - Col [col].start = p [col] ; - Col [col].length = p [col+1] - p [col] ; + /* === Initialize columns, and check column pointers ==================== */ - if (Col [col].length < 0) + for (col = 0 ; col < n_col ; col++) { + Col [col].start = p [col] ; + Col [col].length = p [col+1] - p [col] ; + + if (Col [col].length < 0) + { /* column pointers must be non-decreasing */ stats [COLAMD_STATUS] = COLAMD_ERROR_col_length_negative ; stats [COLAMD_INFO1] = col ; stats [COLAMD_INFO2] = Col [col].length ; COLAMD_DEBUG0 (("colamd: col %d length %d < 0\n", col, Col [col].length)) ; return (false) ; - } - - Col [col].shared1.thickness = 1 ; - Col [col].shared2.score = 0 ; - Col [col].shared3.prev = COLAMD_EMPTY ; - Col [col].shared4.degree_next = COLAMD_EMPTY ; } - /* p [0..n_col] no longer needed, used as "head" in subsequent routines */ - - /* === Scan columns, compute row degrees, and check row indices ========= */ + Col [col].shared1.thickness = 1 ; + Col [col].shared2.score = 0 ; + Col [col].shared3.prev = COLAMD_EMPTY ; + Col [col].shared4.degree_next = COLAMD_EMPTY ; + } - stats [COLAMD_INFO3] = 0 ; /* number of duplicate or unsorted row indices*/ + /* p [0..n_col] no longer needed, used as "head" in subsequent routines */ - for (row = 0 ; row < n_row ; row++) - { - Row [row].length = 0 ; - Row [row].shared2.mark = -1 ; - } + /* === Scan columns, compute row degrees, and check row indices ========= */ - for (col = 0 ; col < n_col ; col++) - { - last_row = -1 ; + stats [COLAMD_INFO3] = 0 ; /* number of duplicate or unsorted row indices*/ - cp = &A [p [col]] ; - cp_end = &A [p [col+1]] ; + for (row = 0 ; row < n_row ; row++) + { + Row [row].length = 0 ; + Row [row].shared2.mark = -1 ; + } - while (cp < cp_end) + for (col = 0 ; col < n_col ; col++) { + last_row = -1 ; + + cp = &A [p [col]] ; + cp_end = &A [p [col+1]] ; + + while (cp < cp_end) + { row = *cp++ ; /* make sure row indices within range */ if (row < 0 || row >= n_row) { - stats [COLAMD_STATUS] = COLAMD_ERROR_row_index_out_of_bounds ; - stats [COLAMD_INFO1] = col ; - stats [COLAMD_INFO2] = row ; - stats [COLAMD_INFO3] = n_row ; - COLAMD_DEBUG0 (("colamd: row %d col %d out of bounds\n", row, col)) ; - return (false) ; + stats [COLAMD_STATUS] = COLAMD_ERROR_row_index_out_of_bounds ; + stats [COLAMD_INFO1] = col ; + stats [COLAMD_INFO2] = row ; + stats [COLAMD_INFO3] = n_row ; + COLAMD_DEBUG0 (("colamd: row %d col %d out of bounds\n", row, col)) ; + return (false) ; } if (row <= last_row || Row [row].shared2.mark == col) { - /* row index are unsorted or repeated (or both), thus col */ - /* is jumbled. This is a notice, not an error condition. */ - stats [COLAMD_STATUS] = COLAMD_OK_BUT_JUMBLED ; - stats [COLAMD_INFO1] = col ; - stats [COLAMD_INFO2] = row ; - (stats [COLAMD_INFO3]) ++ ; - COLAMD_DEBUG1 (("colamd: row %d col %d unsorted/duplicate\n",row,col)); + /* row index are unsorted or repeated (or both), thus col */ + /* is jumbled. This is a notice, not an error condition. */ + stats [COLAMD_STATUS] = COLAMD_OK_BUT_JUMBLED ; + stats [COLAMD_INFO1] = col ; + stats [COLAMD_INFO2] = row ; + (stats [COLAMD_INFO3]) ++ ; + COLAMD_DEBUG1 (("colamd: row %d col %d unsorted/duplicate\n",row,col)); } if (Row [row].shared2.mark != col) { - Row [row].length++ ; + Row [row].length++ ; } else { - /* this is a repeated entry in the column, */ - /* it will be removed */ - Col [col].length-- ; + /* this is a repeated entry in the column, */ + /* it will be removed */ + Col [col].length-- ; } /* mark the row as having been seen in this column */ Row [row].shared2.mark = col ; last_row = row ; - } } + } - /* === Compute row pointers ============================================= */ + /* === Compute row pointers ============================================= */ - /* row form of the matrix starts directly after the column */ - /* form of matrix in A */ - Row [0].start = p [n_col] ; - Row [0].shared1.p = Row [0].start ; - Row [0].shared2.mark = -1 ; - for (row = 1 ; row < n_row ; row++) - { - Row [row].start = Row [row-1].start + Row [row-1].length ; - Row [row].shared1.p = Row [row].start ; - Row [row].shared2.mark = -1 ; - } + /* row form of the matrix starts directly after the column */ + /* form of matrix in A */ + Row [0].start = p [n_col] ; + Row [0].shared1.p = Row [0].start ; + Row [0].shared2.mark = -1 ; + for (row = 1 ; row < n_row ; row++) + { + Row [row].start = Row [row-1].start + Row [row-1].length ; + Row [row].shared1.p = Row [row].start ; + Row [row].shared2.mark = -1 ; + } - /* === Create row form ================================================== */ + /* === Create row form ================================================== */ - if (stats [COLAMD_STATUS] == COLAMD_OK_BUT_JUMBLED) - { - /* if cols jumbled, watch for repeated row indices */ - for (col = 0 ; col < n_col ; col++) + if (stats [COLAMD_STATUS] == COLAMD_OK_BUT_JUMBLED) { + /* if cols jumbled, watch for repeated row indices */ + for (col = 0 ; col < n_col ; col++) + { cp = &A [p [col]] ; cp_end = &A [p [col+1]] ; while (cp < cp_end) { - row = *cp++ ; - if (Row [row].shared2.mark != col) - { - A [(Row [row].shared1.p)++] = col ; - Row [row].shared2.mark = col ; - } + row = *cp++ ; + if (Row [row].shared2.mark != col) + { + A [(Row [row].shared1.p)++] = col ; + Row [row].shared2.mark = col ; + } } - } } - else - { - /* if cols not jumbled, we don't need the mark (this is faster) */ - for (col = 0 ; col < n_col ; col++) + } + else { + /* if cols not jumbled, we don't need the mark (this is faster) */ + for (col = 0 ; col < n_col ; col++) + { cp = &A [p [col]] ; cp_end = &A [p [col+1]] ; while (cp < cp_end) { - A [(Row [*cp++].shared1.p)++] = col ; + A [(Row [*cp++].shared1.p)++] = col ; } - } } + } - /* === Clear the row marks and set row degrees ========================== */ + /* === Clear the row marks and set row degrees ========================== */ - for (row = 0 ; row < n_row ; row++) - { - Row [row].shared2.mark = 0 ; - Row [row].shared1.degree = Row [row].length ; - } + for (row = 0 ; row < n_row ; row++) + { + Row [row].shared2.mark = 0 ; + Row [row].shared1.degree = Row [row].length ; + } - /* === See if we need to re-create columns ============================== */ + /* === See if we need to re-create columns ============================== */ - if (stats [COLAMD_STATUS] == COLAMD_OK_BUT_JUMBLED) - { - COLAMD_DEBUG0 (("colamd: reconstructing column form, matrix jumbled\n")) ; + if (stats [COLAMD_STATUS] == COLAMD_OK_BUT_JUMBLED) + { + COLAMD_DEBUG0 (("colamd: reconstructing column form, matrix jumbled\n")) ; - /* === Compute col pointers ========================================= */ + /* === Compute col pointers ========================================= */ - /* col form of the matrix starts at A [0]. */ - /* Note, we may have a gap between the col form and the row */ - /* form if there were duplicate entries, if so, it will be */ - /* removed upon the first garbage collection */ - Col [0].start = 0 ; - p [0] = Col [0].start ; - for (col = 1 ; col < n_col ; col++) - { + /* col form of the matrix starts at A [0]. */ + /* Note, we may have a gap between the col form and the row */ + /* form if there were duplicate entries, if so, it will be */ + /* removed upon the first garbage collection */ + Col [0].start = 0 ; + p [0] = Col [0].start ; + for (col = 1 ; col < n_col ; col++) + { /* note that the lengths here are for pruned columns, i.e. */ /* no duplicate row indices will exist for these columns */ Col [col].start = Col [col-1].start + Col [col-1].length ; p [col] = Col [col].start ; - } + } - /* === Re-create col form =========================================== */ + /* === Re-create col form =========================================== */ - for (row = 0 ; row < n_row ; row++) - { + for (row = 0 ; row < n_row ; row++) + { rp = &A [Row [row].start] ; rp_end = rp + Row [row].length ; while (rp < rp_end) { - A [(p [*rp++])++] = row ; + A [(p [*rp++])++] = row ; } - } } + } - /* === Done. Matrix is not (or no longer) jumbled ====================== */ + /* === Done. Matrix is not (or no longer) jumbled ====================== */ - return (true) ; + return (true) ; } @@ -695,83 +698,83 @@ static bool colamd(int n_row, int n_col, int Alen, int *A, int *p, double knobs[ /* ========================================================================== */ /* - Kills dense or empty columns and rows, calculates an initial score for - each column, and places all columns in the degree lists. Not user-callable. + Kills dense or empty columns and rows, calculates an initial score for + each column, and places all columns in the degree lists. Not user-callable. */ - +template static void init_scoring -( + ( /* === Parameters ======================================================= */ - int n_row, /* number of rows of A */ - int n_col, /* number of columns of A */ - Colamd_Row Row [], /* of size n_row+1 */ - colamd_col Col [], /* of size n_col+1 */ - int A [], /* column form and row form of A */ - int head [], /* of size n_col+1 */ + Index n_row, /* number of rows of A */ + Index n_col, /* number of columns of A */ + Colamd_Row Row [], /* of size n_row+1 */ + colamd_col Col [], /* of size n_col+1 */ + Index A [], /* column form and row form of A */ + Index head [], /* of size n_col+1 */ double knobs [COLAMD_KNOBS],/* parameters */ - int *p_n_row2, /* number of non-dense, non-empty rows */ - int *p_n_col2, /* number of non-dense, non-empty columns */ - int *p_max_deg /* maximum row degree */ -) + Index *p_n_row2, /* number of non-dense, non-empty rows */ + Index *p_n_col2, /* number of non-dense, non-empty columns */ + Index *p_max_deg /* maximum row degree */ + ) { - /* === Local variables ================================================== */ - - int c ; /* a column index */ - int r, row ; /* a row index */ - int *cp ; /* a column pointer */ - int deg ; /* degree of a row or column */ - int *cp_end ; /* a pointer to the end of a column */ - int *new_cp ; /* new column pointer */ - int col_length ; /* length of pruned column */ - int score ; /* current column score */ - int n_col2 ; /* number of non-dense, non-empty columns */ - int n_row2 ; /* number of non-dense, non-empty rows */ - int dense_row_count ; /* remove rows with more entries than this */ - int dense_col_count ; /* remove cols with more entries than this */ - int min_score ; /* smallest column score */ - int max_deg ; /* maximum row degree */ - int next_col ; /* Used to add to degree list.*/ - - - /* === Extract knobs ==================================================== */ - - dense_row_count = COLAMD_MAX (0, COLAMD_MIN (knobs [COLAMD_DENSE_ROW] * n_col, n_col)) ; - dense_col_count = COLAMD_MAX (0, COLAMD_MIN (knobs [COLAMD_DENSE_COL] * n_row, n_row)) ; - COLAMD_DEBUG1 (("colamd: densecount: %d %d\n", dense_row_count, dense_col_count)) ; - max_deg = 0 ; - n_col2 = n_col ; - n_row2 = n_row ; - - /* === Kill empty columns =============================================== */ - - /* Put the empty columns at the end in their natural order, so that LU */ - /* factorization can proceed as far as possible. */ - for (c = n_col-1 ; c >= 0 ; c--) - { - deg = Col [c].length ; - if (deg == 0) + /* === Local variables ================================================== */ + + Index c ; /* a column index */ + Index r, row ; /* a row index */ + Index *cp ; /* a column pointer */ + Index deg ; /* degree of a row or column */ + Index *cp_end ; /* a pointer to the end of a column */ + Index *new_cp ; /* new column pointer */ + Index col_length ; /* length of pruned column */ + Index score ; /* current column score */ + Index n_col2 ; /* number of non-dense, non-empty columns */ + Index n_row2 ; /* number of non-dense, non-empty rows */ + Index dense_row_count ; /* remove rows with more entries than this */ + Index dense_col_count ; /* remove cols with more entries than this */ + Index min_score ; /* smallest column score */ + Index max_deg ; /* maximum row degree */ + Index next_col ; /* Used to add to degree list.*/ + + + /* === Extract knobs ==================================================== */ + + dense_row_count = COLAMD_MAX (0, COLAMD_MIN (knobs [COLAMD_DENSE_ROW] * n_col, n_col)) ; + dense_col_count = COLAMD_MAX (0, COLAMD_MIN (knobs [COLAMD_DENSE_COL] * n_row, n_row)) ; + COLAMD_DEBUG1 (("colamd: densecount: %d %d\n", dense_row_count, dense_col_count)) ; + max_deg = 0 ; + n_col2 = n_col ; + n_row2 = n_row ; + + /* === Kill empty columns =============================================== */ + + /* Put the empty columns at the end in their natural order, so that LU */ + /* factorization can proceed as far as possible. */ + for (c = n_col-1 ; c >= 0 ; c--) { + deg = Col [c].length ; + if (deg == 0) + { /* this is a empty column, kill and order it last */ Col [c].shared2.order = --n_col2 ; KILL_PRINCIPAL_COL (c) ; - } } - COLAMD_DEBUG1 (("colamd: null columns killed: %d\n", n_col - n_col2)) ; + } + COLAMD_DEBUG1 (("colamd: null columns killed: %d\n", n_col - n_col2)) ; - /* === Kill dense columns =============================================== */ + /* === Kill dense columns =============================================== */ - /* Put the dense columns at the end, in their natural order */ - for (c = n_col-1 ; c >= 0 ; c--) - { - /* skip any dead columns */ - if (COL_IS_DEAD (c)) + /* Put the dense columns at the end, in their natural order */ + for (c = n_col-1 ; c >= 0 ; c--) { + /* skip any dead columns */ + if (COL_IS_DEAD (c)) + { continue ; - } - deg = Col [c].length ; - if (deg > dense_col_count) - { + } + deg = Col [c].length ; + if (deg > dense_col_count) + { /* this is a dense column, kill and order it last */ Col [c].shared2.order = --n_col2 ; /* decrement the row degrees */ @@ -779,60 +782,60 @@ static void init_scoring cp_end = cp + Col [c].length ; while (cp < cp_end) { - Row [*cp++].shared1.degree-- ; + Row [*cp++].shared1.degree-- ; } KILL_PRINCIPAL_COL (c) ; - } } - COLAMD_DEBUG1 (("colamd: Dense and null columns killed: %d\n", n_col - n_col2)) ; + } + COLAMD_DEBUG1 (("colamd: Dense and null columns killed: %d\n", n_col - n_col2)) ; - /* === Kill dense and empty rows ======================================== */ + /* === Kill dense and empty rows ======================================== */ - for (r = 0 ; r < n_row ; r++) - { - deg = Row [r].shared1.degree ; - COLAMD_ASSERT (deg >= 0 && deg <= n_col) ; - if (deg > dense_row_count || deg == 0) + for (r = 0 ; r < n_row ; r++) { + deg = Row [r].shared1.degree ; + COLAMD_ASSERT (deg >= 0 && deg <= n_col) ; + if (deg > dense_row_count || deg == 0) + { /* kill a dense or empty row */ KILL_ROW (r) ; --n_row2 ; - } - else - { + } + else + { /* keep track of max degree of remaining rows */ max_deg = COLAMD_MAX (max_deg, deg) ; - } } - COLAMD_DEBUG1 (("colamd: Dense and null rows killed: %d\n", n_row - n_row2)) ; + } + COLAMD_DEBUG1 (("colamd: Dense and null rows killed: %d\n", n_row - n_row2)) ; - /* === Compute initial column scores ==================================== */ + /* === Compute initial column scores ==================================== */ - /* At this point the row degrees are accurate. They reflect the number */ - /* of "live" (non-dense) columns in each row. No empty rows exist. */ - /* Some "live" columns may contain only dead rows, however. These are */ - /* pruned in the code below. */ + /* At this point the row degrees are accurate. They reflect the number */ + /* of "live" (non-dense) columns in each row. No empty rows exist. */ + /* Some "live" columns may contain only dead rows, however. These are */ + /* pruned in the code below. */ - /* now find the initial matlab score for each column */ - for (c = n_col-1 ; c >= 0 ; c--) - { - /* skip dead column */ - if (COL_IS_DEAD (c)) + /* now find the initial matlab score for each column */ + for (c = n_col-1 ; c >= 0 ; c--) { + /* skip dead column */ + if (COL_IS_DEAD (c)) + { continue ; - } - score = 0 ; - cp = &A [Col [c].start] ; - new_cp = cp ; - cp_end = cp + Col [c].length ; - while (cp < cp_end) - { + } + score = 0 ; + cp = &A [Col [c].start] ; + new_cp = cp ; + cp_end = cp + Col [c].length ; + while (cp < cp_end) + { /* get a row */ row = *cp++ ; /* skip if dead */ if (ROW_IS_DEAD (row)) { - continue ; + continue ; } /* compact the column */ *new_cp++ = row ; @@ -840,52 +843,52 @@ static void init_scoring score += Row [row].shared1.degree - 1 ; /* guard against integer overflow */ score = COLAMD_MIN (score, n_col) ; - } - /* determine pruned column length */ - col_length = (int) (new_cp - &A [Col [c].start]) ; - if (col_length == 0) - { + } + /* determine pruned column length */ + col_length = (Index) (new_cp - &A [Col [c].start]) ; + if (col_length == 0) + { /* a newly-made null column (all rows in this col are "dense" */ /* and have already been killed) */ COLAMD_DEBUG2 (("Newly null killed: %d\n", c)) ; Col [c].shared2.order = --n_col2 ; KILL_PRINCIPAL_COL (c) ; - } - else - { + } + else + { /* set column length and set score */ COLAMD_ASSERT (score >= 0) ; COLAMD_ASSERT (score <= n_col) ; Col [c].length = col_length ; Col [c].shared2.score = score ; - } } - COLAMD_DEBUG1 (("colamd: Dense, null, and newly-null columns killed: %d\n", - n_col-n_col2)) ; + } + COLAMD_DEBUG1 (("colamd: Dense, null, and newly-null columns killed: %d\n", + n_col-n_col2)) ; - /* At this point, all empty rows and columns are dead. All live columns */ - /* are "clean" (containing no dead rows) and simplicial (no supercolumns */ - /* yet). Rows may contain dead columns, but all live rows contain at */ - /* least one live column. */ + /* At this point, all empty rows and columns are dead. All live columns */ + /* are "clean" (containing no dead rows) and simplicial (no supercolumns */ + /* yet). Rows may contain dead columns, but all live rows contain at */ + /* least one live column. */ - /* === Initialize degree lists ========================================== */ + /* === Initialize degree lists ========================================== */ - /* clear the hash buckets */ - for (c = 0 ; c <= n_col ; c++) - { - head [c] = COLAMD_EMPTY ; - } - min_score = n_col ; - /* place in reverse order, so low column indices are at the front */ - /* of the lists. This is to encourage natural tie-breaking */ - for (c = n_col-1 ; c >= 0 ; c--) - { - /* only add principal columns to degree lists */ - if (COL_IS_ALIVE (c)) + /* clear the hash buckets */ + for (c = 0 ; c <= n_col ; c++) + { + head [c] = COLAMD_EMPTY ; + } + min_score = n_col ; + /* place in reverse order, so low column indices are at the front */ + /* of the lists. This is to encourage natural tie-breaking */ + for (c = n_col-1 ; c >= 0 ; c--) { + /* only add principal columns to degree lists */ + if (COL_IS_ALIVE (c)) + { COLAMD_DEBUG4 (("place %d score %d minscore %d ncol %d\n", - c, Col [c].shared2.score, min_score, n_col)) ; + c, Col [c].shared2.score, min_score, n_col)) ; /* === Add columns score to DList =============================== */ @@ -906,7 +909,7 @@ static void init_scoring /* previous pointer to this new column */ if (next_col != COLAMD_EMPTY) { - Col [next_col].shared3.prev = c ; + Col [next_col].shared3.prev = c ; } head [score] = c ; @@ -914,15 +917,15 @@ static void init_scoring min_score = COLAMD_MIN (min_score, score) ; - } } + } - /* === Return number of remaining columns, and max row degree =========== */ + /* === Return number of remaining columns, and max row degree =========== */ - *p_n_col2 = n_col2 ; - *p_n_row2 = n_row2 ; - *p_max_deg = max_deg ; + *p_n_col2 = n_col2 ; + *p_n_row2 = n_row2 ; + *p_max_deg = max_deg ; } @@ -931,115 +934,115 @@ static void init_scoring /* ========================================================================== */ /* - Order the principal columns of the supercolumn form of the matrix - (no supercolumns on input). Uses a minimum approximate column minimum - degree ordering method. Not user-callable. + Order the principal columns of the supercolumn form of the matrix + (no supercolumns on input). Uses a minimum approximate column minimum + degree ordering method. Not user-callable. */ - -static int find_ordering /* return the number of garbage collections */ -( +template +static Index find_ordering /* return the number of garbage collections */ + ( /* === Parameters ======================================================= */ - int n_row, /* number of rows of A */ - int n_col, /* number of columns of A */ - int Alen, /* size of A, 2*nnz + n_col or larger */ - Colamd_Row Row [], /* of size n_row+1 */ - colamd_col Col [], /* of size n_col+1 */ - int A [], /* column form and row form of A */ - int head [], /* of size n_col+1 */ - int n_col2, /* Remaining columns to order */ - int max_deg, /* Maximum row degree */ - int pfree /* index of first free slot (2*nnz on entry) */ -) + Index n_row, /* number of rows of A */ + Index n_col, /* number of columns of A */ + Index Alen, /* size of A, 2*nnz + n_col or larger */ + Colamd_Row Row [], /* of size n_row+1 */ + colamd_col Col [], /* of size n_col+1 */ + Index A [], /* column form and row form of A */ + Index head [], /* of size n_col+1 */ + Index n_col2, /* Remaining columns to order */ + Index max_deg, /* Maximum row degree */ + Index pfree /* index of first free slot (2*nnz on entry) */ + ) { - /* === Local variables ================================================== */ - - int k ; /* current pivot ordering step */ - int pivot_col ; /* current pivot column */ - int *cp ; /* a column pointer */ - int *rp ; /* a row pointer */ - int pivot_row ; /* current pivot row */ - int *new_cp ; /* modified column pointer */ - int *new_rp ; /* modified row pointer */ - int pivot_row_start ; /* pointer to start of pivot row */ - int pivot_row_degree ; /* number of columns in pivot row */ - int pivot_row_length ; /* number of supercolumns in pivot row */ - int pivot_col_score ; /* score of pivot column */ - int needed_memory ; /* free space needed for pivot row */ - int *cp_end ; /* pointer to the end of a column */ - int *rp_end ; /* pointer to the end of a row */ - int row ; /* a row index */ - int col ; /* a column index */ - int max_score ; /* maximum possible score */ - int cur_score ; /* score of current column */ - unsigned int hash ; /* hash value for supernode detection */ - int head_column ; /* head of hash bucket */ - int first_col ; /* first column in hash bucket */ - int tag_mark ; /* marker value for mark array */ - int row_mark ; /* Row [row].shared2.mark */ - int set_difference ; /* set difference size of row with pivot row */ - int min_score ; /* smallest column score */ - int col_thickness ; /* "thickness" (no. of columns in a supercol) */ - int max_mark ; /* maximum value of tag_mark */ - int pivot_col_thickness ; /* number of columns represented by pivot col */ - int prev_col ; /* Used by Dlist operations. */ - int next_col ; /* Used by Dlist operations. */ - int ngarbage ; /* number of garbage collections performed */ - - - /* === Initialization and clear mark ==================================== */ - - max_mark = INT_MAX - n_col ; /* INT_MAX defined in */ - tag_mark = clear_mark (n_row, Row) ; - min_score = 0 ; - ngarbage = 0 ; - COLAMD_DEBUG1 (("colamd: Ordering, n_col2=%d\n", n_col2)) ; - - /* === Order the columns ================================================ */ - - for (k = 0 ; k < n_col2 ; /* 'k' is incremented below */) - { + /* === Local variables ================================================== */ + + Index k ; /* current pivot ordering step */ + Index pivot_col ; /* current pivot column */ + Index *cp ; /* a column pointer */ + Index *rp ; /* a row pointer */ + Index pivot_row ; /* current pivot row */ + Index *new_cp ; /* modified column pointer */ + Index *new_rp ; /* modified row pointer */ + Index pivot_row_start ; /* pointer to start of pivot row */ + Index pivot_row_degree ; /* number of columns in pivot row */ + Index pivot_row_length ; /* number of supercolumns in pivot row */ + Index pivot_col_score ; /* score of pivot column */ + Index needed_memory ; /* free space needed for pivot row */ + Index *cp_end ; /* pointer to the end of a column */ + Index *rp_end ; /* pointer to the end of a row */ + Index row ; /* a row index */ + Index col ; /* a column index */ + Index max_score ; /* maximum possible score */ + Index cur_score ; /* score of current column */ + unsigned int hash ; /* hash value for supernode detection */ + Index head_column ; /* head of hash bucket */ + Index first_col ; /* first column in hash bucket */ + Index tag_mark ; /* marker value for mark array */ + Index row_mark ; /* Row [row].shared2.mark */ + Index set_difference ; /* set difference size of row with pivot row */ + Index min_score ; /* smallest column score */ + Index col_thickness ; /* "thickness" (no. of columns in a supercol) */ + Index max_mark ; /* maximum value of tag_mark */ + Index pivot_col_thickness ; /* number of columns represented by pivot col */ + Index prev_col ; /* Used by Dlist operations. */ + Index next_col ; /* Used by Dlist operations. */ + Index ngarbage ; /* number of garbage collections performed */ + + + /* === Initialization and clear mark ==================================== */ + + max_mark = INT_MAX - n_col ; /* INT_MAX defined in */ + tag_mark = clear_mark (n_row, Row) ; + min_score = 0 ; + ngarbage = 0 ; + COLAMD_DEBUG1 (("colamd: Ordering, n_col2=%d\n", n_col2)) ; + + /* === Order the columns ================================================ */ + + for (k = 0 ; k < n_col2 ; /* 'k' is incremented below */) + { - /* === Select pivot column, and order it ============================ */ + /* === Select pivot column, and order it ============================ */ - /* make sure degree list isn't empty */ - COLAMD_ASSERT (min_score >= 0) ; - COLAMD_ASSERT (min_score <= n_col) ; - COLAMD_ASSERT (head [min_score] >= COLAMD_EMPTY) ; + /* make sure degree list isn't empty */ + COLAMD_ASSERT (min_score >= 0) ; + COLAMD_ASSERT (min_score <= n_col) ; + COLAMD_ASSERT (head [min_score] >= COLAMD_EMPTY) ; - /* get pivot column from head of minimum degree list */ - while (head [min_score] == COLAMD_EMPTY && min_score < n_col) - { + /* get pivot column from head of minimum degree list */ + while (head [min_score] == COLAMD_EMPTY && min_score < n_col) + { min_score++ ; - } - pivot_col = head [min_score] ; - COLAMD_ASSERT (pivot_col >= 0 && pivot_col <= n_col) ; - next_col = Col [pivot_col].shared4.degree_next ; - head [min_score] = next_col ; - if (next_col != COLAMD_EMPTY) - { + } + pivot_col = head [min_score] ; + COLAMD_ASSERT (pivot_col >= 0 && pivot_col <= n_col) ; + next_col = Col [pivot_col].shared4.degree_next ; + head [min_score] = next_col ; + if (next_col != COLAMD_EMPTY) + { Col [next_col].shared3.prev = COLAMD_EMPTY ; - } + } - COLAMD_ASSERT (COL_IS_ALIVE (pivot_col)) ; - COLAMD_DEBUG3 (("Pivot col: %d\n", pivot_col)) ; + COLAMD_ASSERT (COL_IS_ALIVE (pivot_col)) ; + COLAMD_DEBUG3 (("Pivot col: %d\n", pivot_col)) ; - /* remember score for defrag check */ - pivot_col_score = Col [pivot_col].shared2.score ; + /* remember score for defrag check */ + pivot_col_score = Col [pivot_col].shared2.score ; - /* the pivot column is the kth column in the pivot order */ - Col [pivot_col].shared2.order = k ; + /* the pivot column is the kth column in the pivot order */ + Col [pivot_col].shared2.order = k ; - /* increment order count by column thickness */ - pivot_col_thickness = Col [pivot_col].shared1.thickness ; - k += pivot_col_thickness ; - COLAMD_ASSERT (pivot_col_thickness > 0) ; + /* increment order count by column thickness */ + pivot_col_thickness = Col [pivot_col].shared1.thickness ; + k += pivot_col_thickness ; + COLAMD_ASSERT (pivot_col_thickness > 0) ; - /* === Garbage_collection, if necessary ============================= */ + /* === Garbage_collection, if necessary ============================= */ - needed_memory = COLAMD_MIN (pivot_col_score, n_col - k) ; - if (pfree + needed_memory >= Alen) - { + needed_memory = COLAMD_MIN (pivot_col_score, n_col - k) ; + if (pfree + needed_memory >= Alen) + { pfree = garbage_collection (n_row, n_col, Row, Col, A, &A [pfree]) ; ngarbage++ ; /* after garbage collection we will have enough */ @@ -1047,119 +1050,119 @@ static int find_ordering /* return the number of garbage collections */ /* garbage collection has wiped out the Row[].shared2.mark array */ tag_mark = clear_mark (n_row, Row) ; - } + } - /* === Compute pivot row pattern ==================================== */ + /* === Compute pivot row pattern ==================================== */ - /* get starting location for this new merged row */ - pivot_row_start = pfree ; + /* get starting location for this new merged row */ + pivot_row_start = pfree ; - /* initialize new row counts to zero */ - pivot_row_degree = 0 ; + /* initialize new row counts to zero */ + pivot_row_degree = 0 ; - /* tag pivot column as having been visited so it isn't included */ - /* in merged pivot row */ - Col [pivot_col].shared1.thickness = -pivot_col_thickness ; + /* tag pivot column as having been visited so it isn't included */ + /* in merged pivot row */ + Col [pivot_col].shared1.thickness = -pivot_col_thickness ; - /* pivot row is the union of all rows in the pivot column pattern */ - cp = &A [Col [pivot_col].start] ; - cp_end = cp + Col [pivot_col].length ; - while (cp < cp_end) - { + /* pivot row is the union of all rows in the pivot column pattern */ + cp = &A [Col [pivot_col].start] ; + cp_end = cp + Col [pivot_col].length ; + while (cp < cp_end) + { /* get a row */ row = *cp++ ; COLAMD_DEBUG4 (("Pivot col pattern %d %d\n", ROW_IS_ALIVE (row), row)) ; /* skip if row is dead */ if (ROW_IS_DEAD (row)) { - continue ; + continue ; } rp = &A [Row [row].start] ; rp_end = rp + Row [row].length ; while (rp < rp_end) { - /* get a column */ - col = *rp++ ; - /* add the column, if alive and untagged */ - col_thickness = Col [col].shared1.thickness ; - if (col_thickness > 0 && COL_IS_ALIVE (col)) - { - /* tag column in pivot row */ - Col [col].shared1.thickness = -col_thickness ; - COLAMD_ASSERT (pfree < Alen) ; - /* place column in pivot row */ - A [pfree++] = col ; - pivot_row_degree += col_thickness ; - } + /* get a column */ + col = *rp++ ; + /* add the column, if alive and untagged */ + col_thickness = Col [col].shared1.thickness ; + if (col_thickness > 0 && COL_IS_ALIVE (col)) + { + /* tag column in pivot row */ + Col [col].shared1.thickness = -col_thickness ; + COLAMD_ASSERT (pfree < Alen) ; + /* place column in pivot row */ + A [pfree++] = col ; + pivot_row_degree += col_thickness ; + } } - } + } - /* clear tag on pivot column */ - Col [pivot_col].shared1.thickness = pivot_col_thickness ; - max_deg = COLAMD_MAX (max_deg, pivot_row_degree) ; + /* clear tag on pivot column */ + Col [pivot_col].shared1.thickness = pivot_col_thickness ; + max_deg = COLAMD_MAX (max_deg, pivot_row_degree) ; - /* === Kill all rows used to construct pivot row ==================== */ + /* === Kill all rows used to construct pivot row ==================== */ - /* also kill pivot row, temporarily */ - cp = &A [Col [pivot_col].start] ; - cp_end = cp + Col [pivot_col].length ; - while (cp < cp_end) - { + /* also kill pivot row, temporarily */ + cp = &A [Col [pivot_col].start] ; + cp_end = cp + Col [pivot_col].length ; + while (cp < cp_end) + { /* may be killing an already dead row */ row = *cp++ ; COLAMD_DEBUG3 (("Kill row in pivot col: %d\n", row)) ; KILL_ROW (row) ; - } + } - /* === Select a row index to use as the new pivot row =============== */ + /* === Select a row index to use as the new pivot row =============== */ - pivot_row_length = pfree - pivot_row_start ; - if (pivot_row_length > 0) - { + pivot_row_length = pfree - pivot_row_start ; + if (pivot_row_length > 0) + { /* pick the "pivot" row arbitrarily (first row in col) */ pivot_row = A [Col [pivot_col].start] ; COLAMD_DEBUG3 (("Pivotal row is %d\n", pivot_row)) ; - } - else - { + } + else + { /* there is no pivot row, since it is of zero length */ pivot_row = COLAMD_EMPTY ; COLAMD_ASSERT (pivot_row_length == 0) ; - } - COLAMD_ASSERT (Col [pivot_col].length > 0 || pivot_row_length == 0) ; + } + COLAMD_ASSERT (Col [pivot_col].length > 0 || pivot_row_length == 0) ; - /* === Approximate degree computation =============================== */ + /* === Approximate degree computation =============================== */ - /* Here begins the computation of the approximate degree. The column */ - /* score is the sum of the pivot row "length", plus the size of the */ - /* set differences of each row in the column minus the pattern of the */ - /* pivot row itself. The column ("thickness") itself is also */ - /* excluded from the column score (we thus use an approximate */ - /* external degree). */ + /* Here begins the computation of the approximate degree. The column */ + /* score is the sum of the pivot row "length", plus the size of the */ + /* set differences of each row in the column minus the pattern of the */ + /* pivot row itself. The column ("thickness") itself is also */ + /* excluded from the column score (we thus use an approximate */ + /* external degree). */ - /* The time taken by the following code (compute set differences, and */ - /* add them up) is proportional to the size of the data structure */ - /* being scanned - that is, the sum of the sizes of each column in */ - /* the pivot row. Thus, the amortized time to compute a column score */ - /* is proportional to the size of that column (where size, in this */ - /* context, is the column "length", or the number of row indices */ - /* in that column). The number of row indices in a column is */ - /* monotonically non-decreasing, from the length of the original */ - /* column on input to colamd. */ + /* The time taken by the following code (compute set differences, and */ + /* add them up) is proportional to the size of the data structure */ + /* being scanned - that is, the sum of the sizes of each column in */ + /* the pivot row. Thus, the amortized time to compute a column score */ + /* is proportional to the size of that column (where size, in this */ + /* context, is the column "length", or the number of row indices */ + /* in that column). The number of row indices in a column is */ + /* monotonically non-decreasing, from the length of the original */ + /* column on input to colamd. */ - /* === Compute set differences ====================================== */ + /* === Compute set differences ====================================== */ - COLAMD_DEBUG3 (("** Computing set differences phase. **\n")) ; + COLAMD_DEBUG3 (("** Computing set differences phase. **\n")) ; - /* pivot row is currently dead - it will be revived later. */ + /* pivot row is currently dead - it will be revived later. */ - COLAMD_DEBUG3 (("Pivot row: ")) ; - /* for each column in pivot row */ - rp = &A [pivot_row_start] ; - rp_end = rp + pivot_row_length ; - while (rp < rp_end) - { + COLAMD_DEBUG3 (("Pivot row: ")) ; + /* for each column in pivot row */ + rp = &A [pivot_row_start] ; + rp_end = rp + pivot_row_length ; + while (rp < rp_end) + { col = *rp++ ; COLAMD_ASSERT (COL_IS_ALIVE (col) && col != pivot_col) ; COLAMD_DEBUG3 (("Col: %d\n", col)) ; @@ -1179,15 +1182,15 @@ static int find_ordering /* return the number of garbage collections */ COLAMD_ASSERT (cur_score >= COLAMD_EMPTY) ; if (prev_col == COLAMD_EMPTY) { - head [cur_score] = next_col ; + head [cur_score] = next_col ; } else { - Col [prev_col].shared4.degree_next = next_col ; + Col [prev_col].shared4.degree_next = next_col ; } if (next_col != COLAMD_EMPTY) { - Col [next_col].shared3.prev = prev_col ; + Col [next_col].shared3.prev = prev_col ; } /* === Scan the column ========================================== */ @@ -1196,49 +1199,49 @@ static int find_ordering /* return the number of garbage collections */ cp_end = cp + Col [col].length ; while (cp < cp_end) { - /* get a row */ - row = *cp++ ; - row_mark = Row [row].shared2.mark ; - /* skip if dead */ - if (ROW_IS_MARKED_DEAD (row_mark)) - { - continue ; - } - COLAMD_ASSERT (row != pivot_row) ; - set_difference = row_mark - tag_mark ; - /* check if the row has been seen yet */ - if (set_difference < 0) - { - COLAMD_ASSERT (Row [row].shared1.degree <= max_deg) ; - set_difference = Row [row].shared1.degree ; - } - /* subtract column thickness from this row's set difference */ - set_difference -= col_thickness ; - COLAMD_ASSERT (set_difference >= 0) ; - /* absorb this row if the set difference becomes zero */ - if (set_difference == 0) - { - COLAMD_DEBUG3 (("aggressive absorption. Row: %d\n", row)) ; - KILL_ROW (row) ; - } - else - { - /* save the new mark */ - Row [row].shared2.mark = set_difference + tag_mark ; - } + /* get a row */ + row = *cp++ ; + row_mark = Row [row].shared2.mark ; + /* skip if dead */ + if (ROW_IS_MARKED_DEAD (row_mark)) + { + continue ; + } + COLAMD_ASSERT (row != pivot_row) ; + set_difference = row_mark - tag_mark ; + /* check if the row has been seen yet */ + if (set_difference < 0) + { + COLAMD_ASSERT (Row [row].shared1.degree <= max_deg) ; + set_difference = Row [row].shared1.degree ; + } + /* subtract column thickness from this row's set difference */ + set_difference -= col_thickness ; + COLAMD_ASSERT (set_difference >= 0) ; + /* absorb this row if the set difference becomes zero */ + if (set_difference == 0) + { + COLAMD_DEBUG3 (("aggressive absorption. Row: %d\n", row)) ; + KILL_ROW (row) ; + } + else + { + /* save the new mark */ + Row [row].shared2.mark = set_difference + tag_mark ; + } } - } + } - /* === Add up set differences for each column ======================= */ + /* === Add up set differences for each column ======================= */ - COLAMD_DEBUG3 (("** Adding set differences phase. **\n")) ; + COLAMD_DEBUG3 (("** Adding set differences phase. **\n")) ; - /* for each column in pivot row */ - rp = &A [pivot_row_start] ; - rp_end = rp + pivot_row_length ; - while (rp < rp_end) - { + /* for each column in pivot row */ + rp = &A [pivot_row_start] ; + rp_end = rp + pivot_row_length ; + while (rp < rp_end) + { /* get a column */ col = *rp++ ; COLAMD_ASSERT (COL_IS_ALIVE (col) && col != pivot_col) ; @@ -1253,119 +1256,119 @@ static int find_ordering /* return the number of garbage collections */ while (cp < cp_end) { - /* get a row */ - row = *cp++ ; - COLAMD_ASSERT(row >= 0 && row < n_row) ; - row_mark = Row [row].shared2.mark ; - /* skip if dead */ - if (ROW_IS_MARKED_DEAD (row_mark)) - { - continue ; - } - COLAMD_ASSERT (row_mark > tag_mark) ; - /* compact the column */ - *new_cp++ = row ; - /* compute hash function */ - hash += row ; - /* add set difference */ - cur_score += row_mark - tag_mark ; - /* integer overflow... */ - cur_score = COLAMD_MIN (cur_score, n_col) ; + /* get a row */ + row = *cp++ ; + COLAMD_ASSERT(row >= 0 && row < n_row) ; + row_mark = Row [row].shared2.mark ; + /* skip if dead */ + if (ROW_IS_MARKED_DEAD (row_mark)) + { + continue ; + } + COLAMD_ASSERT (row_mark > tag_mark) ; + /* compact the column */ + *new_cp++ = row ; + /* compute hash function */ + hash += row ; + /* add set difference */ + cur_score += row_mark - tag_mark ; + /* integer overflow... */ + cur_score = COLAMD_MIN (cur_score, n_col) ; } /* recompute the column's length */ - Col [col].length = (int) (new_cp - &A [Col [col].start]) ; + Col [col].length = (Index) (new_cp - &A [Col [col].start]) ; /* === Further mass elimination ================================= */ if (Col [col].length == 0) { - COLAMD_DEBUG4 (("further mass elimination. Col: %d\n", col)) ; - /* nothing left but the pivot row in this column */ - KILL_PRINCIPAL_COL (col) ; - pivot_row_degree -= Col [col].shared1.thickness ; - COLAMD_ASSERT (pivot_row_degree >= 0) ; - /* order it */ - Col [col].shared2.order = k ; - /* increment order count by column thickness */ - k += Col [col].shared1.thickness ; + COLAMD_DEBUG4 (("further mass elimination. Col: %d\n", col)) ; + /* nothing left but the pivot row in this column */ + KILL_PRINCIPAL_COL (col) ; + pivot_row_degree -= Col [col].shared1.thickness ; + COLAMD_ASSERT (pivot_row_degree >= 0) ; + /* order it */ + Col [col].shared2.order = k ; + /* increment order count by column thickness */ + k += Col [col].shared1.thickness ; } else { - /* === Prepare for supercolumn detection ==================== */ - - COLAMD_DEBUG4 (("Preparing supercol detection for Col: %d.\n", col)) ; - - /* save score so far */ - Col [col].shared2.score = cur_score ; - - /* add column to hash table, for supercolumn detection */ - hash %= n_col + 1 ; - - COLAMD_DEBUG4 ((" Hash = %d, n_col = %d.\n", hash, n_col)) ; - COLAMD_ASSERT (hash <= n_col) ; - - head_column = head [hash] ; - if (head_column > COLAMD_EMPTY) - { - /* degree list "hash" is non-empty, use prev (shared3) of */ - /* first column in degree list as head of hash bucket */ - first_col = Col [head_column].shared3.headhash ; - Col [head_column].shared3.headhash = col ; - } - else - { - /* degree list "hash" is empty, use head as hash bucket */ - first_col = - (head_column + 2) ; - head [hash] = - (col + 2) ; - } - Col [col].shared4.hash_next = first_col ; - - /* save hash function in Col [col].shared3.hash */ - Col [col].shared3.hash = (int) hash ; - COLAMD_ASSERT (COL_IS_ALIVE (col)) ; + /* === Prepare for supercolumn detection ==================== */ + + COLAMD_DEBUG4 (("Preparing supercol detection for Col: %d.\n", col)) ; + + /* save score so far */ + Col [col].shared2.score = cur_score ; + + /* add column to hash table, for supercolumn detection */ + hash %= n_col + 1 ; + + COLAMD_DEBUG4 ((" Hash = %d, n_col = %d.\n", hash, n_col)) ; + COLAMD_ASSERT (hash <= n_col) ; + + head_column = head [hash] ; + if (head_column > COLAMD_EMPTY) + { + /* degree list "hash" is non-empty, use prev (shared3) of */ + /* first column in degree list as head of hash bucket */ + first_col = Col [head_column].shared3.headhash ; + Col [head_column].shared3.headhash = col ; + } + else + { + /* degree list "hash" is empty, use head as hash bucket */ + first_col = - (head_column + 2) ; + head [hash] = - (col + 2) ; + } + Col [col].shared4.hash_next = first_col ; + + /* save hash function in Col [col].shared3.hash */ + Col [col].shared3.hash = (Index) hash ; + COLAMD_ASSERT (COL_IS_ALIVE (col)) ; } - } + } - /* The approximate external column degree is now computed. */ + /* The approximate external column degree is now computed. */ - /* === Supercolumn detection ======================================== */ + /* === Supercolumn detection ======================================== */ - COLAMD_DEBUG3 (("** Supercolumn detection phase. **\n")) ; + COLAMD_DEBUG3 (("** Supercolumn detection phase. **\n")) ; - detect_super_cols ( + detect_super_cols ( - Col, A, head, pivot_row_start, pivot_row_length) ; + Col, A, head, pivot_row_start, pivot_row_length) ; - /* === Kill the pivotal column ====================================== */ + /* === Kill the pivotal column ====================================== */ - KILL_PRINCIPAL_COL (pivot_col) ; + KILL_PRINCIPAL_COL (pivot_col) ; - /* === Clear mark =================================================== */ + /* === Clear mark =================================================== */ - tag_mark += (max_deg + 1) ; - if (tag_mark >= max_mark) - { + tag_mark += (max_deg + 1) ; + if (tag_mark >= max_mark) + { COLAMD_DEBUG2 (("clearing tag_mark\n")) ; tag_mark = clear_mark (n_row, Row) ; - } + } - /* === Finalize the new pivot row, and column scores ================ */ + /* === Finalize the new pivot row, and column scores ================ */ - COLAMD_DEBUG3 (("** Finalize scores phase. **\n")) ; + COLAMD_DEBUG3 (("** Finalize scores phase. **\n")) ; - /* for each column in pivot row */ - rp = &A [pivot_row_start] ; - /* compact the pivot row */ - new_rp = rp ; - rp_end = rp + pivot_row_length ; - while (rp < rp_end) - { + /* for each column in pivot row */ + rp = &A [pivot_row_start] ; + /* compact the pivot row */ + new_rp = rp ; + rp_end = rp + pivot_row_length ; + while (rp < rp_end) + { col = *rp++ ; /* skip dead columns */ if (COL_IS_DEAD (col)) { - continue ; + continue ; } *new_rp++ = col ; /* add new pivot row to column */ @@ -1403,32 +1406,32 @@ static int find_ordering /* return the number of garbage collections */ Col [col].shared3.prev = COLAMD_EMPTY ; if (next_col != COLAMD_EMPTY) { - Col [next_col].shared3.prev = col ; + Col [next_col].shared3.prev = col ; } head [cur_score] = col ; /* see if this score is less than current min */ min_score = COLAMD_MIN (min_score, cur_score) ; - } + } - /* === Resurrect the new pivot row ================================== */ + /* === Resurrect the new pivot row ================================== */ - if (pivot_row_degree > 0) - { + if (pivot_row_degree > 0) + { /* update pivot row length to reflect any cols that were killed */ /* during super-col detection and mass elimination */ Row [pivot_row].start = pivot_row_start ; - Row [pivot_row].length = (int) (new_rp - &A[pivot_row_start]) ; + Row [pivot_row].length = (Index) (new_rp - &A[pivot_row_start]) ; Row [pivot_row].shared1.degree = pivot_row_degree ; Row [pivot_row].shared2.mark = 0 ; /* pivot row is no longer dead */ - } } + } - /* === All principal columns have now been ordered ====================== */ + /* === All principal columns have now been ordered ====================== */ - return (ngarbage) ; + return (ngarbage) ; } @@ -1437,47 +1440,47 @@ static int find_ordering /* return the number of garbage collections */ /* ========================================================================== */ /* - The find_ordering routine has ordered all of the principal columns (the - representatives of the supercolumns). The non-principal columns have not - yet been ordered. This routine orders those columns by walking up the - parent tree (a column is a child of the column which absorbed it). The - final permutation vector is then placed in p [0 ... n_col-1], with p [0] - being the first column, and p [n_col-1] being the last. It doesn't look - like it at first glance, but be assured that this routine takes time linear - in the number of columns. Although not immediately obvious, the time - taken by this routine is O (n_col), that is, linear in the number of - columns. Not user-callable. + The find_ordering routine has ordered all of the principal columns (the + representatives of the supercolumns). The non-principal columns have not + yet been ordered. This routine orders those columns by walking up the + parent tree (a column is a child of the column which absorbed it). The + final permutation vector is then placed in p [0 ... n_col-1], with p [0] + being the first column, and p [n_col-1] being the last. It doesn't look + like it at first glance, but be assured that this routine takes time linear + in the number of columns. Although not immediately obvious, the time + taken by this routine is O (n_col), that is, linear in the number of + columns. Not user-callable. */ - +template static inline void order_children ( - /* === Parameters ======================================================= */ + /* === Parameters ======================================================= */ - int n_col, /* number of columns of A */ - colamd_col Col [], /* of size n_col+1 */ - int p [] /* p [0 ... n_col-1] is the column permutation*/ -) + Index n_col, /* number of columns of A */ + colamd_col Col [], /* of size n_col+1 */ + Index p [] /* p [0 ... n_col-1] is the column permutation*/ + ) { - /* === Local variables ================================================== */ + /* === Local variables ================================================== */ - int i ; /* loop counter for all columns */ - int c ; /* column index */ - int parent ; /* index of column's parent */ - int order ; /* column's order */ + Index i ; /* loop counter for all columns */ + Index c ; /* column index */ + Index parent ; /* index of column's parent */ + Index order ; /* column's order */ - /* === Order each non-principal column ================================== */ + /* === Order each non-principal column ================================== */ - for (i = 0 ; i < n_col ; i++) - { - /* find an un-ordered non-principal column */ - COLAMD_ASSERT (COL_IS_DEAD (i)) ; - if (!COL_IS_DEAD_PRINCIPAL (i) && Col [i].shared2.order == COLAMD_EMPTY) + for (i = 0 ; i < n_col ; i++) { + /* find an un-ordered non-principal column */ + COLAMD_ASSERT (COL_IS_DEAD (i)) ; + if (!COL_IS_DEAD_PRINCIPAL (i) && Col [i].shared2.order == COLAMD_EMPTY) + { parent = i ; /* once found, find its principal parent */ do { - parent = Col [parent].shared1.parent ; + parent = Col [parent].shared1.parent ; } while (!COL_IS_DEAD_PRINCIPAL (parent)) ; /* now, order all un-ordered non-principal columns along path */ @@ -1488,32 +1491,32 @@ static inline void order_children do { - COLAMD_ASSERT (Col [c].shared2.order == COLAMD_EMPTY) ; + COLAMD_ASSERT (Col [c].shared2.order == COLAMD_EMPTY) ; - /* order this column */ - Col [c].shared2.order = order++ ; - /* collaps tree */ - Col [c].shared1.parent = parent ; + /* order this column */ + Col [c].shared2.order = order++ ; + /* collaps tree */ + Col [c].shared1.parent = parent ; - /* get immediate parent of this column */ - c = Col [c].shared1.parent ; + /* get immediate parent of this column */ + c = Col [c].shared1.parent ; - /* continue until we hit an ordered column. There are */ - /* guarranteed not to be anymore unordered columns */ - /* above an ordered column */ + /* continue until we hit an ordered column. There are */ + /* guarranteed not to be anymore unordered columns */ + /* above an ordered column */ } while (Col [c].shared2.order == COLAMD_EMPTY) ; /* re-order the super_col parent to largest order for this group */ Col [parent].shared2.order = order ; - } } + } - /* === Generate the permutation ========================================= */ + /* === Generate the permutation ========================================= */ - for (c = 0 ; c < n_col ; c++) - { - p [Col [c].shared2.order] = c ; - } + for (c = 0 ; c < n_col ; c++) + { + p [Col [c].shared2.order] = c ; + } } @@ -1522,94 +1525,94 @@ static inline void order_children /* ========================================================================== */ /* - Detects supercolumns by finding matches between columns in the hash buckets. - Check amongst columns in the set A [row_start ... row_start + row_length-1]. - The columns under consideration are currently *not* in the degree lists, - and have already been placed in the hash buckets. + Detects supercolumns by finding matches between columns in the hash buckets. + Check amongst columns in the set A [row_start ... row_start + row_length-1]. + The columns under consideration are currently *not* in the degree lists, + and have already been placed in the hash buckets. - The hash bucket for columns whose hash function is equal to h is stored - as follows: + The hash bucket for columns whose hash function is equal to h is stored + as follows: if head [h] is >= 0, then head [h] contains a degree list, so: - head [h] is the first column in degree bucket h. - Col [head [h]].headhash gives the first column in hash bucket h. + head [h] is the first column in degree bucket h. + Col [head [h]].headhash gives the first column in hash bucket h. otherwise, the degree list is empty, and: - -(head [h] + 2) is the first column in hash bucket h. + -(head [h] + 2) is the first column in hash bucket h. - For a column c in a hash bucket, Col [c].shared3.prev is NOT a "previous - column" pointer. Col [c].shared3.hash is used instead as the hash number - for that column. The value of Col [c].shared4.hash_next is the next column - in the same hash bucket. + For a column c in a hash bucket, Col [c].shared3.prev is NOT a "previous + column" pointer. Col [c].shared3.hash is used instead as the hash number + for that column. The value of Col [c].shared4.hash_next is the next column + in the same hash bucket. - Assuming no, or "few" hash collisions, the time taken by this routine is - linear in the sum of the sizes (lengths) of each column whose score has - just been computed in the approximate degree computation. - Not user-callable. + Assuming no, or "few" hash collisions, the time taken by this routine is + linear in the sum of the sizes (lengths) of each column whose score has + just been computed in the approximate degree computation. + Not user-callable. */ - +template static void detect_super_cols ( - /* === Parameters ======================================================= */ - - colamd_col Col [], /* of size n_col+1 */ - int A [], /* row indices of A */ - int head [], /* head of degree lists and hash buckets */ - int row_start, /* pointer to set of columns to check */ - int row_length /* number of columns to check */ + /* === Parameters ======================================================= */ + + colamd_col Col [], /* of size n_col+1 */ + Index A [], /* row indices of A */ + Index head [], /* head of degree lists and hash buckets */ + Index row_start, /* pointer to set of columns to check */ + Index row_length /* number of columns to check */ ) { - /* === Local variables ================================================== */ - - int hash ; /* hash value for a column */ - int *rp ; /* pointer to a row */ - int c ; /* a column index */ - int super_c ; /* column index of the column to absorb into */ - int *cp1 ; /* column pointer for column super_c */ - int *cp2 ; /* column pointer for column c */ - int length ; /* length of column super_c */ - int prev_c ; /* column preceding c in hash bucket */ - int i ; /* loop counter */ - int *rp_end ; /* pointer to the end of the row */ - int col ; /* a column index in the row to check */ - int head_column ; /* first column in hash bucket or degree list */ - int first_col ; /* first column in hash bucket */ - - /* === Consider each column in the row ================================== */ - - rp = &A [row_start] ; - rp_end = rp + row_length ; - while (rp < rp_end) - { - col = *rp++ ; - if (COL_IS_DEAD (col)) + /* === Local variables ================================================== */ + + Index hash ; /* hash value for a column */ + Index *rp ; /* pointer to a row */ + Index c ; /* a column index */ + Index super_c ; /* column index of the column to absorb into */ + Index *cp1 ; /* column pointer for column super_c */ + Index *cp2 ; /* column pointer for column c */ + Index length ; /* length of column super_c */ + Index prev_c ; /* column preceding c in hash bucket */ + Index i ; /* loop counter */ + Index *rp_end ; /* pointer to the end of the row */ + Index col ; /* a column index in the row to check */ + Index head_column ; /* first column in hash bucket or degree list */ + Index first_col ; /* first column in hash bucket */ + + /* === Consider each column in the row ================================== */ + + rp = &A [row_start] ; + rp_end = rp + row_length ; + while (rp < rp_end) { + col = *rp++ ; + if (COL_IS_DEAD (col)) + { continue ; - } + } - /* get hash number for this column */ - hash = Col [col].shared3.hash ; - COLAMD_ASSERT (hash <= n_col) ; + /* get hash number for this column */ + hash = Col [col].shared3.hash ; + COLAMD_ASSERT (hash <= n_col) ; - /* === Get the first column in this hash bucket ===================== */ + /* === Get the first column in this hash bucket ===================== */ - head_column = head [hash] ; - if (head_column > COLAMD_EMPTY) - { + head_column = head [hash] ; + if (head_column > COLAMD_EMPTY) + { first_col = Col [head_column].shared3.headhash ; - } - else - { + } + else + { first_col = - (head_column + 2) ; - } + } - /* === Consider each column in the hash bucket ====================== */ + /* === Consider each column in the hash bucket ====================== */ - for (super_c = first_col ; super_c != COLAMD_EMPTY ; - super_c = Col [super_c].shared4.hash_next) - { + for (super_c = first_col ; super_c != COLAMD_EMPTY ; + super_c = Col [super_c].shared4.hash_next) + { COLAMD_ASSERT (COL_IS_ALIVE (super_c)) ; COLAMD_ASSERT (Col [super_c].shared3.hash == hash) ; length = Col [super_c].length ; @@ -1620,71 +1623,71 @@ static void detect_super_cols /* === Compare super_c with all columns after it ================ */ for (c = Col [super_c].shared4.hash_next ; - c != COLAMD_EMPTY ; c = Col [c].shared4.hash_next) + c != COLAMD_EMPTY ; c = Col [c].shared4.hash_next) { - COLAMD_ASSERT (c != super_c) ; - COLAMD_ASSERT (COL_IS_ALIVE (c)) ; - COLAMD_ASSERT (Col [c].shared3.hash == hash) ; - - /* not identical if lengths or scores are different */ - if (Col [c].length != length || - Col [c].shared2.score != Col [super_c].shared2.score) - { - prev_c = c ; - continue ; + COLAMD_ASSERT (c != super_c) ; + COLAMD_ASSERT (COL_IS_ALIVE (c)) ; + COLAMD_ASSERT (Col [c].shared3.hash == hash) ; + + /* not identical if lengths or scores are different */ + if (Col [c].length != length || + Col [c].shared2.score != Col [super_c].shared2.score) + { + prev_c = c ; + continue ; + } + + /* compare the two columns */ + cp1 = &A [Col [super_c].start] ; + cp2 = &A [Col [c].start] ; + + for (i = 0 ; i < length ; i++) + { + /* the columns are "clean" (no dead rows) */ + COLAMD_ASSERT (ROW_IS_ALIVE (*cp1)) ; + COLAMD_ASSERT (ROW_IS_ALIVE (*cp2)) ; + /* row indices will same order for both supercols, */ + /* no gather scatter nessasary */ + if (*cp1++ != *cp2++) + { + break ; + } + } + + /* the two columns are different if the for-loop "broke" */ + if (i != length) + { + prev_c = c ; + continue ; + } + + /* === Got it! two columns are identical =================== */ + + COLAMD_ASSERT (Col [c].shared2.score == Col [super_c].shared2.score) ; + + Col [super_c].shared1.thickness += Col [c].shared1.thickness ; + Col [c].shared1.parent = super_c ; + KILL_NON_PRINCIPAL_COL (c) ; + /* order c later, in order_children() */ + Col [c].shared2.order = COLAMD_EMPTY ; + /* remove c from hash bucket */ + Col [prev_c].shared4.hash_next = Col [c].shared4.hash_next ; + } } - /* compare the two columns */ - cp1 = &A [Col [super_c].start] ; - cp2 = &A [Col [c].start] ; + /* === Empty this hash bucket ======================================= */ - for (i = 0 ; i < length ; i++) - { - /* the columns are "clean" (no dead rows) */ - COLAMD_ASSERT (ROW_IS_ALIVE (*cp1)) ; - COLAMD_ASSERT (ROW_IS_ALIVE (*cp2)) ; - /* row indices will same order for both supercols, */ - /* no gather scatter nessasary */ - if (*cp1++ != *cp2++) - { - break ; - } - } - - /* the two columns are different if the for-loop "broke" */ - if (i != length) + if (head_column > COLAMD_EMPTY) { - prev_c = c ; - continue ; - } - - /* === Got it! two columns are identical =================== */ - - COLAMD_ASSERT (Col [c].shared2.score == Col [super_c].shared2.score) ; - - Col [super_c].shared1.thickness += Col [c].shared1.thickness ; - Col [c].shared1.parent = super_c ; - KILL_NON_PRINCIPAL_COL (c) ; - /* order c later, in order_children() */ - Col [c].shared2.order = COLAMD_EMPTY ; - /* remove c from hash bucket */ - Col [prev_c].shared4.hash_next = Col [c].shared4.hash_next ; - } - } - - /* === Empty this hash bucket ======================================= */ - - if (head_column > COLAMD_EMPTY) - { /* corresponding degree list "hash" is not empty */ Col [head_column].shared3.headhash = COLAMD_EMPTY ; - } - else - { + } + else + { /* corresponding degree list "hash" is empty */ head [hash] = COLAMD_EMPTY ; - } } + } } @@ -1693,93 +1696,93 @@ static void detect_super_cols /* ========================================================================== */ /* - Defragments and compacts columns and rows in the workspace A. Used when - all avaliable memory has been used while performing row merging. Returns - the index of the first free position in A, after garbage collection. The - time taken by this routine is linear is the size of the array A, which is - itself linear in the number of nonzeros in the input matrix. - Not user-callable. + Defragments and compacts columns and rows in the workspace A. Used when + all avaliable memory has been used while performing row merging. Returns + the index of the first free position in A, after garbage collection. The + time taken by this routine is linear is the size of the array A, which is + itself linear in the number of nonzeros in the input matrix. + Not user-callable. */ - -static int garbage_collection /* returns the new value of pfree */ -( +template +static Index garbage_collection /* returns the new value of pfree */ + ( /* === Parameters ======================================================= */ - - int n_row, /* number of rows */ - int n_col, /* number of columns */ - Colamd_Row Row [], /* row info */ - colamd_col Col [], /* column info */ - int A [], /* A [0 ... Alen-1] holds the matrix */ - int *pfree /* &A [0] ... pfree is in use */ -) + + Index n_row, /* number of rows */ + Index n_col, /* number of columns */ + Colamd_Row Row [], /* row info */ + colamd_col Col [], /* column info */ + Index A [], /* A [0 ... Alen-1] holds the matrix */ + Index *pfree /* &A [0] ... pfree is in use */ + ) { - /* === Local variables ================================================== */ + /* === Local variables ================================================== */ - int *psrc ; /* source pointer */ - int *pdest ; /* destination pointer */ - int j ; /* counter */ - int r ; /* a row index */ - int c ; /* a column index */ - int length ; /* length of a row or column */ + Index *psrc ; /* source pointer */ + Index *pdest ; /* destination pointer */ + Index j ; /* counter */ + Index r ; /* a row index */ + Index c ; /* a column index */ + Index length ; /* length of a row or column */ - /* === Defragment the columns =========================================== */ + /* === Defragment the columns =========================================== */ - pdest = &A[0] ; - for (c = 0 ; c < n_col ; c++) - { - if (COL_IS_ALIVE (c)) + pdest = &A[0] ; + for (c = 0 ; c < n_col ; c++) { + if (COL_IS_ALIVE (c)) + { psrc = &A [Col [c].start] ; /* move and compact the column */ COLAMD_ASSERT (pdest <= psrc) ; - Col [c].start = (int) (pdest - &A [0]) ; + Col [c].start = (Index) (pdest - &A [0]) ; length = Col [c].length ; for (j = 0 ; j < length ; j++) { - r = *psrc++ ; - if (ROW_IS_ALIVE (r)) - { - *pdest++ = r ; - } + r = *psrc++ ; + if (ROW_IS_ALIVE (r)) + { + *pdest++ = r ; + } } - Col [c].length = (int) (pdest - &A [Col [c].start]) ; - } + Col [c].length = (Index) (pdest - &A [Col [c].start]) ; } + } - /* === Prepare to defragment the rows =================================== */ + /* === Prepare to defragment the rows =================================== */ - for (r = 0 ; r < n_row ; r++) - { - if (ROW_IS_ALIVE (r)) + for (r = 0 ; r < n_row ; r++) { + if (ROW_IS_ALIVE (r)) + { if (Row [r].length == 0) { - /* this row is of zero length. cannot compact it, so kill it */ - COLAMD_DEBUG3 (("Defrag row kill\n")) ; - KILL_ROW (r) ; + /* this row is of zero length. cannot compact it, so kill it */ + COLAMD_DEBUG3 (("Defrag row kill\n")) ; + KILL_ROW (r) ; } else { - /* save first column index in Row [r].shared2.first_column */ - psrc = &A [Row [r].start] ; - Row [r].shared2.first_column = *psrc ; - COLAMD_ASSERT (ROW_IS_ALIVE (r)) ; - /* flag the start of the row with the one's complement of row */ - *psrc = ONES_COMPLEMENT (r) ; + /* save first column index in Row [r].shared2.first_column */ + psrc = &A [Row [r].start] ; + Row [r].shared2.first_column = *psrc ; + COLAMD_ASSERT (ROW_IS_ALIVE (r)) ; + /* flag the start of the row with the one's complement of row */ + *psrc = ONES_COMPLEMENT (r) ; } - } } + } - /* === Defragment the rows ============================================== */ + /* === Defragment the rows ============================================== */ - psrc = pdest ; - while (psrc < pfree) - { - /* find a negative number ... the start of a row */ - if (*psrc++ < 0) + psrc = pdest ; + while (psrc < pfree) { + /* find a negative number ... the start of a row */ + if (*psrc++ < 0) + { psrc-- ; /* get the row index */ r = ONES_COMPLEMENT (*psrc) ; @@ -1790,26 +1793,26 @@ static int garbage_collection /* returns the new value of pfree */ /* move and compact the row */ COLAMD_ASSERT (pdest <= psrc) ; - Row [r].start = (int) (pdest - &A [0]) ; + Row [r].start = (Index) (pdest - &A [0]) ; length = Row [r].length ; for (j = 0 ; j < length ; j++) { - c = *psrc++ ; - if (COL_IS_ALIVE (c)) - { - *pdest++ = c ; - } + c = *psrc++ ; + if (COL_IS_ALIVE (c)) + { + *pdest++ = c ; + } } - Row [r].length = (int) (pdest - &A [Row [r].start]) ; + Row [r].length = (Index) (pdest - &A [Row [r].start]) ; - } } - /* ensure we found all the rows */ - COLAMD_ASSERT (debug_rows == 0) ; + } + /* ensure we found all the rows */ + COLAMD_ASSERT (debug_rows == 0) ; - /* === Return the new value of pfree ==================================== */ + /* === Return the new value of pfree ==================================== */ - return ((int) (pdest - &A [0])) ; + return ((Index) (pdest - &A [0])) ; } @@ -1818,30 +1821,30 @@ static int garbage_collection /* returns the new value of pfree */ /* ========================================================================== */ /* - Clears the Row [].shared2.mark array, and returns the new tag_mark. - Return value is the new tag_mark. Not user-callable. + Clears the Row [].shared2.mark array, and returns the new tag_mark. + Return value is the new tag_mark. Not user-callable. */ - -static inline int clear_mark /* return the new value for tag_mark */ -( - /* === Parameters ======================================================= */ - - int n_row, /* number of rows in A */ - Colamd_Row Row [] /* Row [0 ... n_row-1].shared2.mark is set to zero */ -) +template +static inline Index clear_mark /* return the new value for tag_mark */ + ( + /* === Parameters ======================================================= */ + + Index n_row, /* number of rows in A */ + Colamd_Row Row [] /* Row [0 ... n_row-1].shared2.mark is set to zero */ + ) { - /* === Local variables ================================================== */ + /* === Local variables ================================================== */ - int r ; + Index r ; - for (r = 0 ; r < n_row ; r++) - { - if (ROW_IS_ALIVE (r)) + for (r = 0 ; r < n_row ; r++) { + if (ROW_IS_ALIVE (r)) + { Row [r].shared2.mark = 0 ; - } } - return (1) ; + } + return (1) ; } diff --git a/Eigen/src/OrderingMethods/Ordering.h b/Eigen/src/OrderingMethods/Ordering.h index fb1da1fe2..b4da6531a 100644 --- a/Eigen/src/OrderingMethods/Ordering.h +++ b/Eigen/src/OrderingMethods/Ordering.h @@ -122,26 +122,26 @@ class COLAMDOrdering template void operator() (const MatrixType& mat, PermutationType& perm) { - int m = mat.rows(); - int n = mat.cols(); - int nnz = mat.nonZeros(); + Index m = mat.rows(); + Index n = mat.cols(); + Index nnz = mat.nonZeros(); // Get the recommended value of Alen to be used by colamd - int Alen = internal::colamd_recommended(nnz, m, n); + Index Alen = internal::colamd_recommended(nnz, m, n); // Set the default parameters double knobs [COLAMD_KNOBS]; - int stats [COLAMD_STATS]; + Index stats [COLAMD_STATS]; internal::colamd_set_defaults(knobs); - int info; + Index info; IndexVector p(n+1), A(Alen); - for(int i=0; i <= n; i++) p(i) = mat.outerIndexPtr()[i]; - for(int i=0; i < nnz; i++) A(i) = mat.innerIndexPtr()[i]; + for(Index i=0; i <= n; i++) p(i) = mat.outerIndexPtr()[i]; + for(Index i=0; i < nnz; i++) A(i) = mat.innerIndexPtr()[i]; // Call Colamd routine to compute the ordering info = internal::colamd(m, n, Alen, A.data(), p.data(), knobs, stats); eigen_assert( info && "COLAMD failed " ); perm.resize(n); - for (int i = 0; i < n; i++) perm.indices()(p(i)) = i; + for (Index i = 0; i < n; i++) perm.indices()(p(i)) = i; } }; -- cgit v1.2.3