Matrix.cpp | Explore in Territory

//===- Matrix.cpp - MLIR Matrix Class -------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#include "mlir/Analysis/Presburger/Matrix.h"
#include "mlir/Analysis/Presburger/Fraction.h"
#include "mlir/Analysis/Presburger/Utils.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <utility>

usingnamespacemlir;
usingnamespacepresburger;

template <typename T>
Matrix<T>::Matrix(unsigned rows, unsigned columns, unsigned reservedRows,
                  unsigned reservedColumns)
    : … { … }

/// We cannot use the default implementation of operator== as it compares
/// fields like `reservedColumns` etc., which are not part of the data.
template <typename T>
bool Matrix<T>::operator==(const Matrix<T> &m) const { … }

template <typename T>
Matrix<T> Matrix<T>::identity(unsigned dimension) { … }

template <typename T>
unsigned Matrix<T>::getNumReservedRows() const { … }

template <typename T>
void Matrix<T>::reserveRows(unsigned rows) { … }

template <typename T>
unsigned Matrix<T>::appendExtraRow() { … }

template <typename T>
unsigned Matrix<T>::appendExtraRow(ArrayRef<T> elems) { … }

template <typename T>
Matrix<T> Matrix<T>::transpose() const { … }

template <typename T>
void Matrix<T>::resizeHorizontally(unsigned newNColumns) { … }

template <typename T>
void Matrix<T>::resize(unsigned newNRows, unsigned newNColumns) { … }

template <typename T>
void Matrix<T>::resizeVertically(unsigned newNRows) { … }

template <typename T>
void Matrix<T>::swapRows(unsigned row, unsigned otherRow) { … }

template <typename T>
void Matrix<T>::swapColumns(unsigned column, unsigned otherColumn) { … }

template <typename T>
MutableArrayRef<T> Matrix<T>::getRow(unsigned row) { … }

template <typename T>
ArrayRef<T> Matrix<T>::getRow(unsigned row) const { … }

template <typename T>
void Matrix<T>::setRow(unsigned row, ArrayRef<T> elems) { … }

template <typename T>
void Matrix<T>::insertColumn(unsigned pos) { … }
template <typename T>
void Matrix<T>::insertColumns(unsigned pos, unsigned count) { … }

template <typename T>
void Matrix<T>::removeColumn(unsigned pos) { … }
template <typename T>
void Matrix<T>::removeColumns(unsigned pos, unsigned count) { … }

template <typename T>
void Matrix<T>::insertRow(unsigned pos) { … }
template <typename T>
void Matrix<T>::insertRows(unsigned pos, unsigned count) { … }

template <typename T>
void Matrix<T>::removeRow(unsigned pos) { … }
template <typename T>
void Matrix<T>::removeRows(unsigned pos, unsigned count) { … }

template <typename T>
void Matrix<T>::copyRow(unsigned sourceRow, unsigned targetRow) { … }

template <typename T>
void Matrix<T>::fillRow(unsigned row, const T &value) { … }

// moveColumns is implemented by moving the columns adjacent to the source range
// to their final position. When moving right (i.e. dstPos > srcPos), the range
// of the adjacent columns is [srcPos + num, dstPos + num). When moving left
// (i.e. dstPos < srcPos) the range of the adjacent columns is [dstPos, srcPos).
// First, zeroed out columns are inserted in the final positions of the adjacent
// columns. Then, the adjacent columns are moved to their final positions by
// swapping them with the zeroed columns. Finally, the now zeroed adjacent
// columns are deleted.
template <typename T>
void Matrix<T>::moveColumns(unsigned srcPos, unsigned num, unsigned dstPos) { … }

template <typename T>
void Matrix<T>::addToRow(unsigned sourceRow, unsigned targetRow,
                         const T &scale) { … }

template <typename T>
void Matrix<T>::addToRow(unsigned row, ArrayRef<T> rowVec, const T &scale) { … }

template <typename T>
void Matrix<T>::scaleRow(unsigned row, const T &scale) { … }

template <typename T>
void Matrix<T>::addToColumn(unsigned sourceColumn, unsigned targetColumn,
                            const T &scale) { … }

template <typename T>
void Matrix<T>::negateColumn(unsigned column) { … }

template <typename T>
void Matrix<T>::negateRow(unsigned row) { … }

template <typename T>
void Matrix<T>::negateMatrix() { … }

template <typename T>
SmallVector<T, 8> Matrix<T>::preMultiplyWithRow(ArrayRef<T> rowVec) const { … }

template <typename T>
SmallVector<T, 8> Matrix<T>::postMultiplyWithColumn(ArrayRef<T> colVec) const { … }

/// Set M(row, targetCol) to its remainder on division by M(row, sourceCol)
/// by subtracting from column targetCol an appropriate integer multiple of
/// sourceCol. This brings M(row, targetCol) to the range [0, M(row,
/// sourceCol)). Apply the same column operation to otherMatrix, with the same
/// integer multiple.
static void modEntryColumnOperation(Matrix<DynamicAPInt> &m, unsigned row,
                                    unsigned sourceCol, unsigned targetCol,
                                    Matrix<DynamicAPInt> &otherMatrix) { … }

template <typename T>
Matrix<T> Matrix<T>::getSubMatrix(unsigned fromRow, unsigned toRow,
                                  unsigned fromColumn,
                                  unsigned toColumn) const { … }

template <typename T>
void Matrix<T>::print(raw_ostream &os) const { … }

/// We iterate over the `indicator` bitset, checking each bit. If a bit is 1,
/// we append it to one matrix, and if it is zero, we append it to the other.
template <typename T>
std::pair<Matrix<T>, Matrix<T>>
Matrix<T>::splitByBitset(ArrayRef<int> indicator) { … }

template <typename T>
void Matrix<T>::dump() const { … }

template <typename T>
bool Matrix<T>::hasConsistentState() const { … }

namespace mlir {
namespace presburger {
template class Matrix<DynamicAPInt>;
template class Matrix<Fraction>;
} // namespace presburger
} // namespace mlir

IntMatrix IntMatrix::identity(unsigned dimension) { … }

std::pair<IntMatrix, IntMatrix> IntMatrix::computeHermiteNormalForm() const { … }

DynamicAPInt IntMatrix::normalizeRow(unsigned row, unsigned cols) { … }

DynamicAPInt IntMatrix::normalizeRow(unsigned row) { … }

DynamicAPInt IntMatrix::determinant(IntMatrix *inverse) const { … }

FracMatrix FracMatrix::identity(unsigned dimension) { … }

FracMatrix::FracMatrix(IntMatrix m)
    : … { … }

Fraction FracMatrix::determinant(FracMatrix *inverse) const { … }

FracMatrix FracMatrix::gramSchmidt() const { … }

// Convert the matrix, interpreted (row-wise) as a basis
// to an LLL-reduced basis.
//
// This is an implementation of the algorithm described in
// "Factoring polynomials with rational coefficients" by
// A. K. Lenstra, H. W. Lenstra Jr., L. Lovasz.
//
// Let {b_1,  ..., b_n}  be the current basis and
//     {b_1*, ..., b_n*} be the Gram-Schmidt orthogonalised
//                          basis (unnormalized).
// Define the Gram-Schmidt coefficients μ_ij as
// (b_i • b_j*) / (b_j* • b_j*), where (•) represents the inner product.
//
// We iterate starting from the second row to the last row.
//
// For the kth row, we first check μ_kj for all rows j < k.
// We subtract b_j (scaled by the integer nearest to μ_kj)
// from b_k.
//
// Now, we update k.
// If b_k and b_{k-1} satisfy the Lovasz condition
//    |b_k|^2 ≥ (δ - μ_k{k-1}^2) |b_{k-1}|^2,
// we are done and we increment k.
// Otherwise, we swap b_k and b_{k-1} and decrement k.
//
// We repeat this until k = n and return.
void FracMatrix::LLL(Fraction delta) { … }

IntMatrix FracMatrix::normalizeRows() const { … }
llvm/mlir/lib/Analysis/Presburger/Matrix.cpp
