Lines Matching defs:basis
197 /// basis transform, and then return the sample value. If the tableau becomes
201 /// Let the basis unknowns be y = (y_1, ... y_n).
251 /// y_1, ... y_n are the other basis unknowns.
255 /// Note that this constraint must always hold, independent of the basis,
258 /// different basis.
391 /// y_1, ... y_n are the other basis unknowns.
614 // On return, the basis as a set is preserved but not the internal
716 // of the basis transform. The sample value of the row must be non-positive.
720 // basis unknown. The row can be represented as (s + c_1*u_1 + ... + c_n*u_n)/d,
721 // where d is the denominator, s is the sample value and the c_i are the basis
722 // coefficients. If s != 0, then since any feasible assignment of the basis
734 // y = (y_1, ... y_n) be the current basis, and
737 // of only describing the transform to get back the non-basis unknowns, it
738 // defines the values of all the unknowns in terms of the basis unknowns.
745 // the n variables cannot be spanned without using all the n basis unknowns.
747 // Consider a pivot where z_i replaces y_j in the basis. Recall the pivot
1140 SmallVector<int, 8> basis;
1141 basis.reserve(colUnknown.size());
1144 basis.emplace_back(index);
1146 savedBases.emplace_back(std::move(basis));
1183 // would result in an invalid basis.
1212 // would result in an invalid basis.
1218 // end by restoring the exact basis that was present at the time of the
1243 // be part of the basis.
1263 SmallVector<int, 8> basis = std::move(savedBases.back());
1266 for (int index : basis) {
1274 if (llvm::is_contained(basis, colUnknown[col]))
1647 /// some operations needed for generalized basis reduction. In what follows,
1713 // orientation because the column unknowns should form a basis and hence
1773 /// Reduce the basis to try and find a direction in which the polytope is
1780 /// Let b_{level}, b_{level + 1}, ... b_n be the current basis.
1816 /// decrement i, resulting in the basis
1828 void Simplex::reduceBasis(IntMatrix &basis, unsigned level) {
1831 if (level == basis.getNumRows() - 1)
1861 basis.addToRow(i, i + 1, u);
1867 // Initially u is floor(dual) and basis reflects this.
1869 basis.getRow(i + 1), candidateDual[0], candidateDualDenom[0]);
1873 basis.addToRow(i, i + 1, 1);
1875 basis.getRow(i + 1), candidateDual[1], candidateDualDenom[1]);
1880 basis.addToRow(i, i + 1, -1);
1891 basis.getRow(i + 1), DynamicAPInt(-1), basis.getRow(i))) >=
1896 basis.getRow(i + 1), DynamicAPInt(+1), basis.getRow(i))) >=
1907 // LHS. (note: the basis has already been updated, so b_{i+1} + dual*b_i in
1908 // the above expression is equal to basis.getRow(i+1) below.)
1909 assert(gbrSimplex.computeWidth(basis.getRow(i + 1)) ==
1917 while (i < basis.getNumRows() - 1) {
1931 gbrSimplex.computeWidthAndDuals(basis.getRow(i), dual, dualDenom));
1938 gbrSimplex.addEqualityForDirection(basis.getRow(i));
1939 width.emplace_back(gbrSimplex.computeWidthAndDuals(basis.getRow(i + 1),
1947 basis.swapRows(i, i + 1);
1964 gbrSimplex.addEqualityForDirection(basis.getRow(i));
1971 /// Each row in the basis matrix is a vector, and the set of basis vectors
1973 /// i.e., the basis vectors are just the variables.
1975 /// In every level, a value is assigned to the level-th basis vector, as
1980 /// If the range has multiple values, perform generalized basis reduction via
2002 IntMatrix basis = IntMatrix::identity(nDims);
2009 // The next value to try constraining the basis vector to at each level.
2012 snapshotStack.reserve(basis.getNumRows());
2013 upperBoundStack.reserve(basis.getNumRows());
2014 nextValueStack.reserve(basis.getNumRows());
2016 if (level == basis.getNumRows()) {
2029 // generalized basis reduction.
2031 llvm::to_vector<8>(basis.getRow(level));
2058 reduceBasis(basis, level);
2059 basisCoeffs = llvm::to_vector<8>(basis.getRow(level));
2095 SmallVector<DynamicAPInt, 8> basisCoeffs(basis.getRow(level).begin(),
2096 basis.getRow(level).end());