OR-Tools  8.2
lu_factorization.cc
Go to the documentation of this file.
1 // Copyright 2010-2018 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
15 
16 #include <cstddef>
17 
20 
21 namespace operations_research {
22 namespace glop {
23 
25  : is_identity_factorization_(true),
26  col_perm_(),
27  inverse_col_perm_(),
28  row_perm_(),
29  inverse_row_perm_() {}
30 
32  SCOPED_TIME_STAT(&stats_);
33  lower_.Reset(RowIndex(0), ColIndex(0));
34  upper_.Reset(RowIndex(0), ColIndex(0));
35  transpose_upper_.Reset(RowIndex(0), ColIndex(0));
36  transpose_lower_.Reset(RowIndex(0), ColIndex(0));
37  is_identity_factorization_ = true;
38  col_perm_.clear();
39  row_perm_.clear();
40  inverse_row_perm_.clear();
41  inverse_col_perm_.clear();
42 }
43 
45  const CompactSparseMatrixView& matrix) {
46  SCOPED_TIME_STAT(&stats_);
47  Clear();
48  if (matrix.num_rows().value() != matrix.num_cols().value()) {
49  GLOP_RETURN_AND_LOG_ERROR(Status::ERROR_LU, "Not a square matrix!!");
50  }
51 
53  markowitz_.ComputeLU(matrix, &row_perm_, &col_perm_, &lower_, &upper_));
54  inverse_col_perm_.PopulateFromInverse(col_perm_);
55  inverse_row_perm_.PopulateFromInverse(row_perm_);
56  ComputeTransposeUpper();
57  ComputeTransposeLower();
58 
59  is_identity_factorization_ = false;
61  stats_.lu_fill_in.Add(GetFillInPercentage(matrix));
62  stats_.basis_num_entries.Add(matrix.num_entries().value());
63  });
64  DCHECK(CheckFactorization(matrix, Fractional(1e-6)));
65  return Status::OK();
66 }
67 
69  SCOPED_TIME_STAT(&stats_);
70  if (is_identity_factorization_) return;
71 
72  ApplyPermutation(row_perm_, *x, &dense_column_scratchpad_);
73  lower_.LowerSolve(&dense_column_scratchpad_);
74  upper_.UpperSolve(&dense_column_scratchpad_);
75  ApplyPermutation(inverse_col_perm_, dense_column_scratchpad_, x);
76 }
77 
79  SCOPED_TIME_STAT(&stats_);
80  if (is_identity_factorization_) return;
81 
82  // We need to interpret y as a column for the permutation functions.
83  DenseColumn* const x = reinterpret_cast<DenseColumn*>(y);
84  ApplyInversePermutation(inverse_col_perm_, *x, &dense_column_scratchpad_);
85  upper_.TransposeUpperSolve(&dense_column_scratchpad_);
86  lower_.TransposeLowerSolve(&dense_column_scratchpad_);
87  ApplyInversePermutation(row_perm_, dense_column_scratchpad_, x);
88 }
89 
90 namespace {
91 // If non_zeros is empty, uses a dense algorithm to compute the squared L2
92 // norm of the given column, otherwise do the same with a sparse version. In
93 // both cases column is cleared.
94 Fractional ComputeSquaredNormAndResetToZero(
95  const std::vector<RowIndex>& non_zeros, DenseColumn* column) {
96  Fractional sum = 0.0;
97  if (non_zeros.empty()) {
98  sum = SquaredNorm(*column);
99  column->clear();
100  } else {
101  for (const RowIndex row : non_zeros) {
102  sum += Square((*column)[row]);
103  (*column)[row] = 0.0;
104  }
105  }
106  return sum;
107 }
108 } // namespace
109 
111  SCOPED_TIME_STAT(&stats_);
112  if (is_identity_factorization_) return SquaredNorm(a);
113 
114  non_zero_rows_.clear();
115  dense_zero_scratchpad_.resize(lower_.num_rows(), 0.0);
116  DCHECK(IsAllZero(dense_zero_scratchpad_));
117 
118  for (const SparseColumn::Entry e : a) {
119  const RowIndex permuted_row = row_perm_[e.row()];
120  dense_zero_scratchpad_[permuted_row] = e.coefficient();
121  non_zero_rows_.push_back(permuted_row);
122  }
123 
124  lower_.ComputeRowsToConsiderInSortedOrder(&non_zero_rows_);
125  if (non_zero_rows_.empty()) {
126  lower_.LowerSolve(&dense_zero_scratchpad_);
127  } else {
128  lower_.HyperSparseSolve(&dense_zero_scratchpad_, &non_zero_rows_);
129  upper_.ComputeRowsToConsiderInSortedOrder(&non_zero_rows_);
130  }
131  if (non_zero_rows_.empty()) {
132  upper_.UpperSolve(&dense_zero_scratchpad_);
133  } else {
134  upper_.HyperSparseSolveWithReversedNonZeros(&dense_zero_scratchpad_,
135  &non_zero_rows_);
136  }
137  return ComputeSquaredNormAndResetToZero(non_zero_rows_,
138  &dense_zero_scratchpad_);
139 }
140 
142  if (is_identity_factorization_) return 1.0;
143  SCOPED_TIME_STAT(&stats_);
144  const RowIndex permuted_row =
145  col_perm_.empty() ? row : ColToRowIndex(col_perm_[RowToColIndex(row)]);
146 
147  non_zero_rows_.clear();
148  dense_zero_scratchpad_.resize(lower_.num_rows(), 0.0);
149  DCHECK(IsAllZero(dense_zero_scratchpad_));
150  dense_zero_scratchpad_[permuted_row] = 1.0;
151  non_zero_rows_.push_back(permuted_row);
152 
153  transpose_upper_.ComputeRowsToConsiderInSortedOrder(&non_zero_rows_);
154  if (non_zero_rows_.empty()) {
155  transpose_upper_.LowerSolveStartingAt(RowToColIndex(permuted_row),
156  &dense_zero_scratchpad_);
157  } else {
158  transpose_upper_.HyperSparseSolve(&dense_zero_scratchpad_, &non_zero_rows_);
159  transpose_lower_.ComputeRowsToConsiderInSortedOrder(&non_zero_rows_);
160  }
161  if (non_zero_rows_.empty()) {
162  transpose_lower_.UpperSolve(&dense_zero_scratchpad_);
163  } else {
164  transpose_lower_.HyperSparseSolveWithReversedNonZeros(
165  &dense_zero_scratchpad_, &non_zero_rows_);
166  }
167  return ComputeSquaredNormAndResetToZero(non_zero_rows_,
168  &dense_zero_scratchpad_);
169 }
170 
171 namespace {
172 // Returns whether 'b' is equal to 'a' permuted by the given row permutation
173 // 'perm'.
174 bool AreEqualWithPermutation(const DenseColumn& a, const DenseColumn& b,
175  const RowPermutation& perm) {
176  const RowIndex num_rows = perm.size();
177  for (RowIndex row(0); row < num_rows; ++row) {
178  if (a[row] != b[perm[row]]) return false;
179  }
180  return true;
181 }
182 } // namespace
183 
185  ScatteredColumn* x) const {
186  SCOPED_TIME_STAT(&stats_);
187  if (!is_identity_factorization_) {
188  DCHECK(AreEqualWithPermutation(a, x->values, row_perm_));
190  if (x->non_zeros.empty()) {
191  lower_.LowerSolve(&x->values);
192  } else {
193  lower_.HyperSparseSolve(&x->values, &x->non_zeros);
194  }
195  }
196 }
197 
198 template <typename Column>
199 void LuFactorization::RightSolveLInternal(const Column& b,
200  ScatteredColumn* x) const {
201  // This code is equivalent to
202  // b.PermutedCopyToDenseVector(row_perm_, num_rows, x);
203  // but it also computes the first column index which does not correspond to an
204  // identity column of lower_ thus exploiting a bit the hyper-sparsity
205  // of b.
206  ColIndex first_column_to_consider(RowToColIndex(x->values.size()));
207  const ColIndex limit = lower_.GetFirstNonIdentityColumn();
208  for (const auto e : b) {
209  const RowIndex permuted_row = row_perm_[e.row()];
210  (*x)[permuted_row] = e.coefficient();
211  x->non_zeros.push_back(permuted_row);
212 
213  // The second condition only works because the elements on the diagonal of
214  // lower_ are all equal to 1.0.
215  const ColIndex col = RowToColIndex(permuted_row);
216  if (col < limit || lower_.ColumnIsDiagonalOnly(col)) {
217  DCHECK_EQ(1.0, lower_.GetDiagonalCoefficient(col));
218  continue;
219  }
220  first_column_to_consider = std::min(first_column_to_consider, col);
221  }
222 
224  x->non_zeros_are_sorted = true;
225  if (x->non_zeros.empty()) {
226  lower_.LowerSolveStartingAt(first_column_to_consider, &x->values);
227  } else {
228  lower_.HyperSparseSolve(&x->values, &x->non_zeros);
229  }
230 }
231 
233  ScatteredColumn* x) const {
234  SCOPED_TIME_STAT(&stats_);
235  DCHECK(IsAllZero(x->values));
236  x->non_zeros.clear();
237  if (is_identity_factorization_) {
238  for (const ColumnView::Entry e : b) {
239  (*x)[e.row()] = e.coefficient();
240  x->non_zeros.push_back(e.row());
241  }
242  return;
243  }
244 
245  RightSolveLInternal(b, x);
246 }
247 
249  if (is_identity_factorization_) return;
250  if (x->non_zeros.empty()) {
251  PermuteWithScratchpad(row_perm_, &dense_zero_scratchpad_, &x->values);
252  lower_.LowerSolve(&x->values);
253  return;
254  }
255 
256  PermuteWithKnownNonZeros(row_perm_, &dense_zero_scratchpad_, &x->values,
257  &x->non_zeros);
259  x->non_zeros_are_sorted = true;
260  if (x->non_zeros.empty()) {
261  lower_.LowerSolve(&x->values);
262  } else {
263  lower_.HyperSparseSolve(&x->values, &x->non_zeros);
264  }
265 }
266 
268  ScatteredColumn* x) const {
269  SCOPED_TIME_STAT(&stats_);
270  DCHECK(IsAllZero(x->values));
271  x->non_zeros.clear();
272 
273  if (is_identity_factorization_) {
274  *x = b;
275  return;
276  }
277 
278  if (b.non_zeros.empty()) {
279  *x = b;
280  return RightSolveLWithNonZeros(x);
281  }
282 
283  RightSolveLInternal(b, x);
284 }
285 
287  SCOPED_TIME_STAT(&stats_);
288  CHECK(col_perm_.empty());
289  if (is_identity_factorization_) return;
290 
291  DenseColumn* const x = reinterpret_cast<DenseColumn*>(&y->values);
292  RowIndexVector* const nz = reinterpret_cast<RowIndexVector*>(&y->non_zeros);
293  transpose_upper_.ComputeRowsToConsiderInSortedOrder(nz);
294  y->non_zeros_are_sorted = true;
295  if (nz->empty()) {
296  upper_.TransposeUpperSolve(x);
297  } else {
298  upper_.TransposeHyperSparseSolve(x, nz);
299  }
300 }
301 
303  SCOPED_TIME_STAT(&stats_);
304  CHECK(col_perm_.empty());
305  if (is_identity_factorization_) return;
306 
307  // If non-zeros is non-empty, we use an hypersparse solve. Note that if
308  // non_zeros starts to be too big, we clear it and thus switch back to a
309  // normal sparse solve.
310  upper_.ComputeRowsToConsiderInSortedOrder(&x->non_zeros, 0.1, 0.2);
311  x->non_zeros_are_sorted = true;
312  if (x->non_zeros.empty()) {
313  transpose_upper_.TransposeLowerSolve(&x->values);
314  } else {
316  &x->values, &x->non_zeros);
317  }
318 }
319 
321  ScatteredRow* y, ScatteredColumn* result_before_permutation) const {
322  SCOPED_TIME_STAT(&stats_);
323  if (is_identity_factorization_) {
324  // It is not advantageous to fill result_before_permutation in this case.
325  return false;
326  }
327  DenseColumn* const x = reinterpret_cast<DenseColumn*>(&y->values);
328  std::vector<RowIndex>* nz = reinterpret_cast<RowIndexVector*>(&y->non_zeros);
329 
330  // Hypersparse?
331  transpose_lower_.ComputeRowsToConsiderInSortedOrder(nz);
332  y->non_zeros_are_sorted = true;
333  if (nz->empty()) {
334  lower_.TransposeLowerSolve(x);
335  } else {
337  }
338 
339  if (result_before_permutation == nullptr) {
340  // Note(user): For the behavior of the two functions to be exactly the same,
341  // we need the positions listed in nz to be the "exact" non-zeros of x. This
342  // should be the case because the hyper-sparse functions makes sure of that.
343  // We also DCHECK() this below.
344  if (nz->empty()) {
345  PermuteWithScratchpad(inverse_row_perm_, &dense_zero_scratchpad_, x);
346  } else {
347  PermuteWithKnownNonZeros(inverse_row_perm_, &dense_zero_scratchpad_, x,
348  nz);
349  }
350  if (DEBUG_MODE) {
351  for (const RowIndex row : *nz) {
352  DCHECK_NE((*x)[row], 0.0);
353  }
354  }
355  return false;
356  }
357 
358  // This computes the same thing as in the other branch but also keeps the
359  // original x in result_before_permutation. Because of this, it is faster to
360  // use a different algorithm.
361  ClearAndResizeVectorWithNonZeros(x->size(), result_before_permutation);
362  x->swap(result_before_permutation->values);
363  if (nz->empty()) {
364  for (RowIndex row(0); row < inverse_row_perm_.size(); ++row) {
365  const Fractional value = (*result_before_permutation)[row];
366  if (value != 0.0) {
367  const RowIndex permuted_row = inverse_row_perm_[row];
368  (*x)[permuted_row] = value;
369  }
370  }
371  } else {
372  nz->swap(result_before_permutation->non_zeros);
373  nz->reserve(result_before_permutation->non_zeros.size());
374  for (const RowIndex row : result_before_permutation->non_zeros) {
375  const Fractional value = (*result_before_permutation)[row];
376  const RowIndex permuted_row = inverse_row_perm_[row];
377  (*x)[permuted_row] = value;
378  nz->push_back(permuted_row);
379  }
380  y->non_zeros_are_sorted = false;
381  }
382  return true;
383 }
384 
386  LeftSolveLWithNonZeros(y, nullptr);
387 }
388 
390  ScatteredRow* y) const {
391  SCOPED_TIME_STAT(&stats_);
392  DCHECK(IsAllZero(y->values));
393  DCHECK(y->non_zeros.empty());
394  if (is_identity_factorization_) {
395  (*y)[col] = 1.0;
396  y->non_zeros.push_back(col);
397  return col;
398  }
399  const ColIndex permuted_col = col_perm_.empty() ? col : col_perm_[col];
400  (*y)[permuted_col] = 1.0;
401  y->non_zeros.push_back(permuted_col);
402 
403  // Using the transposed matrix here is faster (even accounting the time to
404  // construct it). Note the small optimization in case the inversion is
405  // trivial.
406  if (transpose_upper_.ColumnIsDiagonalOnly(permuted_col)) {
407  (*y)[permuted_col] /= transpose_upper_.GetDiagonalCoefficient(permuted_col);
408  } else {
409  RowIndexVector* const nz = reinterpret_cast<RowIndexVector*>(&y->non_zeros);
410  DenseColumn* const x = reinterpret_cast<DenseColumn*>(&y->values);
411  transpose_upper_.ComputeRowsToConsiderInSortedOrder(nz);
412  y->non_zeros_are_sorted = true;
413  if (y->non_zeros.empty()) {
414  transpose_upper_.LowerSolveStartingAt(permuted_col, x);
415  } else {
416  transpose_upper_.HyperSparseSolve(x, nz);
417  }
418  }
419  return permuted_col;
420 }
421 
423  if (is_identity_factorization_) {
424  column_of_upper_.Clear();
425  column_of_upper_.SetCoefficient(ColToRowIndex(col), 1.0);
426  return column_of_upper_;
427  }
428  upper_.CopyColumnToSparseColumn(col_perm_.empty() ? col : col_perm_[col],
429  &column_of_upper_);
430  return column_of_upper_;
431 }
432 
434  const CompactSparseMatrixView& matrix) const {
435  const int initial_num_entries = matrix.num_entries().value();
436  const int lu_num_entries =
437  (lower_.num_entries() + upper_.num_entries()).value();
438  if (is_identity_factorization_ || initial_num_entries == 0) return 1.0;
439  return static_cast<double>(lu_num_entries) /
440  static_cast<double>(initial_num_entries);
441 }
442 
444  return is_identity_factorization_
445  ? EntryIndex(0)
446  : lower_.num_entries() + upper_.num_entries();
447 }
448 
450  if (is_identity_factorization_) return 1.0;
451  DCHECK_EQ(upper_.num_rows().value(), upper_.num_cols().value());
452  Fractional product(1.0);
453  for (ColIndex col(0); col < upper_.num_cols(); ++col) {
454  product *= upper_.GetDiagonalCoefficient(col);
455  }
456  return product * row_perm_.ComputeSignature() *
457  inverse_col_perm_.ComputeSignature();
458 }
459 
461  if (is_identity_factorization_) return 1.0;
462  const RowIndex num_rows = lower_.num_rows();
463  const ColIndex num_cols = lower_.num_cols();
464  Fractional norm = 0.0;
465  for (ColIndex col(0); col < num_cols; ++col) {
466  DenseColumn right_hand_side(num_rows, 0.0);
467  right_hand_side[ColToRowIndex(col)] = 1.0;
468  // Get a column of the matrix inverse.
469  RightSolve(&right_hand_side);
470  Fractional column_norm = 0.0;
471  // Compute sum_i |basis_matrix_ij|.
472  for (RowIndex row(0); row < num_rows; ++row) {
473  column_norm += std::abs(right_hand_side[row]);
474  }
475  // Compute max_j sum_i |basis_matrix_ij|
476  norm = std::max(norm, column_norm);
477  }
478  return norm;
479 }
480 
482  if (is_identity_factorization_) return 1.0;
483  const RowIndex num_rows = lower_.num_rows();
484  const ColIndex num_cols = lower_.num_cols();
485  DenseColumn row_sum(num_rows, 0.0);
486  for (ColIndex col(0); col < num_cols; ++col) {
487  DenseColumn right_hand_side(num_rows, 0.0);
488  right_hand_side[ColToRowIndex(col)] = 1.0;
489  // Get a column of the matrix inverse.
490  RightSolve(&right_hand_side);
491  // Compute sum_j |basis_matrix_ij|.
492  for (RowIndex row(0); row < num_rows; ++row) {
493  row_sum[row] += std::abs(right_hand_side[row]);
494  }
495  }
496  // Compute max_i sum_j |basis_matrix_ij|
497  Fractional norm = 0.0;
498  for (RowIndex row(0); row < num_rows; ++row) {
499  norm = std::max(norm, row_sum[row]);
500  }
501  return norm;
502 }
503 
505  const CompactSparseMatrixView& matrix) const {
506  if (is_identity_factorization_) return 1.0;
507  return matrix.ComputeOneNorm() * ComputeInverseOneNorm();
508 }
509 
511  const CompactSparseMatrixView& matrix) const {
512  if (is_identity_factorization_) return 1.0;
514 }
515 
517  return lower_.ComputeInverseInfinityNormUpperBound() *
519 }
520 
521 namespace {
522 // Returns the density of the sparse column 'b' w.r.t. the given permutation.
523 double ComputeDensity(const SparseColumn& b, const RowPermutation& row_perm) {
524  double density = 0.0;
525  for (const SparseColumn::Entry e : b) {
526  if (row_perm[e.row()] != kNonPivotal && e.coefficient() != 0.0) {
527  ++density;
528  }
529  }
530  const RowIndex num_rows = row_perm.size();
531  return density / num_rows.value();
532 }
533 } // anonymous namespace
534 
535 void LuFactorization::ComputeTransposeUpper() {
536  SCOPED_TIME_STAT(&stats_);
537  transpose_upper_.PopulateFromTranspose(upper_);
538 }
539 
540 void LuFactorization::ComputeTransposeLower() const {
541  SCOPED_TIME_STAT(&stats_);
542  transpose_lower_.PopulateFromTranspose(lower_);
543 }
544 
545 bool LuFactorization::CheckFactorization(const CompactSparseMatrixView& matrix,
546  Fractional tolerance) const {
547  if (is_identity_factorization_) return true;
548  SparseMatrix lu;
550  SparseMatrix paq;
551  paq.PopulateFromPermutedMatrix(matrix, row_perm_, inverse_col_perm_);
552  if (!row_perm_.Check()) {
553  return false;
554  }
555  if (!inverse_col_perm_.Check()) {
556  return false;
557  }
558 
559  SparseMatrix should_be_zero;
560  should_be_zero.PopulateFromLinearCombination(Fractional(1.0), paq,
561  Fractional(-1.0), lu);
562 
563  for (ColIndex col(0); col < should_be_zero.num_cols(); ++col) {
564  for (const SparseColumn::Entry e : should_be_zero.column(col)) {
565  const Fractional magnitude = std::abs(e.coefficient());
566  if (magnitude > tolerance) {
567  VLOG(2) << magnitude << " != 0, at column " << col;
568  return false;
569  }
570  }
571  }
572  return true;
573 }
574 
575 } // namespace glop
576 } // namespace operations_research
int64 min
Definition: alldiff_cst.cc:138
int64 max
Definition: alldiff_cst.cc:139
#define CHECK(condition)
Definition: base/logging.h:495
#define DCHECK_NE(val1, val2)
Definition: base/logging.h:886
#define DCHECK(condition)
Definition: base/logging.h:884
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
#define VLOG(verboselevel)
Definition: base/logging.h:978
void swap(StrongVector &x)
void LeftSolveUWithNonZeros(ScatteredRow *y) const
const SparseColumn & GetColumnOfU(ColIndex col) const
void RightSolveLForColumnView(const ColumnView &b, ScatteredColumn *x) const
void RightSolveLWithPermutedInput(const DenseColumn &a, ScatteredColumn *x) const
double GetFillInPercentage(const CompactSparseMatrixView &matrix) const
Fractional RightSolveSquaredNorm(const ColumnView &a) const
void RightSolveUWithNonZeros(ScatteredColumn *x) const
bool LeftSolveLWithNonZeros(ScatteredRow *y, ScatteredColumn *result_before_permutation) const
ColIndex LeftSolveUForUnitRow(ColIndex col, ScatteredRow *y) const
Fractional DualEdgeSquaredNorm(RowIndex row) const
void RightSolveLForScatteredColumn(const ScatteredColumn &b, ScatteredColumn *x) const
void RightSolveLWithNonZeros(ScatteredColumn *x) const
Fractional ComputeInfinityNormConditionNumber(const CompactSparseMatrixView &matrix) const
void ComputeLowerTimesUpper(SparseMatrix *product) const
ABSL_MUST_USE_RESULT Status ComputeFactorization(const CompactSparseMatrixView &compact_matrix)
Fractional ComputeOneNormConditionNumber(const CompactSparseMatrixView &matrix) const
ABSL_MUST_USE_RESULT Status ComputeLU(const CompactSparseMatrixView &basis_matrix, RowPermutation *row_perm, ColumnPermutation *col_perm, TriangularMatrix *lower, TriangularMatrix *upper)
Definition: markowitz.cc:143
void PopulateFromInverse(const Permutation &inverse)
Definition: sparse_column.h:28
void SetCoefficient(Index index, Fractional value)
static const Status OK()
Definition: status.h:54
void TransposeHyperSparseSolve(DenseColumn *rhs, RowIndexVector *non_zero_rows) const
Definition: sparse.cc:930
void UpperSolve(DenseColumn *rhs) const
Definition: sparse.cc:770
void HyperSparseSolve(DenseColumn *rhs, RowIndexVector *non_zero_rows) const
Definition: sparse.cc:869
Fractional GetDiagonalCoefficient(ColIndex col) const
Definition: sparse.h:572
void LowerSolve(DenseColumn *rhs) const
Definition: sparse.cc:737
void TransposeHyperSparseSolveWithReversedNonZeros(DenseColumn *rhs, RowIndexVector *non_zero_rows) const
Definition: sparse.cc:960
void LowerSolveStartingAt(ColIndex start, DenseColumn *rhs) const
Definition: sparse.cc:741
void PopulateFromTranspose(const TriangularMatrix &input)
Definition: sparse.cc:491
void CopyColumnToSparseColumn(ColIndex col, SparseColumn *output) const
Definition: sparse.cc:720
void ComputeRowsToConsiderInSortedOrder(RowIndexVector *non_zero_rows, Fractional sparsity_ratio, Fractional num_ops_ratio) const
Definition: sparse.cc:1314
void TransposeLowerSolve(DenseColumn *rhs) const
Definition: sparse.cc:831
void TransposeUpperSolve(DenseColumn *rhs) const
Definition: sparse.cc:801
Fractional ComputeInverseInfinityNormUpperBound() const
Definition: sparse.cc:1357
void Reset(RowIndex num_rows, ColIndex col_capacity)
Definition: sparse.cc:524
bool ColumnIsDiagonalOnly(ColIndex col) const
Definition: sparse.h:577
void HyperSparseSolveWithReversedNonZeros(DenseColumn *rhs, RowIndexVector *non_zero_rows) const
Definition: sparse.cc:899
int64 value
const bool DEBUG_MODE
Definition: macros.h:24
ColIndex col
Definition: markowitz.cc:176
RowIndex row
Definition: markowitz.cc:175
void PermuteWithScratchpad(const Permutation< PermutationIndexType > &permutation, StrictITIVector< IndexType, Fractional > *zero_scratchpad, StrictITIVector< IndexType, Fractional > *input_output)
Fractional Square(Fractional f)
Fractional SquaredNorm(const SparseColumn &v)
void ApplyInversePermutation(const Permutation< IndexType > &perm, const ITIVectorType &b, ITIVectorType *result)
bool IsAllZero(const Container &input)
void PermuteWithKnownNonZeros(const Permutation< IndexType > &permutation, StrictITIVector< IndexType, Fractional > *zero_scratchpad, StrictITIVector< IndexType, Fractional > *output, std::vector< IndexType > *non_zeros)
ColIndex RowToColIndex(RowIndex row)
Definition: lp_types.h:48
void ClearAndResizeVectorWithNonZeros(IndexType size, ScatteredRowOrCol *v)
RowIndex ColToRowIndex(ColIndex col)
Definition: lp_types.h:51
const RowIndex kNonPivotal(-1)
std::vector< RowIndex > RowIndexVector
Definition: lp_types.h:309
void ApplyPermutation(const Permutation< IndexType > &perm, const ITIVectorType &b, ITIVectorType *result)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
#define IF_STATS_ENABLED(instructions)
Definition: stats.h:437
#define SCOPED_TIME_STAT(stats)
Definition: stats.h:438
#define GLOP_RETURN_IF_ERROR(function_call)
Definition: status.h:70
#define GLOP_RETURN_AND_LOG_ERROR(error_code, message)
Definition: status.h:77
StrictITIVector< Index, Fractional > values