477 lines · 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-exception6//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 15using namespace mlir;16using namespace presburger;17 18TEST(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 28TEST(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 50TEST(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 72TEST(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 97TEST(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 else116 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 134TEST(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 else154 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 172TEST(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 197template <typename T>198static 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 207static void checkHermiteNormalForm(const IntMatrix &mat,208 const IntMatrix &hermiteForm) {209 auto [h, u] = mat.computeHermiteNormalForm();210 211 checkMatEqual(h, hermiteForm);212}213 214TEST(MatrixTest, computeHermiteNormalForm) {215 // TODO: Add a check to test the original statement of hermite normal form216 // 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 261TEST(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 297TEST(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 325TEST(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 393static 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 415TEST(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 441TEST(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}477