mlir/unittests/Analysis/Presburger/MatrixTest.cpp

   1 //===- MatrixTest.cpp - Tests for Matrix ----------------------------------===//
   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 #include "mlir/Analysis/Presburger/Matrix.h"
  10 #include "./Utils.h"
  11 #include "mlir/Analysis/Presburger/Fraction.h"
  12 #include <gmock/gmock.h>
  13 #include <gtest/gtest.h>
  14
  15 using namespace mlir;
  16 using namespace presburger;
  17
  18 TEST(MatrixTest, ReadWrite) {
  19   IntMatrix mat(5, 5);
  20   for (unsigned row = 0; row < 5; ++row)
  21     for (unsigned col = 0; col < 5; ++col)
  22       mat(row, col) = 10 * row + col;
  23   for (unsigned row = 0; row < 5; ++row)
  24     for (unsigned col = 0; col < 5; ++col)
  25       EXPECT_EQ(mat(row, col), int(10 * row + col));
  26 }
  27
  28 TEST(MatrixTest, SwapColumns) {
  29   IntMatrix mat(5, 5);
  30   for (unsigned row = 0; row < 5; ++row)
  31     for (unsigned col = 0; col < 5; ++col)
  32       mat(row, col) = col == 3 ? 1 : 0;
  33   mat.swapColumns(3, 1);
  34   for (unsigned row = 0; row < 5; ++row)
  35     for (unsigned col = 0; col < 5; ++col)
  36       EXPECT_EQ(mat(row, col), col == 1 ? 1 : 0);
  37
  38   // swap around all the other columns, swap (1, 3) twice for no effect.
  39   mat.swapColumns(3, 1);
  40   mat.swapColumns(2, 4);
  41   mat.swapColumns(1, 3);
  42   mat.swapColumns(0, 4);
  43   mat.swapColumns(2, 2);
  44
  45   for (unsigned row = 0; row < 5; ++row)
  46     for (unsigned col = 0; col < 5; ++col)
  47       EXPECT_EQ(mat(row, col), col == 1 ? 1 : 0);
  48 }
  49
  50 TEST(MatrixTest, SwapRows) {
  51   IntMatrix mat(5, 5);
  52   for (unsigned row = 0; row < 5; ++row)
  53     for (unsigned col = 0; col < 5; ++col)
  54       mat(row, col) = row == 2 ? 1 : 0;
  55   mat.swapRows(2, 0);
  56   for (unsigned row = 0; row < 5; ++row)
  57     for (unsigned col = 0; col < 5; ++col)
  58       EXPECT_EQ(mat(row, col), row == 0 ? 1 : 0);
  59
  60   // swap around all the other rows, swap (2, 0) twice for no effect.
  61   mat.swapRows(3, 4);
  62   mat.swapRows(1, 4);
  63   mat.swapRows(2, 0);
  64   mat.swapRows(1, 1);
  65   mat.swapRows(0, 2);
  66
  67   for (unsigned row = 0; row < 5; ++row)
  68     for (unsigned col = 0; col < 5; ++col)
  69       EXPECT_EQ(mat(row, col), row == 0 ? 1 : 0);
  70 }
  71
  72 TEST(MatrixTest, resizeVertically) {
  73   IntMatrix mat(5, 5);
  74   EXPECT_EQ(mat.getNumRows(), 5u);
  75   EXPECT_EQ(mat.getNumColumns(), 5u);
  76   for (unsigned row = 0; row < 5; ++row)
  77     for (unsigned col = 0; col < 5; ++col)
  78       mat(row, col) = 10 * row + col;
  79
  80   mat.resizeVertically(3);
  81   ASSERT_TRUE(mat.hasConsistentState());
  82   EXPECT_EQ(mat.getNumRows(), 3u);
  83   EXPECT_EQ(mat.getNumColumns(), 5u);
  84   for (unsigned row = 0; row < 3; ++row)
  85     for (unsigned col = 0; col < 5; ++col)
  86       EXPECT_EQ(mat(row, col), int(10 * row + col));
  87
  88   mat.resizeVertically(5);
  89   ASSERT_TRUE(mat.hasConsistentState());
  90   EXPECT_EQ(mat.getNumRows(), 5u);
  91   EXPECT_EQ(mat.getNumColumns(), 5u);
  92   for (unsigned row = 0; row < 5; ++row)
  93     for (unsigned col = 0; col < 5; ++col)
  94       EXPECT_EQ(mat(row, col), row >= 3 ? 0 : int(10 * row + col));
  95 }
  96
  97 TEST(MatrixTest, insertColumns) {
  98   IntMatrix mat(5, 5, 5, 10);
  99   EXPECT_EQ(mat.getNumRows(), 5u);
 100   EXPECT_EQ(mat.getNumColumns(), 5u);
 101   for (unsigned row = 0; row < 5; ++row)
 102     for (unsigned col = 0; col < 5; ++col)
 103       mat(row, col) = 10 * row + col;
 104
 105   mat.insertColumns(3, 100);
 106   ASSERT_TRUE(mat.hasConsistentState());
 107   EXPECT_EQ(mat.getNumRows(), 5u);
 108   EXPECT_EQ(mat.getNumColumns(), 105u);
 109   for (unsigned row = 0; row < 5; ++row) {
 110     for (unsigned col = 0; col < 105; ++col) {
 111       if (col < 3)
 112         EXPECT_EQ(mat(row, col), int(10 * row + col));
 113       else if (3 <= col && col <= 102)
 114         EXPECT_EQ(mat(row, col), 0);
 115       else
 116         EXPECT_EQ(mat(row, col), int(10 * row + col - 100));
 117     }
 118   }
 119
 120   mat.removeColumns(3, 100);
 121   ASSERT_TRUE(mat.hasConsistentState());
 122   mat.insertColumns(0, 0);
 123   ASSERT_TRUE(mat.hasConsistentState());
 124   mat.insertColumn(5);
 125   ASSERT_TRUE(mat.hasConsistentState());
 126
 127   EXPECT_EQ(mat.getNumRows(), 5u);
 128   EXPECT_EQ(mat.getNumColumns(), 6u);
 129   for (unsigned row = 0; row < 5; ++row)
 130     for (unsigned col = 0; col < 6; ++col)
 131       EXPECT_EQ(mat(row, col), col == 5 ? 0 : 10 * row + col);
 132 }
 133
 134 TEST(MatrixTest, insertRows) {
 135   IntMatrix mat(5, 5, 5, 10);
 136   ASSERT_TRUE(mat.hasConsistentState());
 137   EXPECT_EQ(mat.getNumRows(), 5u);
 138   EXPECT_EQ(mat.getNumColumns(), 5u);
 139   for (unsigned row = 0; row < 5; ++row)
 140     for (unsigned col = 0; col < 5; ++col)
 141       mat(row, col) = 10 * row + col;
 142
 143   mat.insertRows(3, 100);
 144   ASSERT_TRUE(mat.hasConsistentState());
 145   EXPECT_EQ(mat.getNumRows(), 105u);
 146   EXPECT_EQ(mat.getNumColumns(), 5u);
 147   for (unsigned row = 0; row < 105; ++row) {
 148     for (unsigned col = 0; col < 5; ++col) {
 149       if (row < 3)
 150         EXPECT_EQ(mat(row, col), int(10 * row + col));
 151       else if (3 <= row && row <= 102)
 152         EXPECT_EQ(mat(row, col), 0);
 153       else
 154         EXPECT_EQ(mat(row, col), int(10 * (row - 100) + col));
 155     }
 156   }
 157
 158   mat.removeRows(3, 100);
 159   ASSERT_TRUE(mat.hasConsistentState());
 160   mat.insertRows(0, 0);
 161   ASSERT_TRUE(mat.hasConsistentState());
 162   mat.insertRow(5);
 163   ASSERT_TRUE(mat.hasConsistentState());
 164
 165   EXPECT_EQ(mat.getNumRows(), 6u);
 166   EXPECT_EQ(mat.getNumColumns(), 5u);
 167   for (unsigned row = 0; row < 6; ++row)
 168     for (unsigned col = 0; col < 5; ++col)
 169       EXPECT_EQ(mat(row, col), row == 5 ? 0 : 10 * row + col);
 170 }
 171
 172 TEST(MatrixTest, resize) {
 173   IntMatrix mat(5, 5);
 174   EXPECT_EQ(mat.getNumRows(), 5u);
 175   EXPECT_EQ(mat.getNumColumns(), 5u);
 176   for (unsigned row = 0; row < 5; ++row)
 177     for (unsigned col = 0; col < 5; ++col)
 178       mat(row, col) = 10 * row + col;
 179
 180   mat.resize(3, 3);
 181   ASSERT_TRUE(mat.hasConsistentState());
 182   EXPECT_EQ(mat.getNumRows(), 3u);
 183   EXPECT_EQ(mat.getNumColumns(), 3u);
 184   for (unsigned row = 0; row < 3; ++row)
 185     for (unsigned col = 0; col < 3; ++col)
 186       EXPECT_EQ(mat(row, col), int(10 * row + col));
 187
 188   mat.resize(7, 7);
 189   ASSERT_TRUE(mat.hasConsistentState());
 190   EXPECT_EQ(mat.getNumRows(), 7u);
 191   EXPECT_EQ(mat.getNumColumns(), 7u);
 192   for (unsigned row = 0; row < 7; ++row)
 193     for (unsigned col = 0; col < 7; ++col)
 194       EXPECT_EQ(mat(row, col), row >= 3 || col >= 3 ? 0 : int(10 * row + col));
 195 }
 196
 197 template <typename T>
 198 static void checkMatEqual(const Matrix<T> m1, const Matrix<T> m2) {
 199   EXPECT_EQ(m1.getNumRows(), m2.getNumRows());
 200   EXPECT_EQ(m1.getNumColumns(), m2.getNumColumns());
 201
 202   for (unsigned row = 0, rows = m1.getNumRows(); row < rows; ++row)
 203     for (unsigned col = 0, cols = m1.getNumColumns(); col < cols; ++col)
 204       EXPECT_EQ(m1(row, col), m2(row, col));
 205 }
 206
 207 static void checkHermiteNormalForm(const IntMatrix &mat,
 208                                    const IntMatrix &hermiteForm) {
 209   auto [h, u] = mat.computeHermiteNormalForm();
 210
 211   checkMatEqual(h, hermiteForm);
 212 }
 213
 214 TEST(MatrixTest, computeHermiteNormalForm) {
 215   // TODO: Add a check to test the original statement of hermite normal form
 216   // instead of using a precomputed result.
 217
 218   {
 219     // Hermite form of a unimodular matrix is the identity matrix.
 220     IntMatrix mat = makeIntMatrix(3, 3, {{2, 3, 6}, {3, 2, 3}, {17, 11, 16}});
 221     IntMatrix hermiteForm =
 222         makeIntMatrix(3, 3, {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}});
 223     checkHermiteNormalForm(mat, hermiteForm);
 224   }
 225
 226   {
 227     // Hermite form of a unimodular is the identity matrix.
 228     IntMatrix mat = makeIntMatrix(
 229         4, 4,
 230         {{-6, -1, -19, -20}, {0, 1, 0, 0}, {-5, 0, -15, -16}, {6, 0, 18, 19}});
 231     IntMatrix hermiteForm = makeIntMatrix(
 232         4, 4, {{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}});
 233     checkHermiteNormalForm(mat, hermiteForm);
 234   }
 235
 236   {
 237     IntMatrix mat = makeIntMatrix(
 238         4, 4, {{3, 3, 1, 4}, {0, 1, 0, 0}, {0, 0, 19, 16}, {0, 0, 0, 3}});
 239     IntMatrix hermiteForm = makeIntMatrix(
 240         4, 4, {{1, 0, 0, 0}, {0, 1, 0, 0}, {1, 0, 3, 0}, {18, 0, 54, 57}});
 241     checkHermiteNormalForm(mat, hermiteForm);
 242   }
 243
 244   {
 245     IntMatrix mat = makeIntMatrix(
 246         4, 4, {{3, 3, 1, 4}, {0, 1, 0, 0}, {0, 0, 19, 16}, {0, 0, 0, 3}});
 247     IntMatrix hermiteForm = makeIntMatrix(
 248         4, 4, {{1, 0, 0, 0}, {0, 1, 0, 0}, {1, 0, 3, 0}, {18, 0, 54, 57}});
 249     checkHermiteNormalForm(mat, hermiteForm);
 250   }
 251
 252   {
 253     IntMatrix mat = makeIntMatrix(
 254         3, 5, {{0, 2, 0, 7, 1}, {-1, 0, 0, -3, 0}, {0, 4, 1, 0, 8}});
 255     IntMatrix hermiteForm = makeIntMatrix(
 256         3, 5, {{1, 0, 0, 0, 0}, {0, 1, 0, 0, 0}, {0, 0, 1, 0, 0}});
 257     checkHermiteNormalForm(mat, hermiteForm);
 258   }
 259 }
 260
 261 TEST(MatrixTest, inverse) {
 262   IntMatrix mat1 = makeIntMatrix(2, 2, {{2, 1}, {7, 0}});
 263   EXPECT_EQ(mat1.determinant(), -7);
 264
 265   FracMatrix mat = makeFracMatrix(
 266       2, 2, {{Fraction(2), Fraction(1)}, {Fraction(7), Fraction(0)}});
 267   FracMatrix inverse = makeFracMatrix(
 268       2, 2, {{Fraction(0), Fraction(1, 7)}, {Fraction(1), Fraction(-2, 7)}});
 269
 270   FracMatrix inv(2, 2);
 271   mat.determinant(&inv);
 272
 273   EXPECT_EQ_FRAC_MATRIX(inv, inverse);
 274
 275   mat = makeFracMatrix(
 276       2, 2, {{Fraction(0), Fraction(1)}, {Fraction(0), Fraction(2)}});
 277   Fraction det = mat.determinant(nullptr);
 278
 279   EXPECT_EQ(det, Fraction(0));
 280
 281   mat = makeFracMatrix(3, 3,
 282                        {{Fraction(1), Fraction(2), Fraction(3)},
 283                         {Fraction(4), Fraction(8), Fraction(6)},
 284                         {Fraction(7), Fraction(8), Fraction(6)}});
 285   inverse = makeFracMatrix(3, 3,
 286                            {{Fraction(0), Fraction(-1, 3), Fraction(1, 3)},
 287                             {Fraction(-1, 2), Fraction(5, 12), Fraction(-1, 6)},
 288                             {Fraction(2, 3), Fraction(-1, 6), Fraction(0)}});
 289
 290   mat.determinant(&inv);
 291   EXPECT_EQ_FRAC_MATRIX(inv, inverse);
 292
 293   mat = makeFracMatrix(0, 0, {});
 294   mat.determinant(&inv);
 295 }
 296
 297 TEST(MatrixTest, intInverse) {
 298   IntMatrix mat = makeIntMatrix(2, 2, {{2, 1}, {7, 0}});
 299   IntMatrix inverse = makeIntMatrix(2, 2, {{0, -1}, {-7, 2}});
 300
 301   IntMatrix inv(2, 2);
 302   mat.determinant(&inv);
 303
 304   EXPECT_EQ_INT_MATRIX(inv, inverse);
 305
 306   mat = makeIntMatrix(
 307       4, 4, {{4, 14, 11, 3}, {13, 5, 14, 12}, {13, 9, 7, 14}, {2, 3, 12, 7}});
 308   inverse = makeIntMatrix(4, 4,
 309                           {{155, 1636, -579, -1713},
 310                            {725, -743, 537, -111},
 311                            {210, 735, -855, 360},
 312                            {-715, -1409, 1401, 1482}});
 313
 314   mat.determinant(&inv);
 315
 316   EXPECT_EQ_INT_MATRIX(inv, inverse);
 317
 318   mat = makeIntMatrix(2, 2, {{0, 0}, {1, 2}});
 319
 320   DynamicAPInt det = mat.determinant(&inv);
 321
 322   EXPECT_EQ(det, 0);
 323 }
 324
 325 TEST(MatrixTest, gramSchmidt) {
 326   FracMatrix mat =
 327       makeFracMatrix(3, 5,
 328                      {{Fraction(3, 1), Fraction(4, 1), Fraction(5, 1),
 329                        Fraction(12, 1), Fraction(19, 1)},
 330                       {Fraction(4, 1), Fraction(5, 1), Fraction(6, 1),
 331                        Fraction(13, 1), Fraction(20, 1)},
 332                       {Fraction(7, 1), Fraction(8, 1), Fraction(9, 1),
 333                        Fraction(16, 1), Fraction(24, 1)}});
 334
 335   FracMatrix gramSchmidt = makeFracMatrix(
 336       3, 5,
 337       {{Fraction(3, 1), Fraction(4, 1), Fraction(5, 1), Fraction(12, 1),
 338         Fraction(19, 1)},
 339        {Fraction(142, 185), Fraction(383, 555), Fraction(68, 111),
 340         Fraction(13, 185), Fraction(-262, 555)},
 341        {Fraction(53, 463), Fraction(27, 463), Fraction(1, 463),
 342         Fraction(-181, 463), Fraction(100, 463)}});
 343
 344   FracMatrix gs = mat.gramSchmidt();
 345
 346   EXPECT_EQ_FRAC_MATRIX(gs, gramSchmidt);
 347   for (unsigned i = 0; i < 3u; i++)
 348     for (unsigned j = i + 1; j < 3u; j++)
 349       EXPECT_EQ(dotProduct(gs.getRow(i), gs.getRow(j)), 0);
 350
 351   mat = makeFracMatrix(3, 3,
 352                        {{Fraction(20, 1), Fraction(17, 1), Fraction(10, 1)},
 353                         {Fraction(20, 1), Fraction(18, 1), Fraction(6, 1)},
 354                         {Fraction(15, 1), Fraction(14, 1), Fraction(10, 1)}});
 355
 356   gramSchmidt = makeFracMatrix(
 357       3, 3,
 358       {{Fraction(20, 1), Fraction(17, 1), Fraction(10, 1)},
 359        {Fraction(460, 789), Fraction(1180, 789), Fraction(-2926, 789)},
 360        {Fraction(-2925, 3221), Fraction(3000, 3221), Fraction(750, 3221)}});
 361
 362   gs = mat.gramSchmidt();
 363
 364   EXPECT_EQ_FRAC_MATRIX(gs, gramSchmidt);
 365   for (unsigned i = 0; i < 3u; i++)
 366     for (unsigned j = i + 1; j < 3u; j++)
 367       EXPECT_EQ(dotProduct(gs.getRow(i), gs.getRow(j)), 0);
 368
 369   mat = makeFracMatrix(
 370       4, 4,
 371       {{Fraction(1, 26), Fraction(13, 12), Fraction(34, 13), Fraction(7, 10)},
 372        {Fraction(40, 23), Fraction(34, 1), Fraction(11, 19), Fraction(15, 1)},
 373        {Fraction(21, 22), Fraction(10, 9), Fraction(4, 11), Fraction(14, 11)},
 374        {Fraction(35, 22), Fraction(1, 15), Fraction(5, 8), Fraction(30, 1)}});
 375
 376   gs = mat.gramSchmidt();
 377
 378   // The integers involved are too big to construct the actual matrix.
 379   // but we can check that the result is linearly independent.
 380   ASSERT_FALSE(mat.determinant(nullptr) == 0);
 381
 382   for (unsigned i = 0; i < 4u; i++)
 383     for (unsigned j = i + 1; j < 4u; j++)
 384       EXPECT_EQ(dotProduct(gs.getRow(i), gs.getRow(j)), 0);
 385
 386   mat = FracMatrix::identity(/*dim=*/10);
 387
 388   gs = mat.gramSchmidt();
 389
 390   EXPECT_EQ_FRAC_MATRIX(gs, FracMatrix::identity(10));
 391 }
 392
 393 void checkReducedBasis(FracMatrix mat, Fraction delta) {
 394   FracMatrix gsOrth = mat.gramSchmidt();
 395
 396   // Size-reduced check.
 397   for (unsigned i = 0, e = mat.getNumRows(); i < e; i++) {
 398     for (unsigned j = 0; j < i; j++) {
 399       Fraction mu = dotProduct(mat.getRow(i), gsOrth.getRow(j)) /
 400                     dotProduct(gsOrth.getRow(j), gsOrth.getRow(j));
 401       EXPECT_TRUE(abs(mu) <= Fraction(1, 2));
 402     }
 403   }
 404
 405   // Lovasz condition check.
 406   for (unsigned i = 1, e = mat.getNumRows(); i < e; i++) {
 407     Fraction mu = dotProduct(mat.getRow(i), gsOrth.getRow(i - 1)) /
 408                   dotProduct(gsOrth.getRow(i - 1), gsOrth.getRow(i - 1));
 409     EXPECT_TRUE(dotProduct(mat.getRow(i), mat.getRow(i)) >
 410                 (delta - mu * mu) *
 411                     dotProduct(gsOrth.getRow(i - 1), gsOrth.getRow(i - 1)));
 412   }
 413 }
 414
 415 TEST(MatrixTest, LLL) {
 416   FracMatrix mat =
 417       makeFracMatrix(3, 3,
 418                      {{Fraction(1, 1), Fraction(1, 1), Fraction(1, 1)},
 419                       {Fraction(-1, 1), Fraction(0, 1), Fraction(2, 1)},
 420                       {Fraction(3, 1), Fraction(5, 1), Fraction(6, 1)}});
 421   mat.LLL(Fraction(3, 4));
 422
 423   checkReducedBasis(mat, Fraction(3, 4));
 424
 425   mat = makeFracMatrix(
 426       2, 2,
 427       {{Fraction(12, 1), Fraction(2, 1)}, {Fraction(13, 1), Fraction(4, 1)}});
 428   mat.LLL(Fraction(3, 4));
 429
 430   checkReducedBasis(mat, Fraction(3, 4));
 431
 432   mat = makeFracMatrix(3, 3,
 433                        {{Fraction(1, 1), Fraction(0, 1), Fraction(2, 1)},
 434                         {Fraction(0, 1), Fraction(1, 3), -Fraction(5, 3)},
 435                         {Fraction(0, 1), Fraction(0, 1), Fraction(1, 1)}});
 436   mat.LLL(Fraction(3, 4));
 437
 438   checkReducedBasis(mat, Fraction(3, 4));
 439 }
 440
 441 TEST(MatrixTest, moveColumns) {
 442   IntMatrix mat =
 443       makeIntMatrix(3, 4, {{0, 1, 2, 3}, {4, 5, 6, 7}, {8, 9, 4, 2}});
 444
 445   {
 446     IntMatrix movedMat =
 447         makeIntMatrix(3, 4, {{0, 3, 1, 2}, {4, 7, 5, 6}, {8, 2, 9, 4}});
 448
 449     movedMat.moveColumns(2, 2, 1);
 450     checkMatEqual(mat, movedMat);
 451   }
 452
 453   {
 454     IntMatrix movedMat =
 455         makeIntMatrix(3, 4, {{0, 3, 1, 2}, {4, 7, 5, 6}, {8, 2, 9, 4}});
 456
 457     movedMat.moveColumns(1, 1, 3);
 458     checkMatEqual(mat, movedMat);
 459   }
 460
 461   {
 462     IntMatrix movedMat =
 463         makeIntMatrix(3, 4, {{1, 2, 0, 3}, {5, 6, 4, 7}, {9, 4, 8, 2}});
 464
 465     movedMat.moveColumns(0, 2, 1);
 466     checkMatEqual(mat, movedMat);
 467   }
 468
 469   {
 470     IntMatrix movedMat =
 471         makeIntMatrix(3, 4, {{1, 0, 2, 3}, {5, 4, 6, 7}, {9, 8, 4, 2}});
 472
 473     movedMat.moveColumns(0, 1, 1);
 474     checkMatEqual(mat, movedMat);
 475   }
 476 }