Lines Matching refs:Row
69 /* knobs [0] and stats [0]: dense row knob and output statistic. */
114 /* Row and column status */
122 /* Macros for row and column status update and checking. */
123 #define ROW_IS_DEAD(r) ROW_IS_MARKED_DEAD (Row[r].shared2.mark)
125 #define ROW_IS_ALIVE(r) (Row [r].shared2.mark >= ALIVE)
129 #define KILL_ROW(r) { Row [r].shared2.mark = DEAD ; }
137 // == Row and Column structures ==
141 Index start ; /* index for A of first row in this column, or DEAD */
175 Index start ; /* index for A of first col in this row */
176 Index length ; /* number of principal columns in this row */
179 Index degree ; /* number of principal & non-principal columns in row */
180 Index p ; /* used as a row pointer in init_rows_cols () */
185 Index first_column ;/* first column in row (used in garbage collection) */
197 argument is negative. 2*nnz space is required for the row and column
199 required for the Col and Row arrays, respectively, which are internal to
218 static Index init_rows_cols (Index n_row, Index n_col, Colamd_Row<Index> Row [], colamd_col<Index> col [], Index A [], Index p [], Index stats[COLAMD_STATS] );
221 static void init_scoring (Index n_row, Index n_col, Colamd_Row<Index> Row [], colamd_col<Index> Col [], Index A [], Index head [], double knobs[COLAMD_KNOBS], Index *p_n_row2, Index *p_n_col2, Index *p_max_deg);
224 static Index find_ordering (Index n_row, Index n_col, Index Alen, Colamd_Row<Index> Row [], colamd_col<Index> Col [], Index A [], Index head [], Index n_col2, Index max_deg, Index pfree);
233 static Index garbage_collection (Index n_row, Index n_col, Colamd_Row<Index> Row [], colamd_col<Index> Col [], Index A [], Index *pfree) ;
236 static inline Index clear_mark (Index n_row, Colamd_Row<Index> Row [] ) ;
323 * \param A row indices of the matrix, of size ALen
335 Index Row_size ; /* size of Row [], in integers */
338 Colamd_Row<Index> *Row ; /* pointer into A of Row [0..n_row] array */
343 Index max_deg ; /* maximum row degree */
417 /* === Allocate the Row and Col arrays from array A ===================== */
435 Row = (Colamd_Row<Index> *) &A [Alen + Col_size] ;
437 /* === Construct the row and column data structures ===================== */
439 if (!Eigen::internal::init_rows_cols (n_row, n_col, Row, Col, A, p, stats))
448 Eigen::internal::init_scoring (n_row, n_col, Row, Col, A, p, knobs,
453 ngarbage = Eigen::internal::find_ordering (n_row, n_col, Alen, Row, Col, A, p,
481 Takes the column form of the matrix in A and creates the row form of the
482 matrix. Also, row and column attributes are stored in the Col and Row
483 structs. If the columns are un-sorted or contain duplicate row indices,
484 this routine will also sort and remove duplicate row indices from the
495 Colamd_Row<Index> Row [], /* of size n_row+1 */
497 Index A [], /* row indices of A, of size Alen */
505 Index row ; /* a row index */
508 Index *rp ; /* a row pointer */
509 Index *rp_end ; /* a pointer to the end of a row */
510 Index last_row ; /* previous row */
537 /* === Scan columns, compute row degrees, and check row indices ========= */
539 stats [COLAMD_INFO3] = 0 ; /* number of duplicate or unsorted row indices*/
541 for (row = 0 ; row < n_row ; row++)
543 Row [row].length = 0 ;
544 Row [row].shared2.mark = -1 ;
556 row = *cp++ ;
558 /* make sure row indices within range */
559 if (row < 0 || row >= n_row)
563 stats [COLAMD_INFO2] = row ;
565 COLAMD_DEBUG0 (("colamd: row %d col %d out of bounds\n", row, col)) ;
569 if (row <= last_row || Row [row].shared2.mark == col)
571 /* row index are unsorted or repeated (or both), thus col */
575 stats [COLAMD_INFO2] = row ;
577 COLAMD_DEBUG1 (("colamd: row %d col %d unsorted/duplicate\n",row,col));
580 if (Row [row].shared2.mark != col)
582 Row [row].length++ ;
591 /* mark the row as having been seen in this column */
592 Row [row].shared2.mark = col ;
594 last_row = row ;
598 /* === Compute row pointers ============================================= */
600 /* row form of the matrix starts directly after the column */
602 Row [0].start = p [n_col] ;
603 Row [0].shared1.p = Row [0].start ;
604 Row [0].shared2.mark = -1 ;
605 for (row = 1 ; row < n_row ; row++)
607 Row [row].start = Row [row-1].start + Row [row-1].length ;
608 Row [row].shared1.p = Row [row].start ;
609 Row [row].shared2.mark = -1 ;
612 /* === Create row form ================================================== */
616 /* if cols jumbled, watch for repeated row indices */
623 row = *cp++ ;
624 if (Row [row].shared2.mark != col)
626 A [(Row [row].shared1.p)++] = col ;
627 Row [row].shared2.mark = col ;
641 A [(Row [*cp++].shared1.p)++] = col ;
646 /* === Clear the row marks and set row degrees ========================== */
648 for (row = 0 ; row < n_row ; row++)
650 Row [row].shared2.mark = 0 ;
651 Row [row].shared1.degree = Row [row].length ;
664 /* Note, we may have a gap between the col form and the row */
672 /* no duplicate row indices will exist for these columns */
679 for (row = 0 ; row < n_row ; row++)
681 rp = &A [Row [row].start] ;
682 rp_end = rp + Row [row].length ;
685 A [(p [*rp++])++] = row ;
711 Colamd_Row<Index> Row [], /* of size n_row+1 */
713 Index A [], /* column form and row form of A */
718 Index *p_max_deg /* maximum row degree */
724 Index r, row ; /* a row index */
726 Index deg ; /* degree of a row or column */
736 Index max_deg ; /* maximum row degree */
780 /* decrement the row degrees */
785 Row [*cp++].shared1.degree-- ;
796 deg = Row [r].shared1.degree ;
800 /* kill a dense or empty row */
814 /* At this point the row degrees are accurate. They reflect the number */
815 /* of "live" (non-dense) columns in each row. No empty rows exist. */
833 /* get a row */
834 row = *cp++ ;
836 if (ROW_IS_DEAD (row))
841 *new_cp++ = row ;
842 /* add row's external degree */
843 score += Row [row].shared1.degree - 1 ;
924 /* === Return number of remaining columns, and max row degree =========== */
949 Colamd_Row<Index> Row [], /* of size n_row+1 */
951 Index A [], /* column form and row form of A */
954 Index max_deg, /* Maximum row degree */
963 Index *rp ; /* a row pointer */
964 Index pivot_row ; /* current pivot row */
966 Index *new_rp ; /* modified row pointer */
967 Index pivot_row_start ; /* pointer to start of pivot row */
968 Index pivot_row_degree ; /* number of columns in pivot row */
969 Index pivot_row_length ; /* number of supercolumns in pivot row */
971 Index needed_memory ; /* free space needed for pivot row */
973 Index *rp_end ; /* pointer to the end of a row */
974 Index row ; /* a row index */
982 Index row_mark ; /* Row [row].shared2.mark */
983 Index set_difference ; /* set difference size of row with pivot row */
996 tag_mark = Eigen::internal::clear_mark (n_row, Row) ;
1046 pfree = Eigen::internal::garbage_collection (n_row, n_col, Row, Col, A, &A [pfree]) ;
1050 /* garbage collection has wiped out the Row[].shared2.mark array */
1051 tag_mark = Eigen::internal::clear_mark (n_row, Row) ;
1055 /* === Compute pivot row pattern ==================================== */
1057 /* get starting location for this new merged row */
1060 /* initialize new row counts to zero */
1064 /* in merged pivot row */
1067 /* pivot row is the union of all rows in the pivot column pattern */
1072 /* get a row */
1073 row = *cp++ ;
1074 COLAMD_DEBUG4 (("Pivot col pattern %d %d\n", ROW_IS_ALIVE (row), row)) ;
1075 /* skip if row is dead */
1076 if (ROW_IS_DEAD (row))
1080 rp = &A [Row [row].start] ;
1081 rp_end = rp + Row [row].length ;
1090 /* tag column in pivot row */
1093 /* place column in pivot row */
1105 /* === Kill all rows used to construct pivot row ==================== */
1107 /* also kill pivot row, temporarily */
1112 /* may be killing an already dead row */
1113 row = *cp++ ;
1114 COLAMD_DEBUG3 (("Kill row in pivot col: %d\n", row)) ;
1115 KILL_ROW (row) ;
1118 /* === Select a row index to use as the new pivot row =============== */
1123 /* pick the "pivot" row arbitrarily (first row in col) */
1125 COLAMD_DEBUG3 (("Pivotal row is %d\n", pivot_row)) ;
1129 /* there is no pivot row, since it is of zero length */
1138 /* score is the sum of the pivot row "length", plus the size of the */
1139 /* set differences of each row in the column minus the pattern of the */
1140 /* pivot row itself. The column ("thickness") itself is also */
1147 /* the pivot row. Thus, the amortized time to compute a column score */
1149 /* context, is the column "length", or the number of row indices */
1150 /* in that column). The number of row indices in a column is */
1158 /* pivot row is currently dead - it will be revived later. */
1160 COLAMD_DEBUG3 (("Pivot row: ")) ;
1161 /* for each column in pivot row */
1170 /* clear tags used to construct pivot row pattern */
1202 /* get a row */
1203 row = *cp++ ;
1204 row_mark = Row [row].shared2.mark ;
1210 COLAMD_ASSERT (row != pivot_row) ;
1212 /* check if the row has been seen yet */
1215 COLAMD_ASSERT (Row [row].shared1.degree <= max_deg) ;
1216 set_difference = Row [row].shared1.degree ;
1218 /* subtract column thickness from this row's set difference */
1221 /* absorb this row if the set difference becomes zero */
1224 COLAMD_DEBUG3 (("aggressive absorption. Row: %d\n", row)) ;
1225 KILL_ROW (row) ;
1230 Row [row].shared2.mark = set_difference + tag_mark ;
1240 /* for each column in pivot row */
1259 /* get a row */
1260 row = *cp++ ;
1261 COLAMD_ASSERT(row >= 0 && row < n_row) ;
1262 row_mark = Row [row].shared2.mark ;
1270 *new_cp++ = row ;
1272 hash += row ;
1287 /* nothing left but the pivot row in this column */
1351 tag_mark = Eigen::internal::clear_mark (n_row, Row) ;
1354 /* === Finalize the new pivot row, and column scores ================ */
1358 /* for each column in pivot row */
1360 /* compact the pivot row */
1372 /* add new pivot row to column */
1375 /* retrieve score so far and add on pivot row's degree. */
1377 /* row's degree was reduced due to mass elimination). */
1416 /* === Resurrect the new pivot row ================================== */
1420 /* update pivot row length to reflect any cols that were killed */
1422 Row [pivot_row].start = pivot_row_start ;
1423 Row [pivot_row].length = (Index) (new_rp - &A[pivot_row_start]) ;
1424 Row [pivot_row].shared1.degree = pivot_row_degree ;
1425 Row [pivot_row].shared2.mark = 0 ;
1426 /* pivot row is no longer dead */
1559 Index A [], /* row indices of A */
1568 Index *rp ; /* pointer to a row */
1576 Index *rp_end ; /* pointer to the end of the row */
1577 Index col ; /* a column index in the row to check */
1581 /* === Consider each column in the row ================================== */
1647 /* row indices will same order for both supercols, */
1698 all avaliable memory has been used while performing row merging. Returns
1711 Colamd_Row<Index> Row [], /* row info */
1722 Index r ; /* a row index */
1724 Index length ; /* length of a row or column */
1757 if (Row [r].length == 0)
1759 /* this row is of zero length. cannot compact it, so kill it */
1760 COLAMD_DEBUG3 (("Defrag row kill\n")) ;
1765 /* save first column index in Row [r].shared2.first_column */
1766 psrc = &A [Row [r].start] ;
1767 Row [r].shared2.first_column = *psrc ;
1769 /* flag the start of the row with the one's complement of row */
1781 /* find a negative number ... the start of a row */
1785 /* get the row index */
1789 *psrc = Row [r].shared2.first_column ;
1792 /* move and compact the row */
1794 Row [r].start = (Index) (pdest - &A [0]) ;
1795 length = Row [r].length ;
1804 Row [r].length = (Index) (pdest - &A [Row [r].start]) ;
1822 Clears the Row [].shared2.mark array, and returns the new tag_mark.
1831 Colamd_Row<Index> Row [] /* Row [0 ... n_row-1].shared2.mark is set to zero */
1842 Row [r].shared2.mark = 0 ;
