18#include "absl/strings/str_format.h"
30template <
typename Matrix>
31EntryIndex ComputeNumEntries(
const Matrix& matrix) {
33 const ColIndex num_cols(matrix.num_cols());
34 for (ColIndex
col(0);
col < num_cols; ++
col) {
43template <
typename Matrix>
44Fractional ComputeOneNormTemplate(
const Matrix& matrix) {
46 const ColIndex num_cols(matrix.num_cols());
47 for (ColIndex
col(0);
col < num_cols; ++
col) {
51 column_norm += fabs(e.coefficient());
62template <
typename Matrix>
63Fractional ComputeInfinityNormTemplate(
const Matrix& matrix) {
65 const ColIndex num_cols(matrix.num_cols());
66 for (ColIndex
col(0);
col < num_cols; ++
col) {
69 row_sum[e.row()] += fabs(e.coefficient());
75 const RowIndex num_rows(matrix.num_rows());
76 for (RowIndex
row(0);
row < num_rows; ++
row) {
89#if (!defined(_MSC_VER) || (_MSC_VER >= 1800))
91 std::initializer_list<std::initializer_list<Fractional>> init_list) {
93 num_rows_ = RowIndex(init_list.size());
95 for (std::initializer_list<Fractional> init_row : init_list) {
112 num_rows_ = RowIndex(0);
116 return columns_.empty() || num_rows_ == 0;
120 const ColIndex
num_cols(columns_.size());
122 columns_[
col].CleanUp();
128 const ColIndex
num_cols(columns_.size());
136 const ColIndex
num_cols(columns_.size());
146 const ColIndex result = columns_.size();
155 columns_.push_back(std::move(new_col));
160 columns_.swap(matrix->columns_);
161 std::swap(num_rows_, matrix->num_rows_);
167 columns_[
col].Clear();
180template <
typename Matrix>
189 ++row_degree[e.row()];
200 columns_[transposed_col].SetCoefficient(transposed_row, e.coefficient());
207 Reset(ColIndex(0), matrix.num_rows_);
208 columns_ = matrix.columns_;
211template <
typename Matrix>
218 for (
const auto e :
a.column(inverse_col_perm[
col])) {
219 columns_[
col].SetCoefficient(row_perm[e.row()], e.coefficient());
245 columns_[
col].CleanUp();
246 dense_column.
Clear();
257 for (ColIndex col_b(0); col_b <
num_cols; ++col_b) {
259 if (eb.coefficient() == 0.0) {
271 columns_[col_b].CleanUp();
277 if (columns_to_delete.
empty())
return;
278 ColIndex new_index(0);
279 const ColIndex
num_cols = columns_.size();
281 if (
col >= columns_to_delete.
size() || !columns_to_delete[
col]) {
282 columns_[
col].Swap(&(columns_[new_index]));
286 columns_.resize(new_index);
292 for (RowIndex
row(0);
row < num_rows_; ++
row) {
296 for (ColIndex
col(0);
col < end; ++
col) {
297 columns_[
col].ApplyPartialRowPermutation(permutation);
308 for (ColIndex
col(0);
col < end; ++
col) {
310 columns_[
col].AppendEntriesWithOffset(source_column, offset);
317 const ColIndex
num_cols(columns_.size());
319 columns_[
col].ApplyRowPermutation(row_perm);
324 return columns_[
col].LookUpCoefficient(
row);
343 if (fabs(e.coefficient() - dense_column.
GetCoefficient(e.row())) >
356 if (fabs(e.coefficient() - dense_column_a.
GetCoefficient(e.row())) >
362 dense_column.
Clear();
363 dense_column_a.
Clear();
374 *max_magnitude = 0.0;
377 const Fractional magnitude = fabs(e.coefficient());
378 if (magnitude != 0.0) {
379 *min_magnitude =
std::min(*min_magnitude, magnitude);
380 *max_magnitude =
std::max(*max_magnitude, magnitude);
384 if (*max_magnitude == 0.0) {
385 *min_magnitude = 0.0;
390 return ComputeNumEntries(*
this);
393 return ComputeOneNormTemplate(*
this);
396 return ComputeInfinityNormTemplate(*
this);
401 const ColIndex
num_cols(columns_.size());
403 for (RowIndex
row(0);
row < num_rows_; ++
row) {
408 result.append(
"}\n");
413void SparseMatrix::Reset(ColIndex num_cols, RowIndex num_rows) {
421 return ComputeOneNormTemplate(*
this);
424 return ComputeInfinityNormTemplate(*
this);
428template void SparseMatrix::PopulateFromTranspose<SparseMatrix>(
430template void SparseMatrix::PopulateFromPermutedMatrix<SparseMatrix>(
433template void SparseMatrix::PopulateFromPermutedMatrix<CompactSparseMatrixView>(
465 for (
const RowIndex
row :
input.rows_) {
479 for (
const EntryIndex i :
input.Column(
col)) {
495 diagonal_coefficients_ =
input.diagonal_coefficients_;
496 all_diagonal_coefficients_are_one_ =
input.all_diagonal_coefficients_are_one_;
506 first_non_identity_column_ = 0;
507 const ColIndex end = diagonal_coefficients_.
size();
508 while (first_non_identity_column_ < end &&
510 diagonal_coefficients_[first_non_identity_column_] == 1.0) {
511 ++first_non_identity_column_;
526 first_non_identity_column_ = 0;
527 all_diagonal_coefficients_are_one_ =
true;
529 pruned_ends_.
resize(col_capacity);
530 diagonal_coefficients_.
resize(col_capacity);
544 if (dense_column[
row] != 0.0) {
555 const DenseColumn& dense_column,
const std::vector<RowIndex>& non_zeros) {
557 for (
const RowIndex
row : non_zeros) {
570 DenseColumn* column, std::vector<RowIndex>* non_zeros) {
571 for (
const RowIndex
row : *non_zeros) {
576 (*column)[
row] = 0.0;
595 diagonal_coefficients_.
swap(other->diagonal_coefficients_);
596 std::swap(first_non_identity_column_, other->first_non_identity_column_);
597 std::swap(all_diagonal_coefficients_are_one_,
598 other->all_diagonal_coefficients_are_one_);
602 return ComputeNumEntries(*
this);
605 return ComputeOneNormTemplate(*
this);
608 return ComputeInfinityNormTemplate(*
this);
614void TriangularMatrix::CloseCurrentColumn(
Fractional diagonal_value) {
619 diagonal_coefficients_[
num_cols_] = diagonal_value;
629 diagonal_value == 1.0) {
632 all_diagonal_coefficients_are_one_ =
633 all_diagonal_coefficients_are_one_ && (diagonal_value == 1.0);
637 CloseCurrentColumn(diagonal_value);
641 RowIndex diagonal_row) {
644 if (e.row() == diagonal_row) {
645 diagonal_value = e.coefficient();
652 CloseCurrentColumn(diagonal_value);
660 if (e.row() != diagonal_row) {
661 if (e.coefficient() != 0.0) {
666 DCHECK_EQ(e.coefficient(), diagonal_coefficient);
669 CloseCurrentColumn(1.0);
680 CloseCurrentColumn(diagonal_value);
694 if (diagonal_coefficients_[
col] == 0.0)
return false;
704 if (diagonal_coefficients_[
col] == 0.0)
return false;
743 if (all_diagonal_coefficients_are_one_) {
744 LowerSolveStartingAtInternal<true>(start, rhs);
746 LowerSolveStartingAtInternal<false>(start, rhs);
750template <
bool diagonal_of_ones>
751void TriangularMatrix::LowerSolveStartingAtInternal(ColIndex start,
754 const ColIndex begin =
std::max(start, first_non_identity_column_);
755 const ColIndex end = diagonal_coefficients_.
size();
756 for (ColIndex
col(begin);
col < end; ++
col) {
758 if (
value == 0.0)
continue;
760 diagonal_of_ones ?
value :
value / diagonal_coefficients_[
col];
761 if (!diagonal_of_ones) {
771 if (all_diagonal_coefficients_are_one_) {
772 UpperSolveInternal<true>(rhs);
774 UpperSolveInternal<false>(rhs);
778template <
bool diagonal_of_ones>
779void TriangularMatrix::UpperSolveInternal(
DenseColumn* rhs)
const {
781 const ColIndex end = first_non_identity_column_;
782 for (ColIndex
col(diagonal_coefficients_.
size() - 1);
col >= end; --
col) {
784 if (
value == 0.0)
continue;
786 diagonal_of_ones ?
value :
value / diagonal_coefficients_[
col];
787 if (!diagonal_of_ones) {
795 for (EntryIndex i(
starts_[
col + 1] - 1); i >= i_end; --i) {
802 if (all_diagonal_coefficients_are_one_) {
803 TransposeUpperSolveInternal<true>(rhs);
805 TransposeUpperSolveInternal<false>(rhs);
809template <
bool diagonal_of_ones>
810void TriangularMatrix::TransposeUpperSolveInternal(
DenseColumn* rhs)
const {
813 EntryIndex i =
starts_[first_non_identity_column_];
814 for (ColIndex
col(first_non_identity_column_);
col < end; ++
col) {
823 for (; i < i_end; ++i) {
827 diagonal_of_ones ? sum : sum / diagonal_coefficients_[
col];
832 if (all_diagonal_coefficients_are_one_) {
833 TransposeLowerSolveInternal<true>(rhs);
835 TransposeLowerSolveInternal<false>(rhs);
839template <
bool diagonal_of_ones>
840void TriangularMatrix::TransposeLowerSolveInternal(
DenseColumn* rhs)
const {
842 const ColIndex end = first_non_identity_column_;
851 for (;
col >= end; --
col) {
861 for (; i >= i_end; --i) {
865 diagonal_of_ones ? sum : sum / diagonal_coefficients_[
col];
871 if (all_diagonal_coefficients_are_one_) {
872 HyperSparseSolveInternal<true>(rhs, non_zero_rows);
874 HyperSparseSolveInternal<false>(rhs, non_zero_rows);
878template <
bool diagonal_of_ones>
879void TriangularMatrix::HyperSparseSolveInternal(
883 for (
const RowIndex
row : *non_zero_rows) {
884 if ((*rhs)[
row] == 0.0)
continue;
887 diagonal_of_ones ? (*rhs)[
row]
888 : (*rhs)[
row] / diagonal_coefficients_[row_as_col];
890 for (
const EntryIndex i :
Column(row_as_col)) {
893 (*non_zero_rows)[new_size] =
row;
896 non_zero_rows->resize(new_size);
901 if (all_diagonal_coefficients_are_one_) {
902 HyperSparseSolveWithReversedNonZerosInternal<true>(rhs, non_zero_rows);
904 HyperSparseSolveWithReversedNonZerosInternal<false>(rhs, non_zero_rows);
908template <
bool diagonal_of_ones>
909void TriangularMatrix::HyperSparseSolveWithReversedNonZerosInternal(
912 int new_start = non_zero_rows->size();
913 for (
const RowIndex
row :
Reverse(*non_zero_rows)) {
914 if ((*rhs)[
row] == 0.0)
continue;
917 diagonal_of_ones ? (*rhs)[
row]
918 : (*rhs)[
row] / diagonal_coefficients_[row_as_col];
920 for (
const EntryIndex i :
Column(row_as_col)) {
924 (*non_zero_rows)[new_start] =
row;
926 non_zero_rows->erase(non_zero_rows->begin(),
927 non_zero_rows->begin() + new_start);
932 if (all_diagonal_coefficients_are_one_) {
933 TransposeHyperSparseSolveInternal<true>(rhs, non_zero_rows);
935 TransposeHyperSparseSolveInternal<false>(rhs, non_zero_rows);
939template <
bool diagonal_of_ones>
940void TriangularMatrix::TransposeHyperSparseSolveInternal(
944 for (
const RowIndex
row : *non_zero_rows) {
947 for (
const EntryIndex i :
Column(row_as_col)) {
951 diagonal_of_ones ? sum : sum / diagonal_coefficients_[row_as_col];
953 (*non_zero_rows)[new_size] =
row;
957 non_zero_rows->resize(new_size);
962 if (all_diagonal_coefficients_are_one_) {
963 TransposeHyperSparseSolveWithReversedNonZerosInternal<true>(rhs,
966 TransposeHyperSparseSolveWithReversedNonZerosInternal<false>(rhs,
971template <
bool diagonal_of_ones>
972void TriangularMatrix::TransposeHyperSparseSolveWithReversedNonZerosInternal(
975 int new_start = non_zero_rows->size();
976 for (
const RowIndex
row :
Reverse(*non_zero_rows)) {
982 EntryIndex i =
starts_[row_as_col + 1] - 1;
983 const EntryIndex i_end =
starts_[row_as_col];
984 for (; i >= i_end; --i) {
988 diagonal_of_ones ? sum : sum / diagonal_coefficients_[row_as_col];
991 (*non_zero_rows)[new_start] =
row;
994 non_zero_rows->erase(non_zero_rows->begin(),
995 non_zero_rows->begin() + new_start);
1002 DCHECK(all_diagonal_coefficients_are_one_);
1008 initially_all_zero_scratchpad_[e.row()] = e.coefficient();
1011 const RowIndex end_row(partial_inverse_row_perm.
size());
1014 const RowIndex permuted_row = partial_inverse_row_perm[
row];
1015 const Fractional pivot = initially_all_zero_scratchpad_[permuted_row];
1016 if (pivot == 0.0)
continue;
1018 initially_all_zero_scratchpad_[
EntryRow(i)] -=
1026 if (initially_all_zero_scratchpad_[
row] != 0.0) {
1027 if (row_perm[
row] < 0) {
1032 initially_all_zero_scratchpad_[
row] = 0.0;
1042 DCHECK(all_diagonal_coefficients_are_one_);
1049 &upper_column_rows_);
1053 for (
const auto e : rhs) {
1054 initially_all_zero_scratchpad_[e.row()] = e.coefficient();
1059 lower_column->
Clear();
1066 EntryIndex(upper_column_rows_.size()));
1067 for (
const RowIndex permuted_row :
Reverse(upper_column_rows_)) {
1068 const Fractional pivot = initially_all_zero_scratchpad_[permuted_row];
1069 if (pivot == 0.0)
continue;
1072 initially_all_zero_scratchpad_[permuted_row] = 0.0;
1073 const ColIndex row_as_col =
RowToColIndex(row_perm[permuted_row]);
1076 DCHECK_EQ(diagonal_coefficients_[row_as_col], 1.0);
1077 for (
const auto e :
column(row_as_col)) {
1078 initially_all_zero_scratchpad_[e.row()] -= e.coefficient() * pivot;
1083 lower_column->
Reserve(EntryIndex(lower_column_rows_.size()));
1084 for (
const RowIndex permuted_row : lower_column_rows_) {
1085 const Fractional pivot = initially_all_zero_scratchpad_[permuted_row];
1086 initially_all_zero_scratchpad_[permuted_row] = 0.0;
1121 lower_column_rows->clear();
1122 upper_column_rows->clear();
1123 nodes_to_explore_.clear();
1128 stored_[e.row()] =
true;
1131 nodes_to_explore_.push_back(e.row());
1145 while (!nodes_to_explore_.empty()) {
1146 const RowIndex
row = nodes_to_explore_.back();
1152 nodes_to_explore_.pop_back();
1153 const RowIndex explored_row = nodes_to_explore_.back();
1154 nodes_to_explore_.pop_back();
1155 DCHECK(!stored_[explored_row]);
1156 stored_[explored_row] =
true;
1157 upper_column_rows->
push_back(explored_row);
1168 EntryIndex end = pruned_ends_[
col];
1170 const RowIndex entry_row =
EntryRow(i);
1171 if (!marked_[entry_row]) {
1180 marked_[entry_row] =
false;
1184 pruned_ends_[
col] = end;
1190 nodes_to_explore_.pop_back();
1198 stored_[
row] =
true;
1200 nodes_to_explore_.pop_back();
1207 const EntryIndex end = pruned_ends_[
col];
1208 for (EntryIndex i =
starts_[
col]; i < end; ++i) {
1209 const RowIndex entry_row =
EntryRow(i);
1210 if (!stored_[entry_row]) {
1211 nodes_to_explore_.push_back(entry_row);
1213 marked_[entry_row] =
true;
1221 for (
const RowIndex
row : *lower_column_rows) {
1222 stored_[
row] =
false;
1224 for (
const RowIndex
row : *upper_column_rows) {
1225 stored_[
row] =
false;
1231 if (non_zero_rows->empty())
return;
1241 const int sparsity_threshold =
1242 static_cast<int>(0.025 *
static_cast<double>(
num_rows_.value()));
1243 const int num_ops_threshold =
1244 static_cast<int>(0.05 *
static_cast<double>(
num_rows_.value()));
1245 int num_ops = non_zero_rows->size();
1246 if (num_ops > sparsity_threshold) {
1247 non_zero_rows->clear();
1253 nodes_to_explore_.clear();
1254 nodes_to_explore_.swap(*non_zero_rows);
1258 while (!nodes_to_explore_.empty()) {
1259 const RowIndex
row = nodes_to_explore_.back();
1264 nodes_to_explore_.pop_back();
1265 const RowIndex explored_row = -
row - 1;
1266 stored_[explored_row] =
true;
1273 nodes_to_explore_.pop_back();
1282 nodes_to_explore_.back() = -
row - 1;
1285 const RowIndex entry_row =
EntryRow(i);
1286 if (!stored_[entry_row]) {
1287 nodes_to_explore_.push_back(entry_row);
1294 if (num_ops > num_ops_threshold)
break;
1298 for (
const RowIndex
row : *non_zero_rows) {
1299 stored_[
row] =
false;
1303 if (num_ops > num_ops_threshold) non_zero_rows->
clear();
1308 static const Fractional kDefaultSparsityRatio = 0.025;
1309 static const Fractional kDefaultNumOpsRatio = 0.05;
1311 kDefaultNumOpsRatio);
1317 if (non_zero_rows->empty())
return;
1320 const int sparsity_threshold =
1321 static_cast<int>(0.025 *
static_cast<double>(
num_rows_.value()));
1322 const int num_ops_threshold =
1323 static_cast<int>(0.05 *
static_cast<double>(
num_rows_.value()));
1324 int num_ops = non_zero_rows->size();
1325 if (num_ops > sparsity_threshold) {
1326 non_zero_rows->clear();
1331 for (
const RowIndex
row : *non_zero_rows) stored_[
row] =
true;
1332 for (
int i = 0; i < non_zero_rows->size(); ++i) {
1333 const RowIndex
row = (*non_zero_rows)[i];
1336 const RowIndex entry_row =
EntryRow(i);
1337 if (!stored_[entry_row]) {
1338 non_zero_rows->push_back(entry_row);
1339 stored_[entry_row] =
true;
1342 if (num_ops > num_ops_threshold)
break;
1345 for (
const RowIndex
row : *non_zero_rows) stored_[
row] =
false;
1346 if (num_ops > num_ops_threshold) {
1347 non_zero_rows->
clear();
1349 std::sort(non_zero_rows->begin(), non_zero_rows->end());
1358 if (first_non_identity_column_ ==
num_cols_) {
1367 for (
int i = 0; i <
num_cols; ++i) {
1368 const ColIndex
col(is_upper ?
num_cols - 1 - i : i);
1371 std::abs(diagonal_coefficients_[
col]);
1374 for (
const EntryIndex i :
Column(
col)) {
1379 return *std::max_element(row_norm_estimate.
begin(), row_norm_estimate.
end());
1400 row_sum[
row] += std::abs(right_hand_side[
row]);
#define DCHECK_LE(val1, val2)
#define DCHECK_NE(val1, val2)
#define DCHECK_GE(val1, val2)
#define DCHECK_LT(val1, val2)
#define DCHECK(condition)
#define DCHECK_EQ(val1, val2)
void push_back(const value_type &x)
void swap(StrongVector &x)
ColIndex AddDenseColumn(const DenseColumn &dense_column)
StrictITIVector< ColIndex, EntryIndex > starts_
ColIndex AddDenseColumnWithNonZeros(const DenseColumn &dense_column, const std::vector< RowIndex > &non_zeros)
ColIndex AddAndClearColumnWithNonZeros(DenseColumn *column, std::vector< RowIndex > *non_zeros)
void Swap(CompactSparseMatrix *other)
StrictITIVector< EntryIndex, RowIndex > rows_
ColIndex AddDenseColumnPrefix(const DenseColumn &dense_column, RowIndex start)
RowIndex num_rows() const
Fractional EntryCoefficient(EntryIndex i) const
StrictITIVector< EntryIndex, Fractional > coefficients_
void PopulateFromTranspose(const CompactSparseMatrix &input)
::util::IntegerRange< EntryIndex > Column(ColIndex col) const
void Reset(RowIndex num_rows)
void PopulateFromMatrixView(const MatrixView &input)
RowIndex EntryRow(EntryIndex i) const
EntryIndex num_entries() const
ColumnView column(ColIndex col) const
EntryIndex ColumnNumEntries(ColIndex col) const
Fractional ComputeInfinityNorm() const
Fractional ComputeOneNorm() const
EntryIndex num_entries() const
Fractional ComputeInfinityNorm() const
Fractional ComputeOneNorm() const
EntryIndex num_entries() const
void AddToCoefficient(RowIndex row, Fractional value)
void PopulateSparseColumn(SparseColumn *sparse_column) const
Fractional GetCoefficient(RowIndex row) const
void AppendUnitVector(RowIndex row, Fractional value)
void PopulateFromLinearCombination(Fractional alpha, const SparseMatrix &a, Fractional beta, const SparseMatrix &b)
void PopulateFromPermutedMatrix(const Matrix &a, const RowPermutation &row_perm, const ColumnPermutation &inverse_col_perm)
bool CheckNoDuplicates() const
void PopulateFromTranspose(const Matrix &input)
void PopulateFromIdentity(ColIndex num_cols)
Fractional ComputeInfinityNorm() const
ColIndex num_cols() const
void SetNumRows(RowIndex num_rows)
SparseColumn * mutable_column(ColIndex col)
Fractional LookUpValue(RowIndex row, ColIndex col) const
void Swap(SparseMatrix *matrix)
Fractional ComputeOneNorm() const
void ComputeMinAndMaxMagnitudes(Fractional *min_magnitude, Fractional *max_magnitude) const
void DeleteRows(RowIndex num_rows, const RowPermutation &permutation)
ColIndex AppendEmptyColumn()
RowIndex num_rows() const
void PopulateFromProduct(const SparseMatrix &a, const SparseMatrix &b)
bool AppendRowsFromSparseMatrix(const SparseMatrix &matrix)
void DeleteColumns(const DenseBooleanRow &columns_to_delete)
void PopulateFromSparseMatrix(const SparseMatrix &matrix)
void ApplyRowPermutation(const RowPermutation &row_perm)
void PopulateFromZero(RowIndex num_rows, ColIndex num_cols)
EntryIndex num_entries() const
bool Equals(const SparseMatrix &a, Fractional tolerance) const
bool CheckNoDuplicates() const
typename Iterator::Entry Entry
void Reserve(EntryIndex new_capacity)
void SetCoefficient(Index index, Fractional value)
EntryIndex num_entries() const
void resize(IntType size)
void assign(IntType size, const T &v)
void TransposeHyperSparseSolve(DenseColumn *rhs, RowIndexVector *non_zero_rows) const
void CopyToSparseMatrix(SparseMatrix *output) const
void AddTriangularColumnWithGivenDiagonalEntry(const SparseColumn &column, RowIndex diagonal_row, Fractional diagonal_value)
void UpperSolve(DenseColumn *rhs) const
void HyperSparseSolve(DenseColumn *rhs, RowIndexVector *non_zero_rows) const
Fractional ComputeInverseInfinityNorm() const
void Swap(TriangularMatrix *other)
void PopulateFromTriangularSparseMatrix(const SparseMatrix &input)
ColIndex num_cols() const
bool IsLowerTriangular() const
void LowerSolve(DenseColumn *rhs) const
void TransposeHyperSparseSolveWithReversedNonZeros(DenseColumn *rhs, RowIndexVector *non_zero_rows) const
void LowerSolveStartingAt(ColIndex start, DenseColumn *rhs) const
void PopulateFromTranspose(const TriangularMatrix &input)
void CopyColumnToSparseColumn(ColIndex col, SparseColumn *output) const
void AddAndNormalizeTriangularColumn(const SparseColumn &column, RowIndex diagonal_row, Fractional diagonal_coefficient)
bool IsUpperTriangular() const
RowIndex num_rows() const
void ComputeRowsToConsiderInSortedOrder(RowIndexVector *non_zero_rows, Fractional sparsity_ratio, Fractional num_ops_ratio) const
void AddTriangularColumn(const ColumnView &column, RowIndex diagonal_row)
void TransposeLowerSolve(DenseColumn *rhs) const
void PermutedLowerSparseSolve(const ColumnView &rhs, const RowPermutation &row_perm, SparseColumn *lower, SparseColumn *upper)
void PermutedComputeRowsToConsider(const ColumnView &rhs, const RowPermutation &row_perm, RowIndexVector *lower_column_rows, RowIndexVector *upper_column_rows)
void ApplyRowPermutationToNonDiagonalEntries(const RowPermutation &row_perm)
void TransposeUpperSolve(DenseColumn *rhs) const
void ComputeRowsToConsiderWithDfs(RowIndexVector *non_zero_rows) const
Fractional ComputeInverseInfinityNormUpperBound() const
void PermutedLowerSolve(const SparseColumn &rhs, const RowPermutation &row_perm, const RowMapping &partial_inverse_row_perm, SparseColumn *lower, SparseColumn *upper) const
void AddDiagonalOnlyColumn(Fractional diagonal_value)
void Reset(RowIndex num_rows, ColIndex col_capacity)
void HyperSparseSolveWithReversedNonZeros(DenseColumn *rhs, RowIndexVector *non_zero_rows) const
EntryIndex num_entries() const
RowIndex ColToRowIndex(ColIndex col)
static double ToDouble(double f)
ColIndex RowToColIndex(RowIndex row)
const RowIndex kInvalidRow(-1)
std::vector< RowIndex > RowIndexVector
StrictITIVector< RowIndex, Fractional > DenseColumn
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
BeginEndReverseIteratorWrapper< Container > Reverse(const Container &c)
static int input(yyscan_t yyscanner)
#define RETURN_IF_NULL(x)