MLIR  19.0.0git
Matrix.h
Go to the documentation of this file.
1 //===- Matrix.h - MLIR Matrix Class -----------------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This is a simple 2D matrix class that supports reading, writing, resizing,
10 // swapping rows, and swapping columns. It can hold integers (MPInt) or rational
11 // numbers (Fraction).
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef MLIR_ANALYSIS_PRESBURGER_MATRIX_H
16 #define MLIR_ANALYSIS_PRESBURGER_MATRIX_H
17 
19 #include "mlir/Support/LLVM.h"
20 #include "llvm/ADT/ArrayRef.h"
21 #include "llvm/Support/raw_ostream.h"
22 
23 #include <bitset>
24 #include <cassert>
25 
26 namespace mlir {
27 namespace presburger {
28 
29 /// This is a class to represent a resizable matrix.
30 ///
31 /// More columns and rows can be reserved than are currently used. The data is
32 /// stored as a single 1D array, viewed as a 2D matrix with nRows rows and
33 /// nReservedColumns columns, stored in row major form. Thus the element at
34 /// (i, j) is stored at data[i*nReservedColumns + j]. The reserved but unused
35 /// columns always have all zero values. The reserved rows are just reserved
36 /// space in the underlying SmallVector's capacity.
37 /// This class only works for the types MPInt and Fraction, since the method
38 /// implementations are in the Matrix.cpp file. Only these two types have
39 /// been explicitly instantiated there.
40 template <typename T>
41 class Matrix {
42  static_assert(std::is_same_v<T, MPInt> || std::is_same_v<T, Fraction>,
43  "T must be MPInt or Fraction.");
44 
45 public:
46  Matrix() = delete;
47 
48  /// Construct a matrix with the specified number of rows and columns.
49  /// The number of reserved rows and columns will be at least the number
50  /// specified, and will always be sufficient to accomodate the number of rows
51  /// and columns specified.
52  ///
53  /// Initially, the entries are initialized to ero.
54  Matrix(unsigned rows, unsigned columns, unsigned reservedRows = 0,
55  unsigned reservedColumns = 0);
56 
57  /// Return the identity matrix of the specified dimension.
58  static Matrix identity(unsigned dimension);
59 
60  /// Access the element at the specified row and column.
61  T &at(unsigned row, unsigned column) {
62  assert(row < nRows && "Row outside of range");
63  assert(column < nColumns && "Column outside of range");
64  return data[row * nReservedColumns + column];
65  }
66 
67  T at(unsigned row, unsigned column) const {
68  assert(row < nRows && "Row outside of range");
69  assert(column < nColumns && "Column outside of range");
70  return data[row * nReservedColumns + column];
71  }
72 
73  T &operator()(unsigned row, unsigned column) { return at(row, column); }
74 
75  T operator()(unsigned row, unsigned column) const { return at(row, column); }
76 
77  bool operator==(const Matrix<T> &m) const;
78 
79  /// Swap the given columns.
80  void swapColumns(unsigned column, unsigned otherColumn);
81 
82  /// Swap the given rows.
83  void swapRows(unsigned row, unsigned otherRow);
84 
85  unsigned getNumRows() const { return nRows; }
86 
87  unsigned getNumColumns() const { return nColumns; }
88 
89  /// Return the maximum number of rows/columns that can be added without
90  /// incurring a reallocation.
91  unsigned getNumReservedRows() const;
92  unsigned getNumReservedColumns() const { return nReservedColumns; }
93 
94  /// Reserve enough space to resize to the specified number of rows without
95  /// reallocations.
96  void reserveRows(unsigned rows);
97 
98  /// Get a [Mutable]ArrayRef corresponding to the specified row.
99  MutableArrayRef<T> getRow(unsigned row);
100  ArrayRef<T> getRow(unsigned row) const;
101 
102  /// Set the specified row to `elems`.
103  void setRow(unsigned row, ArrayRef<T> elems);
104 
105  /// Insert columns having positions pos, pos + 1, ... pos + count - 1.
106  /// Columns that were at positions 0 to pos - 1 will stay where they are;
107  /// columns that were at positions pos to nColumns - 1 will be pushed to the
108  /// right. pos should be at most nColumns.
109  void insertColumns(unsigned pos, unsigned count);
110  void insertColumn(unsigned pos);
111 
112  /// Insert rows having positions pos, pos + 1, ... pos + count - 1.
113  /// Rows that were at positions 0 to pos - 1 will stay where they are;
114  /// rows that were at positions pos to nColumns - 1 will be pushed to the
115  /// right. pos should be at most nRows.
116  void insertRows(unsigned pos, unsigned count);
117  void insertRow(unsigned pos);
118 
119  /// Remove the columns having positions pos, pos + 1, ... pos + count - 1.
120  /// Rows that were at positions 0 to pos - 1 will stay where they are;
121  /// columns that were at positions pos + count - 1 or later will be pushed to
122  /// the right. The columns to be deleted must be valid rows: pos + count - 1
123  /// must be at most nColumns - 1.
124  void removeColumns(unsigned pos, unsigned count);
125  void removeColumn(unsigned pos);
126 
127  /// Remove the rows having positions pos, pos + 1, ... pos + count - 1.
128  /// Rows that were at positions 0 to pos - 1 will stay where they are;
129  /// rows that were at positions pos + count - 1 or later will be pushed to the
130  /// right. The rows to be deleted must be valid rows: pos + count - 1 must be
131  /// at most nRows - 1.
132  void removeRows(unsigned pos, unsigned count);
133  void removeRow(unsigned pos);
134 
135  void copyRow(unsigned sourceRow, unsigned targetRow);
136 
137  void fillRow(unsigned row, const T &value);
138  void fillRow(unsigned row, int64_t value) { fillRow(row, T(value)); }
139 
140  /// Add `scale` multiples of the source row to the target row.
141  void addToRow(unsigned sourceRow, unsigned targetRow, const T &scale);
142  void addToRow(unsigned sourceRow, unsigned targetRow, int64_t scale) {
143  addToRow(sourceRow, targetRow, T(scale));
144  }
145  /// Add `scale` multiples of the rowVec row to the specified row.
146  void addToRow(unsigned row, ArrayRef<T> rowVec, const T &scale);
147 
148  /// Multiply the specified row by a factor of `scale`.
149  void scaleRow(unsigned row, const T &scale);
150 
151  /// Add `scale` multiples of the source column to the target column.
152  void addToColumn(unsigned sourceColumn, unsigned targetColumn,
153  const T &scale);
154  void addToColumn(unsigned sourceColumn, unsigned targetColumn,
155  int64_t scale) {
156  addToColumn(sourceColumn, targetColumn, T(scale));
157  }
158 
159  /// Negate the specified column.
160  void negateColumn(unsigned column);
161 
162  /// Negate the specified row.
163  void negateRow(unsigned row);
164 
165  /// Negate the entire matrix.
166  void negateMatrix();
167 
168  /// The given vector is interpreted as a row vector v. Post-multiply v with
169  /// this matrix, say M, and return vM.
171 
172  /// The given vector is interpreted as a column vector v. Pre-multiply v with
173  /// this matrix, say M, and return Mv.
175 
176  /// Resize the matrix to the specified dimensions. If a dimension is smaller,
177  /// the values are truncated; if it is bigger, the new values are initialized
178  /// to zero.
179  ///
180  /// Due to the representation of the matrix, resizing vertically (adding rows)
181  /// is less expensive than increasing the number of columns beyond
182  /// nReservedColumns.
183  void resize(unsigned newNRows, unsigned newNColumns);
184  void resizeHorizontally(unsigned newNColumns);
185  void resizeVertically(unsigned newNRows);
186 
187  /// Add an extra row at the bottom of the matrix and return its position.
188  unsigned appendExtraRow();
189  /// Same as above, but copy the given elements into the row. The length of
190  /// `elems` must be equal to the number of columns.
191  unsigned appendExtraRow(ArrayRef<T> elems);
192 
193  // Transpose the matrix without modifying it.
194  Matrix<T> transpose() const;
195 
196  // Copy the cells in the intersection of
197  // the rows between `fromRows` and `toRows` and
198  // the columns between `fromColumns` and `toColumns`, both inclusive.
199  Matrix<T> getSubMatrix(unsigned fromRow, unsigned toRow, unsigned fromColumn,
200  unsigned toColumn) const;
201 
202  /// Split the rows of a matrix into two matrices according to which bits are
203  /// 1 and which are 0 in a given bitset.
204  ///
205  /// The first matrix returned has the rows corresponding to 1 and the second
206  /// corresponding to 2.
207  std::pair<Matrix<T>, Matrix<T>> splitByBitset(ArrayRef<int> indicator);
208 
209  /// Print the matrix.
210  void print(raw_ostream &os) const;
211  void dump() const;
212 
213  /// Return whether the Matrix is in a consistent state with all its
214  /// invariants satisfied.
215  bool hasConsistentState() const;
216 
217  /// Move the columns in the source range [srcPos, srcPos + num) to the
218  /// specified destination [dstPos, dstPos + num), while moving the columns
219  /// adjacent to the source range to the left/right of the shifted columns.
220  ///
221  /// When moving the source columns right (i.e. dstPos > srcPos), columns that
222  /// were at positions [0, srcPos) and [dstPos + num, nCols) will stay where
223  /// they are; columns that were at positions [srcPos, srcPos + num) will be
224  /// moved to [dstPos, dstPos + num); and columns that were at positions
225  /// [srcPos + num, dstPos + num) will be moved to [srcPos, dstPos).
226  /// Equivalently, the columns [srcPos + num, dstPos + num) are interchanged
227  /// with [srcPos, srcPos + num).
228  /// For example, if m = |0 1 2 3 4 5| then:
229  /// m.moveColumns(1, 3, 2) will result in m = |0 4 1 2 3 5|; or
230  /// m.moveColumns(1, 2, 4) will result in m = |0 3 4 5 1 2|.
231  ///
232  /// The left shift operation (i.e. dstPos < srcPos) works in a similar way.
233  void moveColumns(unsigned srcPos, unsigned num, unsigned dstPos);
234 
235 protected:
236  /// The current number of rows, columns, and reserved columns. The underlying
237  /// data vector is viewed as an nRows x nReservedColumns matrix, of which the
238  /// first nColumns columns are currently in use, and the remaining are
239  /// reserved columns filled with zeros.
241 
242  /// Stores the data. data.size() is equal to nRows * nReservedColumns.
243  /// data.capacity() / nReservedColumns is the number of reserved rows.
245 };
246 
247 // An inherited class for integer matrices, with no new data attributes.
248 // This is only used for the matrix-related methods which apply only
249 // to integers (hermite normal form computation and row normalisation).
250 class IntMatrix : public Matrix<MPInt> {
251 public:
252  IntMatrix(unsigned rows, unsigned columns, unsigned reservedRows = 0,
253  unsigned reservedColumns = 0)
254  : Matrix<MPInt>(rows, columns, reservedRows, reservedColumns){};
255 
256  IntMatrix(Matrix<MPInt> m) : Matrix<MPInt>(std::move(m)){};
257 
258  /// Return the identity matrix of the specified dimension.
259  static IntMatrix identity(unsigned dimension);
260 
261  /// Given the current matrix M, returns the matrices H, U such that H is the
262  /// column hermite normal form of M, i.e. H = M * U, where U is unimodular and
263  /// the matrix H has the following restrictions:
264  /// - H is lower triangular.
265  /// - The leading coefficient (the first non-zero entry from the top, called
266  /// the pivot) of a non-zero column is always strictly below of the leading
267  /// coefficient of the column before it; moreover, it is positive.
268  /// - The elements to the right of the pivots are zero and the elements to
269  /// the left of the pivots are nonnegative and strictly smaller than the
270  /// pivot.
271  std::pair<IntMatrix, IntMatrix> computeHermiteNormalForm() const;
272 
273  /// Divide the first `nCols` of the specified row by their GCD.
274  /// Returns the GCD of the first `nCols` of the specified row.
275  MPInt normalizeRow(unsigned row, unsigned nCols);
276  /// Divide the columns of the specified row by their GCD.
277  /// Returns the GCD of the columns of the specified row.
278  MPInt normalizeRow(unsigned row);
279 
280  // Compute the determinant of the matrix (cubic time).
281  // Stores the integer inverse of the matrix in the pointer
282  // passed (if any). The pointer is unchanged if the inverse
283  // does not exist, which happens iff det = 0.
284  // For a matrix M, the integer inverse is the matrix M' such that
285  // M x M' = M'  M = det(M) x I.
286  // Assert-fails if the matrix is not square.
287  MPInt determinant(IntMatrix *inverse = nullptr) const;
288 };
289 
290 // An inherited class for rational matrices, with no new data attributes.
291 // This class is for functionality that only applies to matrices of fractions.
292 class FracMatrix : public Matrix<Fraction> {
293 public:
294  FracMatrix(unsigned rows, unsigned columns, unsigned reservedRows = 0,
295  unsigned reservedColumns = 0)
296  : Matrix<Fraction>(rows, columns, reservedRows, reservedColumns){};
297 
299 
300  explicit FracMatrix(IntMatrix m);
301 
302  /// Return the identity matrix of the specified dimension.
303  static FracMatrix identity(unsigned dimension);
304 
305  // Compute the determinant of the matrix (cubic time).
306  // Stores the inverse of the matrix in the pointer
307  // passed (if any). The pointer is unchanged if the inverse
308  // does not exist, which happens iff det = 0.
309  // Assert-fails if the matrix is not square.
310  Fraction determinant(FracMatrix *inverse = nullptr) const;
311 
312  // Computes the Gram-Schmidt orthogonalisation
313  // of the rows of matrix (cubic time).
314  // The rows of the matrix must be linearly independent.
315  FracMatrix gramSchmidt() const;
316 
317  // Run LLL basis reduction on the matrix, modifying it in-place.
318  // The parameter is what [the original
319  // paper](https://www.cs.cmu.edu/~avrim/451f11/lectures/lect1129_LLL.pdf)
320  // calls `y`, usually 3/4.
321  void LLL(Fraction delta);
322 
323  // Multiply each row of the matrix by the LCM of the denominators, thereby
324  // converting it to an integer matrix.
325  IntMatrix normalizeRows() const;
326 };
327 
328 } // namespace presburger
329 } // namespace mlir
330 
331 #endif // MLIR_ANALYSIS_PRESBURGER_MATRIX_H
FracMatrix gramSchmidt() const
Definition: Matrix.cpp:672
IntMatrix normalizeRows() const
Definition: Matrix.cpp:760
static FracMatrix identity(unsigned dimension)
Return the identity matrix of the specified dimension.
Definition: Matrix.cpp:576
FracMatrix(unsigned rows, unsigned columns, unsigned reservedRows=0, unsigned reservedColumns=0)
Definition: Matrix.h:294
void LLL(Fraction delta)
Definition: Matrix.cpp:720
Fraction determinant(FracMatrix *inverse=nullptr) const
Definition: Matrix.cpp:587
FracMatrix(Matrix< Fraction > m)
Definition: Matrix.h:298
MPInt normalizeRow(unsigned row, unsigned nCols)
Divide the first nCols of the specified row by their GCD.
Definition: Matrix.cpp:545
static IntMatrix identity(unsigned dimension)
Return the identity matrix of the specified dimension.
Definition: Matrix.cpp:452
IntMatrix(Matrix< MPInt > m)
Definition: Matrix.h:256
std::pair< IntMatrix, IntMatrix > computeHermiteNormalForm() const
Given the current matrix M, returns the matrices H, U such that H is the column hermite normal form o...
Definition: Matrix.cpp:459
MPInt determinant(IntMatrix *inverse=nullptr) const
Definition: Matrix.cpp:553
IntMatrix(unsigned rows, unsigned columns, unsigned reservedRows=0, unsigned reservedColumns=0)
Definition: Matrix.h:252
This class provides support for multi-precision arithmetic.
Definition: MPInt.h:87
This is a class to represent a resizable matrix.
Definition: Matrix.h:41
void moveColumns(unsigned srcPos, unsigned num, unsigned dstPos)
Move the columns in the source range [srcPos, srcPos + num) to the specified destination [dstPos,...
Definition: Matrix.cpp:268
bool hasConsistentState() const
Return whether the Matrix is in a consistent state with all its invariants satisfied.
Definition: Matrix.cpp:431
void insertRows(unsigned pos, unsigned count)
Insert rows having positions pos, pos + 1, ...
Definition: Matrix.cpp:218
unsigned getNumRows() const
Definition: Matrix.h:85
void swapColumns(unsigned column, unsigned otherColumn)
Swap the given columns.
Definition: Matrix.cpp:122
T & operator()(unsigned row, unsigned column)
Definition: Matrix.h:73
unsigned nRows
The current number of rows, columns, and reserved columns.
Definition: Matrix.h:240
void removeColumn(unsigned pos)
Definition: Matrix.cpp:196
unsigned appendExtraRow()
Add an extra row at the bottom of the matrix and return its position.
Definition: Matrix.cpp:67
unsigned nReservedColumns
Definition: Matrix.h:240
void addToColumn(unsigned sourceColumn, unsigned targetColumn, const T &scale)
Add scale multiples of the source column to the target column.
Definition: Matrix.cpp:321
Matrix< T > getSubMatrix(unsigned fromRow, unsigned toRow, unsigned fromColumn, unsigned toColumn) const
Definition: Matrix.cpp:386
void print(raw_ostream &os) const
Print the matrix.
Definition: Matrix.cpp:402
void copyRow(unsigned sourceRow, unsigned targetRow)
Definition: Matrix.cpp:246
void scaleRow(unsigned row, const T &scale)
Multiply the specified row by a factor of scale.
Definition: Matrix.cpp:315
void insertColumn(unsigned pos)
Definition: Matrix.cpp:150
T at(unsigned row, unsigned column) const
Definition: Matrix.h:67
MutableArrayRef< T > getRow(unsigned row)
Get a [Mutable]ArrayRef corresponding to the specified row.
Definition: Matrix.cpp:132
void removeColumns(unsigned pos, unsigned count)
Remove the columns having positions pos, pos + 1, ...
Definition: Matrix.cpp:200
void addToColumn(unsigned sourceColumn, unsigned targetColumn, int64_t scale)
Definition: Matrix.h:154
void insertColumns(unsigned pos, unsigned count)
Insert columns having positions pos, pos + 1, ...
Definition: Matrix.cpp:154
void setRow(unsigned row, ArrayRef< T > elems)
Set the specified row to elems.
Definition: Matrix.cpp:142
std::pair< Matrix< T >, Matrix< T > > splitByBitset(ArrayRef< int > indicator)
Split the rows of a matrix into two matrices according to which bits are 1 and which are 0 in a given...
Definition: Matrix.cpp:414
void fillRow(unsigned row, int64_t value)
Definition: Matrix.h:138
void removeRow(unsigned pos)
Definition: Matrix.cpp:232
bool operator==(const Matrix< T > &m) const
We cannot use the default implementation of operator== as it compares fields like reservedColumns etc...
Definition: Matrix.cpp:35
SmallVector< T, 16 > data
Stores the data.
Definition: Matrix.h:244
unsigned getNumColumns() const
Definition: Matrix.h:87
void resizeVertically(unsigned newNRows)
Definition: Matrix.cpp:106
unsigned getNumReservedRows() const
Return the maximum number of rows/columns that can be added without incurring a reallocation.
Definition: Matrix.cpp:57
unsigned getNumReservedColumns() const
Definition: Matrix.h:92
Matrix< T > transpose() const
Definition: Matrix.cpp:82
SmallVector< T, 8 > preMultiplyWithRow(ArrayRef< T > rowVec) const
The given vector is interpreted as a row vector v.
Definition: Matrix.cpp:348
static Matrix identity(unsigned dimension)
Return the identity matrix of the specified dimension.
Definition: Matrix.cpp:49
void insertRow(unsigned pos)
Definition: Matrix.cpp:214
SmallVector< T, 8 > postMultiplyWithColumn(ArrayRef< T > colVec) const
The given vector is interpreted as a column vector v.
Definition: Matrix.cpp:359
void negateMatrix()
Negate the entire matrix.
Definition: Matrix.cpp:342
void swapRows(unsigned row, unsigned otherRow)
Swap the given rows.
Definition: Matrix.cpp:112
void resizeHorizontally(unsigned newNColumns)
Definition: Matrix.cpp:92
void reserveRows(unsigned rows)
Reserve enough space to resize to the specified number of rows without reallocations.
Definition: Matrix.cpp:62
void negateColumn(unsigned column)
Negate the specified column.
Definition: Matrix.cpp:330
void resize(unsigned newNRows, unsigned newNColumns)
Resize the matrix to the specified dimensions.
Definition: Matrix.cpp:100
void fillRow(unsigned row, const T &value)
Definition: Matrix.cpp:254
void addToRow(unsigned sourceRow, unsigned targetRow, const T &scale)
Add scale multiples of the source row to the target row.
Definition: Matrix.cpp:301
T operator()(unsigned row, unsigned column) const
Definition: Matrix.h:75
void negateRow(unsigned row)
Negate the specified row.
Definition: Matrix.cpp:336
T & at(unsigned row, unsigned column)
Access the element at the specified row and column.
Definition: Matrix.h:61
void addToRow(unsigned sourceRow, unsigned targetRow, int64_t scale)
Definition: Matrix.h:142
void removeRows(unsigned pos, unsigned count)
Remove the rows having positions pos, pos + 1, ...
Definition: Matrix.cpp:236
Include the generated interface declarations.
A class to represent fractions.
Definition: Fraction.h:28