599 #ifdef MATLAB_MEX_FILE
604 #if !defined (NPRINT) || !defined (NDEBUG)
609 #define NULL ((void *) 0)
618 #define Int SuiteSparse_long
619 #define ID SuiteSparse_long_id
620 #define Int_MAX SuiteSparse_long_max
622 #define CCOLAMD_recommended ccolamd_l_recommended
623 #define CCOLAMD_set_defaults ccolamd_l_set_defaults
624 #define CCOLAMD_2 ccolamd2_l
625 #define CCOLAMD_MAIN ccolamd_l
626 #define CCOLAMD_apply_order ccolamd_l_apply_order
627 #define CCOLAMD_postorder ccolamd_l_postorder
628 #define CCOLAMD_post_tree ccolamd_l_post_tree
629 #define CCOLAMD_fsize ccolamd_l_fsize
630 #define CSYMAMD_MAIN csymamd_l
631 #define CCOLAMD_report ccolamd_l_report
632 #define CSYMAMD_report csymamd_l_report
638 #define Int_MAX INT_MAX
640 #define CCOLAMD_recommended ccolamd_recommended
641 #define CCOLAMD_set_defaults ccolamd_set_defaults
642 #define CCOLAMD_2 ccolamd2
643 #define CCOLAMD_MAIN ccolamd
644 #define CCOLAMD_apply_order ccolamd_apply_order
645 #define CCOLAMD_postorder ccolamd_postorder
646 #define CCOLAMD_post_tree ccolamd_post_tree
647 #define CCOLAMD_fsize ccolamd_fsize
648 #define CSYMAMD_MAIN csymamd
649 #define CCOLAMD_report ccolamd_report
650 #define CSYMAMD_report csymamd_report
727 #define MAX(a,b) (((a) > (b)) ? (a) : (b))
728 #define MIN(a,b) (((a) < (b)) ? (a) : (b))
733 #define PRIVATE static
735 #define DENSE_DEGREE(alpha,n) \
736 ((Int) MAX (16.0, (alpha) * sqrt ((double) (n))))
738 #define CMEMBER(c) ((cmember == (Int *) NULL) ? (0) : (cmember [c]))
741 #define SCALAR_IS_NAN(x) ((x) != (x))
744 #define INT_OVERFLOW(x) ((!((x) * (1.0+1e-8) <= (double) Int_MAX)) \
745 || SCALAR_IS_NAN (x))
747 #define ONES_COMPLEMENT(r) (-(r)-1)
758 #define DEAD_PRINCIPAL (-1)
759 #define DEAD_NON_PRINCIPAL (-2)
762 #define ROW_IS_DEAD(r) ROW_IS_MARKED_DEAD (Row[r].shared2.mark)
763 #define ROW_IS_MARKED_DEAD(row_mark) (row_mark < ALIVE)
764 #define ROW_IS_ALIVE(r) (Row [r].shared2.mark >= ALIVE)
765 #define COL_IS_DEAD(c) (Col [c].start < ALIVE)
766 #define COL_IS_ALIVE(c) (Col [c].start >= ALIVE)
767 #define COL_IS_DEAD_PRINCIPAL(c) (Col [c].start == DEAD_PRINCIPAL)
768 #define KILL_ROW(r) { Row [r].shared2.mark = DEAD ; }
769 #define KILL_PRINCIPAL_COL(c) { Col [c].start = DEAD_PRINCIPAL ; }
770 #define KILL_NON_PRINCIPAL_COL(c) { Col [c].start = DEAD_NON_PRINCIPAL ; }
777 #if defined (MATLAB_MEX_FILE) || defined (MATHWORKS)
779 #define INDEX(i) ((i)+1)
798 #define DEBUG0(params) { SUITESPARSE_PRINTF (params) ; }
799 #define DEBUG1(params) { if (ccolamd_debug >= 1) SUITESPARSE_PRINTF (params) ; }
800 #define DEBUG2(params) { if (ccolamd_debug >= 2) SUITESPARSE_PRINTF (params) ; }
801 #define DEBUG3(params) { if (ccolamd_debug >= 3) SUITESPARSE_PRINTF (params) ; }
802 #define DEBUG4(params) { if (ccolamd_debug >= 4) SUITESPARSE_PRINTF (params) ; }
804 #ifdef MATLAB_MEX_FILE
805 #define ASSERT(expression) (mxAssert ((expression), ""))
807 #define ASSERT(expression) (assert (expression))
866 #define DEBUG0(params) ;
867 #define DEBUG1(params) ;
868 #define DEBUG2(params) ;
869 #define DEBUG3(params) ;
870 #define DEBUG4(params) ;
872 #define ASSERT(expression)
909 Int *p_nnewlyempty_row,
912 Int *p_nnewlyempty_col
935 Int Front_npivcol [ ],
938 Int Front_parent [ ],
1018 (*ok) = (*ok) && ((
a +
b) >=
MAX (
a,
b)) ;
1019 return ((*ok) ? (
a +
b) : 0) ;
1023 static size_t t_mult (
size_t a,
size_t k,
int *ok)
1026 for (
i = 0 ;
i < k ;
i++)
1034 #define CCOLAMD_C(n_col,ok) \
1035 ((t_mult (t_add (n_col, 1, ok), sizeof (CColamd_Col), ok) / sizeof (Int)))
1037 #define CCOLAMD_R(n_row,ok) \
1038 ((t_mult (t_add (n_row, 1, ok), sizeof (CColamd_Row), ok) / sizeof (Int)))
1074 c =
t_add (n_col, 1, ok) ;
1080 return (ok ?
s : 0) ;
1094 if (nnz < 0 || n_row < 0 || n_col < 0)
1101 return (ok ?
s : 0) ;
1185 ccolamd_get_debug (
"csymamd") ;
1188 both = (stype == 0) ;
1189 upper = (stype > 0) ;
1190 lower = (stype < 0) ;
1196 DEBUG1 ((
"csymamd: stats not present\n")) ;
1210 DEBUG1 ((
"csymamd: A not present\n")) ;
1217 DEBUG1 ((
"csymamd: p not present\n")) ;
1225 DEBUG1 ((
"csymamd: n negative "ID" \n",
n)) ;
1234 DEBUG1 ((
"csymamd: number of entries negative "ID" \n", nnz)) ;
1242 DEBUG1 ((
"csymamd: p[0] not zero "ID"\n",
p [0])) ;
1251 knobs = default_knobs ;
1256 count = (
Int *) ((*allocate) (
n+1,
sizeof (
Int))) ;
1260 DEBUG1 ((
"csymamd: allocate count (size "ID") failed\n",
n+1)) ;
1264 mark = (
Int *) ((*allocate) (
n+1,
sizeof (
Int))) ;
1268 (*release) ((
void *) count) ;
1269 DEBUG1 ((
"csymamd: allocate mark (size "ID") failed\n",
n+1)) ;
1277 for (
i = 0 ;
i <
n ;
i++)
1282 for (
j = 0 ;
j <
n ;
j++)
1286 length =
p [
j+1] -
p [
j] ;
1293 (*release) ((
void *) count) ;
1294 (*release) ((
void *) mark) ;
1295 DEBUG1 ((
"csymamd: col "ID" negative length "ID"\n",
j, length)) ;
1299 for (pp =
p [
j] ; pp <
p [
j+1] ; pp++)
1302 if (i < 0 || i >=
n)
1309 (*release) ((
void *) count) ;
1310 (*release) ((
void *) mark) ;
1311 DEBUG1 ((
"csymamd: row "ID" col "ID" out of bounds\n",
i,
j)) ;
1315 if (
i <= last_row || mark [
i] ==
j)
1323 DEBUG1 ((
"csymamd: row "ID" col "ID" unsorted/dupl.\n",
i,
j)) ;
1328 if ((both &&
i !=
j) || (
lower &&
i >
j) || (upper &&
i <
j))
1347 for (
j = 1 ;
j <=
n ;
j++)
1351 for (
j = 0 ;
j <
n ;
j++)
1361 M = (
Int *) ((*allocate) (Mlen,
sizeof (
Int))) ;
1362 DEBUG1 ((
"csymamd: M is "ID"-by-"ID" with "ID" entries, Mlen = %g\n",
1363 n_row,
n, mnz, (
double) Mlen)) ;
1368 (*release) ((
void *) count) ;
1369 (*release) ((
void *) mark) ;
1370 DEBUG1 ((
"csymamd: allocate M (size %g) failed\n", (
double) Mlen)) ;
1379 for (
j = 0 ;
j <
n ;
j++)
1382 for (pp =
p [
j] ; pp <
p [
j+1] ; pp++)
1386 if ((both &&
i !=
j) || (
lower &&
i >
j) || (upper &&
i <
j))
1389 M [count [
i]++] = k ;
1390 M [count [
j]++] = k ;
1399 DEBUG1 ((
"csymamd: Duplicates in A.\n")) ;
1400 for (
i = 0 ;
i <
n ;
i++)
1404 for (
j = 0 ;
j <
n ;
j++)
1407 for (pp =
p [
j] ; pp <
p [
j+1] ; pp++)
1413 if ((both &&
i !=
j) || (
lower &&
i >
j) || (upper &&
i<
j))
1416 M [count [
i]++] = k ;
1417 M [count [
j]++] = k ;
1427 (*release) ((
void *) mark) ;
1428 (*release) ((
void *) count) ;
1435 cknobs [
i] = knobs [
i] ;
1458 (*release) ((
void *)
M) ;
1459 DEBUG1 ((
"csymamd: done.\n")) ;
1518 Int Front_npivcol [ ],
1519 Int Front_nrows [ ],
1520 Int Front_ncols [ ],
1521 Int Front_parent [ ],
1554 Int ndense_row, nempty_row, parent, ndense_col,
1555 nempty_col, k,
col, nfr, *Front_child, *Front_sibling, *Front_stack,
1556 *Front_order, *Front_size ;
1557 Int nnewlyempty_col, nnewlyempty_row ;
1568 ccolamd_get_debug (
"ccolamd") ;
1575 DEBUG1 ((
"ccolamd: stats not present\n")) ;
1589 DEBUG1 ((
"ccolamd: A not present\n")) ;
1596 DEBUG1 ((
"ccolamd: p not present\n")) ;
1604 DEBUG1 ((
"ccolamd: nrow negative "ID"\n", n_row)) ;
1612 DEBUG1 ((
"ccolamd: ncol negative "ID"\n", n_col)) ;
1621 DEBUG1 ((
"ccolamd: number of entries negative "ID"\n", nnz)) ;
1629 DEBUG1 ((
"ccolamd: p[0] not zero "ID"\n",
p [0])) ;
1638 knobs = default_knobs ;
1660 if (!ok || need > (
size_t) Alen || need >
Int_MAX)
1666 DEBUG1 ((
"ccolamd: Need Alen >= "ID", given "ID"\n", need, Alen)) ;
1671 Alen -= Col_size + Row_size + (3*n_col + 1) + 5*(n_col+1) + n_row ;
1680 if (!Front_npivcol || !Front_nrows || !Front_ncols || !Front_parent ||
1681 !Front_cols || !Front_cols || !InFront)
1683 Front_npivcol = &
A [ap] ; ap += (n_col + 1) ;
1684 Front_nrows = &
A [ap] ; ap += (n_col + 1) ;
1685 Front_ncols = &
A [ap] ; ap += (n_col + 1) ;
1686 Front_parent = &
A [ap] ; ap += (n_col + 1) ;
1687 Front_cols = &
A [ap] ; ap += (n_col + 1) ;
1688 InFront = &
A [ap] ; ap += (n_row) ;
1693 ap += 5*(n_col+1) + n_row ;
1699 cset_start = &
A [ap] ;
1703 dead_cols = &
A [ap] ;
1712 temp_cstart = (
Int *) Col ;
1713 csize = temp_cstart + (n_col+1) ;
1715 ASSERT (Col_size >= 2*n_col+1) ;
1722 for (
i = 0 ;
i < n_col ;
i++)
1734 else if (cmember == (
Int *)
NULL)
1739 DEBUG1 ((
"no cmember present\n")) ;
1744 for (
i = 0 ;
i < n_col ;
i++)
1746 if (cmember [
i] < 0 || cmember [
i] > n_col)
1749 DEBUG1 ((
"ccolamd: malformed cmember \n")) ;
1752 n_cset =
MAX (n_cset, cmember [
i]) ;
1753 csize [cmember [
i]]++ ;
1759 ASSERT ((n_cset >= 0) && (n_cset <= n_col)) ;
1761 cset_start [0] = temp_cstart [0] = 0 ;
1762 for (
i = 1 ;
i <= n_cset ;
i++)
1764 cset_start [
i] = cset_start [
i-1] + csize [
i-1] ;
1765 DEBUG4 ((
" cset_start ["ID"] = "ID" \n",
i , cset_start [
i])) ;
1766 temp_cstart [
i] = cset_start [
i] ;
1772 for (
i = n_col-1 ;
i >= 0 ;
i--)
1774 cset [temp_cstart [0]++] =
i ;
1779 for (
i = n_col-1 ;
i >= 0 ;
i--)
1781 cset [temp_cstart [cmember [
i]]++] =
i ;
1792 DEBUG1 ((
"ccolamd: Matrix invalid\n")) ;
1800 Front_npivcol [
col] = 0 ;
1801 Front_nrows [
col] = 0 ;
1802 Front_ncols [
col] = 0 ;
1810 &n_row2, &n_col2, &max_deg, cmember, n_cset, cset_start, dead_cols,
1811 &ndense_row, &nempty_row, &nnewlyempty_row,
1812 &ndense_col, &nempty_col, &nnewlyempty_col) ;
1814 ASSERT (n_row2 == n_row - nempty_row - nnewlyempty_row - ndense_row) ;
1815 ASSERT (n_col2 == n_col - nempty_col - nnewlyempty_col - ndense_col) ;
1816 DEBUG1 ((
"# dense rows "ID" cols "ID"\n", ndense_row, ndense_col)) ;
1824 max_deg, 2*nnz, cset, cset_start,
1828 cmember, Front_npivcol, Front_nrows, Front_ncols, Front_parent,
1829 Front_cols, &nfr, aggressive, InFront, order_for_lu) ;
1831 ASSERT (Alen >= 5*n_col) ;
1838 Front_sibling = Front_child + nfr ;
1839 Front_stack = Front_sibling + nfr ;
1840 Front_order = Front_stack + nfr ;
1841 Front_size = Front_order + nfr ;
1844 Front_parent, Front_npivcol) ;
1847 Front_order, Front_child, Front_sibling, Front_stack, Front_cols,
1860 for (
i = 0 ;
i < nfr ;
i++)
1862 parent = Front_parent [
i] ;
1863 if (parent !=
EMPTY)
1865 Front_parent [
i] = Front_order [parent] ;
1876 InFront [
row] = Front_order [
i] ;
1885 for (
i = 0 ;
i < n_col ;
i++)
1892 for (
i = 0 ;
i < nfr ;
i++)
1894 ASSERT (Front_npivcol [
i] > 0) ;
1899 k += dead_cols [set1] ;
1900 DEBUG3 ((
"Skip null/dense columns of set "ID"\n",set1)) ;
1908 DEBUG1 ((
"ccolamd output ordering: k "ID" col "ID"\n", k,
col)) ;
1913 ASSERT (k >= cset_start [cs] && k < cset_start [cs+1]) ;
1933 ASSERT (k >= cset_start [cs] && k < cset_start [cs+1]) ;
1934 DEBUG1 ((
"ccolamd output ordering: k "ID" col "ID
1935 " (dense or null col)\n", k,
col)) ;
1943 for (
i = 0 ;
i < n_cset ;
i++)
1957 ASSERT (ndense_col + nempty_col + nnewlyempty_col == n_col - n_col2) ;
1963 DEBUG1 ((
"ccolamd: done.\n")) ;
2044 if (Col [
col].length < 0)
2050 DEBUG1 ((
"ccolamd: col "ID" length "ID" < 0\n",
2051 col, Col [
col].length)) ;
2055 Col [
col].shared1.thickness = 1 ;
2056 Col [
col].shared2.score = 0 ;
2058 Col [
col].shared4.degree_next =
EMPTY ;
2060 Col [
col].lastcol =
col ;
2072 Row [
row].shared2.mark = -1 ;
2073 Row [
row].thickness = 1 ;
2079 DEBUG1 ((
"\nCcolamd input column "ID":\n",
col)) ;
2083 cp_end = &
A [
p [
col+1]] ;
2091 if (row < 0 || row >= n_row)
2120 Col [
col].length-- ;
2134 Row [0].start =
p [n_col] ;
2135 Row [0].shared1.p =
Row [0].start ;
2136 Row [0].shared2.mark = -1 ;
2141 Row [
row].shared2.mark = -1 ;
2152 cp_end = &
A [
p [
col+1]] ;
2170 cp_end = &
A [
p [
col+1]] ;
2173 A [(
Row [*cp++].shared1.p)++] =
col ;
2182 Row [
row].shared2.mark = 0 ;
2190 DEBUG1 ((
"ccolamd: reconstructing column form, matrix jumbled\n")) ;
2201 rp_end = rp +
Row [
row].length ;
2221 p [0] = Col [0].start ;
2226 Col [
col].start = Col [
col-1].start + Col [
col-1].length ;
2235 rp_end = rp +
Row [
row].length ;
2238 A [(
p [*rp++])++] =
row ;
2279 Int *p_nnewlyempty_row,
2282 Int *p_nnewlyempty_col
2297 Int dense_row_count ;
2298 Int dense_col_count ;
2303 Int nnewlyempty_row ;
2306 Int nnewlyempty_col ;
2319 dense_row_count = n_col-1 ;
2328 dense_col_count = n_row-1 ;
2336 DEBUG1 ((
"densecount: "ID" "ID"\n", dense_row_count, dense_col_count)) ;
2344 for (
s = 0 ;
s < n_cset ;
s++)
2346 head [
s] = cset_start [
s+1] ;
2351 nnewlyempty_col = 0 ;
2354 nnewlyempty_row = 0 ;
2360 for (
c = n_col-1 ;
c >= 0 ;
c--)
2373 DEBUG1 ((
"ccolamd: null columns killed: "ID"\n", n_col - n_col2)) ;
2378 for (
c = n_col-1 ;
c >= 0 ;
c--)
2386 if (deg > dense_col_count)
2395 cp_end = cp + Col [
c].length ;
2398 Row [*cp++].shared1.degree-- ;
2403 DEBUG1 ((
"Dense and null columns killed: "ID"\n", n_col - n_col2)) ;
2411 for (r = 0 ; r < n_row ; r++)
2413 deg =
Row [r].shared1.degree ;
2414 ASSERT (deg >= 0 && deg <= n_col) ;
2415 if (deg > dense_row_count)
2426 if (deg > dense_row_count || deg == 0)
2430 Row [r].thickness = 0 ;
2436 max_deg =
MAX (max_deg, deg) ;
2439 nnewlyempty_row = ne - nempty_row ;
2440 DEBUG1 ((
"ccolamd: Dense and null rows killed: "ID"\n", n_row - n_row2)) ;
2450 for (
c = n_col-1 ;
c >= 0 ;
c--)
2460 cp_end = cp + Col [
c].length ;
2473 score +=
Row [
row].shared1.degree - 1 ;
2475 score =
MIN (score, n_col) ;
2478 col_length = (
Int) (new_cp - &
A [Col [
c].start]) ;
2479 if (col_length == 0)
2483 DEBUG1 ((
"Newly null killed: "ID"\n",
c)) ;
2494 ASSERT (score <= n_col) ;
2495 Col [
c].length = col_length ;
2496 Col [
c].shared2.score = score ;
2499 DEBUG1 ((
"ccolamd: Dense, null, and newly-null columns killed: "ID"\n",
2512 for (
c = 0 ;
c <= n_col ;
c++)
2518 debug_structures (n_row, n_col,
Row, Col,
A, cmember, cset_start) ;
2523 *p_n_col2 = n_col2 ;
2524 *p_n_row2 = n_row2 ;
2525 *p_max_deg = max_deg ;
2526 *p_ndense_row = ndense_row ;
2527 *p_nempty_row = nempty_row ;
2528 *p_nnewlyempty_row = nnewlyempty_row ;
2529 *p_ndense_col = ndense_col ;
2530 *p_nempty_col = nempty_col ;
2531 *p_nnewlyempty_col = nnewlyempty_col ;
2567 Int Front_npivcol [ ],
2568 Int Front_nrows [ ],
2569 Int Front_ncols [ ],
2570 Int Front_parent [ ],
2587 Int pivot_row_start ;
2588 Int pivot_row_degree ;
2589 Int pivot_row_length ;
2590 Int pivot_col_score ;
2603 Int set_difference ;
2607 Int pivot_col_thickness ;
2619 Int debug_step = 0 ;
2620 Int cols_thickness = 0 ;
2624 Int pivot_row_thickness ;
2636 DEBUG1 ((
"ccolamd: Ordering, n_col2="ID"\n", n_col2)) ;
2645 for (k = 0 ; k < n_col ; )
2649 ASSERT (min_score >= 0) ;
2650 ASSERT (min_score <= n_col) ;
2654 for (debug_d = 0 ; debug_d < min_score ; debug_d++)
2662 while ((k+deadcol) == cset_start [current_set+1])
2665 DEBUG1 ((
"\n\n\n============ CSET: "ID"\n", current_set)) ;
2669 ASSERT ((current_set == n_cset) == (k == n_col)) ;
2686 colstart = cset_start [current_set] ;
2687 colend = cset_start [current_set+1] ;
2689 while (colstart < colend)
2691 col = cset [colstart++] ;
2697 if (Col [
col].shared2.order !=
EMPTY)
2707 score = Col [
col].shared2.score ;
2708 DEBUG1 ((
"Column "ID" is alive, score "ID"\n",
col, score)) ;
2710 ASSERT (min_score >= 0) ;
2711 ASSERT (min_score <= n_col) ;
2713 ASSERT (score <= n_col) ;
2717 next_col =
head [score] ;
2719 Col [
col].shared4.degree_next = next_col ;
2723 if (next_col !=
EMPTY)
2725 Col [next_col].shared3.prev =
col ;
2730 min_score =
MIN (min_score, score) ;
2734 DEBUG1 ((
"degree lists initialized \n")) ;
2735 debug_deg_lists (n_row, n_col,
Row, Col,
head, min_score,
2736 ((cset_start [current_set+1]-cset_start [current_set])-deadcol),
2742 if (debug_step % 100 == 0)
2744 DEBUG2 ((
"\n... Step k: "ID" out of n_col2: "ID"\n", k, n_col2)) ;
2748 DEBUG3 ((
"\n------Step k: "ID" out of n_col2: "ID"\n", k, n_col2)) ;
2751 DEBUG1 ((
"start of step k="ID": ", k)) ;
2752 debug_deg_lists (n_row, n_col,
Row, Col,
head,
2753 min_score, cset_start [current_set+1]-(k+deadcol), max_deg) ;
2754 debug_matrix (n_row, n_col,
Row, Col,
A) ;
2759 while (
head [min_score] ==
EMPTY && min_score < n_col)
2764 pivot_col =
head [min_score] ;
2766 ASSERT (pivot_col >= 0 && pivot_col <= n_col) ;
2767 next_col = Col [pivot_col].shared4.degree_next ;
2768 head [min_score] = next_col ;
2769 if (next_col !=
EMPTY)
2771 Col [next_col].shared3.prev =
EMPTY ;
2777 pivot_col_score = Col [pivot_col].shared2.score ;
2780 Col [pivot_col].shared2.order = k ;
2783 pivot_col_thickness = Col [pivot_col].shared1.thickness ;
2784 k += pivot_col_thickness ;
2785 ASSERT (pivot_col_thickness > 0) ;
2786 DEBUG3 ((
"Pivot col: "ID" thick "ID"\n", pivot_col,
2787 pivot_col_thickness)) ;
2791 needed_memory =
MIN (pivot_col_score, n_col - k) ;
2792 if (pfree + needed_memory >= Alen)
2797 ASSERT (pfree + needed_memory < Alen) ;
2802 debug_matrix (n_row, n_col,
Row, Col,
A) ;
2809 pivot_row_start = pfree ;
2812 pivot_row_degree = 0 ;
2813 pivot_row_thickness = 0 ;
2817 Col [pivot_col].shared1.thickness = -pivot_col_thickness ;
2820 cp = &
A [Col [pivot_col].start] ;
2821 cp_end = cp + Col [pivot_col].length ;
2832 pivot_row_thickness +=
Row [
row].thickness ;
2835 rp_end = rp +
Row [
row].length ;
2841 col_thickness = Col [
col].shared1.thickness ;
2845 Col [
col].shared1.thickness = -col_thickness ;
2849 pivot_row_degree += col_thickness ;
2850 DEBUG4 ((
"\t\t\tNew live col in pivrow: "ID"\n",
col)) ;
2855 DEBUG4 ((
"\t\t\tOld live col in pivrow: "ID"\n",
col)) ;
2866 Col [pivot_col].shared1.thickness = pivot_col_thickness ;
2867 max_deg =
MAX (max_deg, pivot_row_degree) ;
2871 debug_mark (n_row,
Row, tag_mark, max_mark) ;
2877 cp = &
A [Col [pivot_col].start] ;
2878 cp_end = cp + Col [pivot_col].length ;
2891 child =
Row [
row].front ;
2892 Front_parent [child] = nfr ;
2893 DEBUG1 ((
"Front "ID" => front "ID", normal\n", child, nfr));
2899 InFront [
row] = nfr ;
2905 Row [
row].thickness = 0 ;
2910 pivot_row_length = pfree - pivot_row_start ;
2911 if (pivot_row_length > 0)
2914 pivot_row =
A [Col [pivot_col].start] ;
2915 DEBUG3 ((
"Pivotal row is "ID"\n", pivot_row)) ;
2921 ASSERT (pivot_row_length == 0) ;
2923 ASSERT (Col [pivot_col].length > 0 || pivot_row_length == 0) ;
2946 DEBUG3 ((
"** Computing set differences phase. **\n")) ;
2950 DEBUG3 ((
"Pivot row: ")) ;
2952 rp = &
A [pivot_row_start] ;
2953 rp_end = rp + pivot_row_length ;
2961 col_thickness = -Col [
col].shared1.thickness ;
2962 ASSERT (col_thickness > 0) ;
2963 Col [
col].shared1.thickness = col_thickness ;
2971 cols_thickness += col_thickness ;
2973 cur_score = Col [
col].shared2.score ;
2974 prev_col = Col [
col].shared3.prev ;
2975 next_col = Col [
col].shared4.degree_next ;
2976 DEBUG3 ((
" cur_score "ID" prev_col "ID" next_col "ID"\n",
2977 cur_score, prev_col, next_col)) ;
2978 ASSERT (cur_score >= 0) ;
2979 ASSERT (cur_score <= n_col) ;
2981 if (prev_col ==
EMPTY)
2983 head [cur_score] = next_col ;
2987 Col [prev_col].shared4.degree_next = next_col ;
2989 if (next_col !=
EMPTY)
2991 Col [next_col].shared3.prev = prev_col ;
2997 cp = &
A [Col [
col].start] ;
2998 cp_end = cp + Col [
col].length ;
3003 row_mark =
Row [
row].shared2.mark ;
3010 set_difference = row_mark - tag_mark ;
3012 if (set_difference < 0)
3015 set_difference =
Row [
row].shared1.degree ;
3018 set_difference -= col_thickness ;
3019 ASSERT (set_difference >= 0) ;
3021 if (set_difference == 0 && aggressive)
3023 DEBUG3 ((
"aggressive absorption. Row: "ID"\n",
row)) ;
3028 child =
Row [
row].front ;
3029 Front_parent [child] = nfr ;
3030 DEBUG1 ((
"Front "ID" => front "ID", aggressive\n",
3037 InFront [
row] = nfr ;
3038 DEBUG1 ((
"Row "ID" => front "ID", aggressive\n",
3045 pivot_row_thickness +=
Row [
row].thickness ;
3046 Row [
row].thickness = 0 ;
3051 Row [
row].shared2.mark = set_difference + tag_mark ;
3057 debug_deg_lists (n_row, n_col,
Row, Col,
head, min_score,
3058 cset_start [current_set+1]-(k+deadcol)-(cols_thickness),
3060 cols_thickness = 0 ;
3065 DEBUG3 ((
"** Adding set differences phase. **\n")) ;
3068 rp = &
A [pivot_row_start] ;
3069 rp_end = rp + pivot_row_length ;
3077 cp = &
A [Col [
col].start] ;
3080 cp_end = cp + Col [
col].length ;
3082 DEBUG4 ((
"Adding set diffs for Col: "ID".\n",
col)) ;
3089 row_mark =
Row [
row].shared2.mark ;
3096 DEBUG4 ((
" Row "ID", set diff "ID"\n",
row, row_mark-tag_mark));
3097 ASSERT (row_mark >= tag_mark) ;
3103 cur_score += row_mark - tag_mark ;
3105 cur_score =
MIN (cur_score, n_col) ;
3109 Col [
col].length = (
Int) (new_cp - &
A [Col [
col].start]) ;
3115 DEBUG4 ((
"further mass elimination. Col: "ID"\n",
col)) ;
3118 pivot_row_degree -= Col [
col].shared1.thickness ;
3119 ASSERT (pivot_row_degree >= 0) ;
3121 Col [
col].shared2.order = k ;
3123 k += Col [
col].shared1.thickness ;
3124 pivot_col_thickness += Col [
col].shared1.thickness ;
3128 dump_super (
col, Col, n_col) ;
3130 Col [Col [
col].lastcol].nextcol = Front_cols [nfr] ;
3131 Front_cols [nfr] =
col ;
3137 DEBUG4 ((
"Preparing supercol detection for Col: "ID".\n",
col));
3140 Col [
col].shared2.score = cur_score ;
3149 if (head_column >
EMPTY)
3153 first_col = Col [head_column].shared3.headhash ;
3154 Col [head_column].shared3.headhash =
col ;
3159 first_col = - (head_column + 2) ;
3162 Col [
col].shared4.hash_next = first_col ;
3174 DEBUG3 ((
"** Supercolumn detection phase. **\n")) ;
3180 Col,
A,
head, pivot_row_start, pivot_row_length, cmember) ;
3184 DEBUG1 ((
" KILLING column detect supercols "ID" \n", pivot_col)) ;
3190 dump_super (pivot_col, Col, n_col) ;
3192 Col [Col [pivot_col].lastcol].nextcol = Front_cols [nfr] ;
3193 Front_cols [nfr] = pivot_col ;
3197 tag_mark =
clear_mark (tag_mark+max_deg+1, max_mark, n_row,
Row) ;
3201 debug_mark (n_row,
Row, tag_mark, max_mark) ;
3206 DEBUG3 ((
"** Finalize scores phase. **\n")) ;
3209 rp = &
A [pivot_row_start] ;
3212 rp_end = rp + pivot_row_length ;
3223 A [Col [
col].start + (Col [
col].length++)] = pivot_row ;
3228 cur_score = Col [
col].shared2.score + pivot_row_degree ;
3233 max_score = n_col - k - Col [
col].shared1.thickness ;
3236 cur_score -= Col [
col].shared1.thickness ;
3239 cur_score =
MIN (cur_score, max_score) ;
3240 ASSERT (cur_score >= 0) ;
3243 Col [
col].shared2.score = cur_score ;
3249 ASSERT (min_score >= 0) ;
3250 ASSERT (min_score <= n_col) ;
3251 ASSERT (cur_score >= 0) ;
3252 ASSERT (cur_score <= n_col) ;
3254 next_col =
head [cur_score] ;
3255 Col [
col].shared4.degree_next = next_col ;
3257 if (next_col !=
EMPTY)
3259 Col [next_col].shared3.prev =
col ;
3263 min_score =
MIN (min_score, cur_score) ;
3267 Col [
col].shared4.degree_next =
EMPTY ;
3273 debug_deg_lists (n_row, n_col,
Row, Col,
head,
3274 min_score, cset_start [current_set+1]-(k+deadcol), max_deg) ;
3281 Front_npivcol [nfr] = pivot_col_thickness ;
3284 Front_nrows [nfr] = pivot_row_thickness ;
3287 Front_ncols [nfr] = pivot_col_thickness + pivot_row_degree ;
3289 Front_parent [nfr] =
EMPTY ;
3291 pivot_row_thickness -= pivot_col_thickness ;
3292 DEBUG1 ((
"Front "ID" Pivot_row_thickness after pivot cols elim: "ID"\n",
3293 nfr, pivot_row_thickness)) ;
3294 pivot_row_thickness =
MAX (0, pivot_row_thickness) ;
3298 if ((pivot_row_degree > 0 && pivot_row_thickness > 0 && (order_for_lu))
3299 || (pivot_row_degree > 0 && (!order_for_lu)))
3303 Row [pivot_row].start = pivot_row_start ;
3304 Row [pivot_row].length = (
Int) (new_rp - &
A[pivot_row_start]) ;
3305 Row [pivot_row].shared1.degree = pivot_row_degree ;
3306 Row [pivot_row].shared2.mark = 0 ;
3307 Row [pivot_row].thickness = pivot_row_thickness ;
3308 Row [pivot_row].front = nfr ;
3310 DEBUG1 ((
"Resurrect Pivot_row "ID" deg: "ID"\n",
3311 pivot_row, pivot_row_degree)) ;
3316 Front_npivcol [nfr], Front_nrows [nfr], Front_ncols [nfr])) ;
3325 ASSERT (debug_d <= pivot_col_thickness) ;
3327 ASSERT (debug_d == pivot_col_thickness) ;
3409 rp = &
A [row_start] ;
3410 rp_end = rp + row_length ;
3420 hash = Col [
col].shared3.hash ;
3426 if (head_column >
EMPTY)
3428 first_col = Col [head_column].shared3.headhash ;
3432 first_col = - (head_column + 2) ;
3437 for (super_c = first_col ; super_c !=
EMPTY ;
3438 super_c = Col [super_c].shared4.hash_next)
3441 ASSERT (Col [super_c].shared3.hash ==
hash) ;
3442 length = Col [super_c].length ;
3449 for (
c = Col [super_c].shared4.hash_next ;
3450 c !=
EMPTY ;
c = Col [
c].shared4.hash_next)
3458 if (Col [
c].length != length ||
3459 Col [
c].shared2.score != Col [super_c].shared2.score
3467 cp1 = &
A [Col [super_c].start] ;
3468 cp2 = &
A [Col [
c].start] ;
3470 for (
i = 0 ;
i < length ;
i++)
3477 if (*cp1++ != *cp2++)
3493 ASSERT (Col [
c].shared2.score == Col [super_c].shared2.score) ;
3495 Col [super_c].shared1.thickness += Col [
c].shared1.thickness ;
3496 Col [
c].shared1.parent = super_c ;
3499 Col [
c].shared2.order =
EMPTY ;
3501 Col [prev_c].shared4.hash_next = Col [
c].shared4.hash_next ;
3504 ASSERT (Col [super_c].lastcol >= 0) ;
3505 ASSERT (Col [super_c].lastcol < n_col) ;
3506 Col [Col [super_c].lastcol].nextcol =
c ;
3507 Col [super_c].lastcol = Col [
c].lastcol ;
3511 dump_super (super_c, Col, n_col) ;
3518 if (head_column >
EMPTY)
3521 Col [head_column].shared3.headhash =
EMPTY ;
3568 DEBUG2 ((
"Defrag..\n")) ;
3569 for (psrc = &
A[0] ; psrc < pfree ; psrc++)
ASSERT (*psrc >= 0) ;
3576 for (
c = 0 ;
c < n_col ;
c++)
3580 psrc = &
A [Col [
c].start] ;
3584 Col [
c].start = (
Int) (pdest - &
A [0]) ;
3585 length = Col [
c].length ;
3586 for (
j = 0 ;
j < length ;
j++)
3594 Col [
c].length = (
Int) (pdest - &
A [Col [
c].start]) ;
3600 for (r = 0 ; r < n_row ; r++)
3613 psrc = &
A [
Row [r].start] ;
3614 Row [r].shared2.first_column = *psrc ;
3627 while (psrc < pfree)
3635 ASSERT (r >= 0 && r < n_row) ;
3637 *psrc =
Row [r].shared2.first_column ;
3642 Row [r].start = (
Int) (pdest - &
A [0]) ;
3643 length =
Row [r].length ;
3644 for (
j = 0 ;
j < length ;
j++)
3652 Row [r].length = (
Int) (pdest - &
A [
Row [r].start]) ;
3660 ASSERT (debug_rows == 0) ;
3664 return ((
Int) (pdest - &
A [0])) ;
3692 if (tag_mark <= 0 || tag_mark >= max_mark)
3694 for (r = 0 ; r < n_row ; r++)
3698 Row [r].shared2.mark = 0 ;
3751 "Matrix has unsorted or duplicate row indices.\n")) ;
3754 "%s: duplicate or out-of-order row indices: "ID"\n",
3758 "%s: last seen duplicate or out-of-order row: "ID"\n",
3759 method,
INDEX (i2))) ;
3762 "%s: last seen in column: "ID"",
3772 "%s: number of dense or empty rows ignored: "ID"\n",
3776 "%s: number of dense or empty columns ignored: "ID"\n",
3780 "%s: number of garbage collections performed: "ID"\n",
3787 "Array A (row indices of matrix) not present.\n")) ;
3793 "Array p (column pointers for matrix) not present.\n")) ;
3809 "Invalid number of nonzero entries ("ID").\n",
i1)) ;
3815 "Invalid column pointer, p [0] = "ID", must be 0.\n",
i1)) ;
3822 " Need Alen >= "ID", but given only Alen = "ID".\n",
3829 "Column "ID" has a negative number of entries ("ID").\n",
3836 "Row index (row "ID") out of bounds ("ID" to "ID") in"
3875 const Int Order [ ],
3884 for (
i = 0 ;
i <
nn ;
i++)
3890 Temp [k] = Front [
i] ;
3894 for (k = 0 ; k < nfr ; k++)
3896 Front [k] = Temp [k] ;
3920 Int j, parent, frsize, r,
c ;
3922 for (
j = 0 ;
j <
nn ;
j++)
3931 DEBUG1 ((
"\n\n========================================FRONTS:\n")) ;
3932 for (
j = 0 ;
j <
nn ;
j++)
3937 parent = Parent [
j] ;
3945 j, Npiv [
j], frsize, parent)) ;
3946 Fsize [
j] =
MAX (Fsize [
j], frsize) ;
3948 if (parent !=
EMPTY)
3951 ASSERT (Npiv [parent] > 0) ;
3953 Fsize [parent] =
MAX (Fsize [parent], Fsize [
j]) ;
3955 parent, Fsize [parent]));
3959 DEBUG1 ((
"fsize done\n")) ;
3991 Int i,
j, k, parent, frsize,
f, fprev, maxfrsize, bigfprev, bigf, fnext ;
3993 for (
j = 0 ;
j <
nn ;
j++)
4003 for (
j =
nn-1 ;
j >= 0 ;
j--)
4008 parent = Parent [
j] ;
4009 if (parent !=
EMPTY)
4013 Sibling [
j] = Child [parent] ;
4016 Child [parent] =
j ;
4024 Int nels, ff, nchild ;
4025 DEBUG1 ((
"\n\n================================ ccolamd_postorder:\n"));
4027 for (
j = 0 ;
j <
nn ;
j++)
4032 " parent "ID" maxfr "ID"\n",
j, nels,
4033 Nv [
j], Fsize [
j], Parent [
j], Fsize [
j])) ;
4037 DEBUG1 ((
" Children: ")) ;
4038 for (ff = Child [
j] ; ff !=
EMPTY ; ff = Sibling [ff])
4045 parent = Parent [
j] ;
4056 for (
i = 0 ;
i <
nn ;
i++)
4058 if (Nv [
i] > 0 && Child [
i] !=
EMPTY)
4063 DEBUG1 ((
"Before partial sort, element "ID"\n",
i)) ;
4065 for (
f = Child [
i] ;
f !=
EMPTY ;
f = Sibling [
f])
4077 for (
f = Child [
i] ;
f !=
EMPTY ;
f = Sibling [
f])
4079 frsize = Fsize [
f] ;
4080 if (frsize >= maxfrsize)
4083 maxfrsize = frsize ;
4090 fnext = Sibling [bigf] ;
4093 " fprev " ID"\n", bigf, maxfrsize, bigfprev, fnext, fprev)) ;
4099 if (bigfprev ==
EMPTY)
4107 Sibling [bigfprev] = fnext ;
4111 Sibling [bigf] =
EMPTY ;
4112 Sibling [fprev] = bigf ;
4116 DEBUG1 ((
"After partial sort, element "ID"\n",
i)) ;
4117 for (
f = Child [
i] ;
f !=
EMPTY ;
f = Sibling [
f])
4130 for (
i = 0 ;
i <
nn ;
i++)
4137 for (
i = 0 ;
i <
nn ;
i++)
4143 DEBUG1 ((
"Root of assembly tree "ID"\n",
i)) ;
4164 const Int Sibling [ ],
4184 for (
f = Child [
i] ;
f !=
EMPTY ;
f = Sibling [
f])
4212 for (
f = Child [
i] ;
f !=
EMPTY ;
f = Sibling [
f])
4217 for (
f = Child [
i] ;
f !=
EMPTY ;
f = Sibling [
f])
4302 for (
c = 0 ;
c < n_col ;
c++)
4308 DEBUG4 ((
"initial live col %5d %5d %5d\n",
c,
len, score)) ;
4311 ASSERT (Col [
c].shared1.thickness == 1) ;
4322 i = Col [
c].shared2.order ;
4324 ASSERT (
i >= cset_start [cs] &&
i < cset_start [cs+1]) ;
4328 for (r = 0 ; r < n_row ; r++)
4334 deg =
Row [r].shared1.degree ;
4337 rp = &
A [
Row [r].start] ;
4387 if (n_col > 10000 && ccolamd_debug <= 0)
4392 DEBUG4 ((
"Degree lists: "ID"\n", min_score)) ;
4393 for (deg = 0 ; deg <= n_col ; deg++)
4411 DEBUG4 ((
"should "ID" have "ID"\n", should, have)) ;
4412 ASSERT (should == have) ;
4416 if (n_row > 10000 && ccolamd_debug <= 0)
4455 ASSERT (tag_mark > 0 && tag_mark <= max_mark) ;
4456 if (n_row > 10000 && ccolamd_debug <= 0)
4460 for (r = 0 ; r < n_row ; r++)
4462 ASSERT (
Row [r].shared2.mark < tag_mark) ;
4495 if (ccolamd_debug < 3)
4499 DEBUG3 ((
"DUMP MATRIX:\n")) ;
4500 for (r = 0 ; r < n_row ; r++)
4509 Row [r].start,
Row [r].length,
Row [r].shared1.degree,
4510 Row [r].thickness)) ;
4512 rp = &
A [
Row [r].start] ;
4513 rp_end = rp +
Row [r].length ;
4521 for (
c = 0 ;
c < n_col ;
c++)
4529 Col [
c].start, Col [
c].length,
4530 Col [
c].shared1.thickness, Col [
c].shared2.score)) ;
4532 cp_end = cp + Col [
c].length ;
4570 ASSERT (ncols <= Col [super_c].shared1.thickness) ;
4572 ASSERT (ncols == Col [super_c].shared1.thickness) ;
4581 PRIVATE void ccolamd_get_debug
4590 debug_file = fopen (
"debug",
"r") ;
4593 (void) fscanf (debug_file,
""ID"", &ccolamd_debug) ;
4594 (void) fclose (debug_file) ;
4598 DEBUG1 ((
"%s: debug version, D = "ID" (THIS WILL BE SLOW!)\n",
4599 method, ccolamd_debug)) ;
4600 DEBUG1 ((
" Debug printing level: "ID"\n", ccolamd_debug)) ;