Frobby 0.9.5
MatrixTest.cpp
Go to the documentation of this file.
1/* Frobby: Software for monomial ideal computations.
2 Copyright (C) 2010 University of Aarhus
3 Contact Bjarke Hammersholt Roune for license information (www.broune.com)
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see http://www.gnu.org/licenses/.
17*/
18#include "stdinc.h"
19#include "Matrix.h"
20#include "tests.h"
21
22#include "BigIntVector.h"
23
25
26namespace {
27 Matrix makeMatrix(size_t colCount, const char* entries) {
28 Matrix mat;
29 istringstream in(entries);
30 mpq_class entry;
31 while (in >> entry) {
32 mat.resize(mat.getRowCount() + 1, colCount);
33 mat(mat.getRowCount() - 1, 0) = entry;
34 for (size_t col = 1; col < colCount; ++col)
35 in >> mat(mat.getRowCount() - 1, col);
36 }
37 return mat;
38 }
39
40 Matrix make123() {
41 return makeMatrix(4,
42 "1 2 3 1\n"
43 "4 5 6 1\n"
44 "7 8 9 1\n");
45 }
46
47 BigIntVector makeVector(const char* entries) {
48 BigIntVector vec(0);
49 istringstream in(entries);
50 mpz_class entry;
51 while (in >> entry) {
52 vec.resize(vec.getSize() + 1);
53 vec[vec.getSize() - 1] = entry;
54 }
55 return vec;
56 }
57}
58
59TEST(Matrix, Basic) {
60 Matrix mat = make123();
61 ASSERT_EQ(mat.getRowCount(), 3u);
62 ASSERT_EQ(mat.getColCount(), 4u);
63 ASSERT_EQ(mat(0, 0), 1);
64 ASSERT_EQ(mat(2, 3), 1);
65 ASSERT_EQ(mat(0, 1), 2);
66
67 const Matrix con = mat;
68 ASSERT_EQ(con.getRowCount(), 3u);
69 ASSERT_EQ(con.getColCount(), 4u);
70 ASSERT_EQ(con(0, 0), 1);
71 ASSERT_EQ(con(2, 3), 1);
72 ASSERT_EQ(con(0, 1), 2);
73}
74
75TEST(Matrix, Resize) {
76 Matrix mat = make123();
77
78 mat.resize(10, 10);
79 ASSERT_EQ(mat.getRowCount(), 10u);
80 ASSERT_EQ(mat.getColCount(), 10u);
81 ASSERT_EQ(mat(0, 1), 2);
82 ASSERT_EQ(mat(2, 3), 1);
83 ASSERT_EQ(mat(9, 9), 0);
84
85 mat.resize(1, 2);
86 ASSERT_EQ(mat.getRowCount(), 1u);
87 ASSERT_EQ(mat.getColCount(), 2u);
88 ASSERT_EQ(mat(0, 1), 2);
89
90 mat.resize(0, 0);
91 ASSERT_EQ(mat.getRowCount(), 0u);
92 ASSERT_EQ(mat.getColCount(), 0u);
93
94 mat.resize(2, 1);
95 ASSERT_EQ(mat.getRowCount(), 2u);
96 ASSERT_EQ(mat.getColCount(), 1u);
97 ASSERT_EQ(mat(1, 0), 0);
98}
99
100TEST(Matrix, Swap) {
101 Matrix mat1 = make123();
102 Matrix mat2(2, 1);
103 mat2(1, 0) = 42;
104 Matrix mat2Copy = mat2;
105
106 swap(mat1, mat2);
107
108 ASSERT_EQ(mat2, make123());
109 ASSERT_EQ(mat1, mat2Copy);
110}
111
112TEST(Matrix, Transpose) {
113 Matrix mat = make123();
114 Matrix trans;
115 transpose(trans, mat);
116 ASSERT_EQ(trans.getRowCount(), 4u);
117 ASSERT_EQ(trans.getColCount(), 3u);
118 ASSERT_EQ(trans(3, 2), 1);
119 ASSERT_EQ(trans(2, 2), 9);
120}
121
122TEST(Matrix, AddMultiplyRow) {
123 Matrix mat = make123();
124
125 addMultiplyRow(mat, 2, 0, -3);
126 ASSERT_EQ(mat, makeMatrix(4,
127 "1 2 3 1\n"
128 "4 5 6 1\n"
129 "4 2 0 -2\n"));
130
131 addMultiplyRow(mat, 0, 2, mpq_class("-3/2"));
132 ASSERT_EQ(mat, makeMatrix(4,
133 "-5 -1 3 4\n"
134 "4 5 6 1\n"
135 "4 2 0 -2\n"));
136
137 addMultiplyRow(mat, 2, 2, 2);
138 ASSERT_EQ(mat, makeMatrix(4,
139 "-5 -1 3 4\n"
140 "4 5 6 1\n"
141 "12 6 0 -6\n"));
142}
143
144TEST(Matrix, MultiplyRows) {
145 Matrix mat = make123();
146 multiplyRow(mat, 1, 2);
147 ASSERT_EQ(mat, makeMatrix(4,
148 "1 2 3 1\n"
149 "8 10 12 2\n"
150 "7 8 9 1\n"));
151}
152
153TEST(Matrix, SwapRows) {
154 Matrix mat = make123();
155
156 swapRows(mat, 1, 1);
157 ASSERT_EQ(mat, make123());
158
159 swapRows(mat, 0, 2);
160 ASSERT_EQ(mat, makeMatrix(4,
161 "7 8 9 1\n"
162 "4 5 6 1\n"
163 "1 2 3 1\n"));
164}
165
166TEST(Matrix, RowReduceAndFully1) {
167 Matrix mat = make123();
168 rowReduce(mat);
169 ASSERT_EQ(mat, makeMatrix(4,
170 "1 2 3 1\n"
171 "0 -3 -6 -3\n"
172 "0 0 0 0\n"));
173
174 rowReduceFully(mat);
175 ASSERT_EQ(mat, makeMatrix(4,
176 "1 0 -1 -1\n"
177 "0 1 2 1\n"
178 "0 0 0 0\n"));
179}
180
181TEST(Matrix, RowReduceAndFully2) {
182 Matrix mat = makeMatrix(5,
183 "-4 -8 3 0 23\n"
184 "-4 -8 2 -1 8\n"
185 " 2 4 -1 3/2 4\n");
186 Matrix red = makeMatrix(5,
187 "1 2 0 0 -1/2\n"
188 "0 0 1 0 7\n"
189 "0 0 0 1 8\n");
190
191 rowReduceFully(mat);
192 ASSERT_EQ(mat, red);
193
194 rowReduce(mat);
195 ASSERT_EQ(mat, red);
196
197 rowReduceFully(mat);
198 ASSERT_EQ(mat, red);
199}
200
201TEST(Matrix, RowReduceAndFully3) {
202 Matrix mat(0, 0);
203
204 rowReduce(mat);
205 ASSERT_EQ(mat, Matrix(0, 0));
206
207 rowReduceFully(mat);
208 ASSERT_EQ(mat, Matrix(0, 0));
209}
210
211TEST(Matrix, RowReduceAndFully4) {
212 Matrix mat(3, 7);
213
214 rowReduce(mat);
215 ASSERT_EQ(mat, Matrix(3, 7));
216
217 rowReduceFully(mat);
218 ASSERT_EQ(mat, Matrix(3, 7));
219}
220
221TEST(Matrix, SubMatrix) {
222 Matrix mat = make123();
223 Matrix sub;
224
225 subMatrix(sub, mat, 0, 3, 0, 4);
226 ASSERT_EQ(sub, mat);
227
228 subMatrix(sub, mat, 1, 1, 0, 0);
229 ASSERT_EQ(sub, Matrix(0, 0));
230
231 subMatrix(sub, mat, 0, 2, 2, 3);
232 ASSERT_EQ(sub, makeMatrix(1, "3\n6\n"));
233
234 subMatrix(mat, mat, 1, 2, 2, 3);
235 ASSERT_EQ(mat, makeMatrix(1, "6\n"));
236}
237
238TEST(Matrix, Inverse) {
239 Matrix mat = makeMatrix(3,
240 "1 3 3\n"
241 "1 4 3\n"
242 "1 3 4\n");
243 Matrix inv;
244
245 inverse(inv, mat);
246 ASSERT_EQ(inv, makeMatrix(3,
247 " 7 -3 -3\n"
248 "-1 1 0\n"
249 "-1 0 1\n"));
250
251 inverse(mat, mat);
252 ASSERT_EQ(inv, mat);
253}
254
255TEST(Matrix, NullSpace1) {
256 Matrix mat = makeMatrix(6,
257 "1 2 0 0 3 0\n"
258 "0 0 1 0 7 0\n"
259 "0 0 0 1 8 0\n"
260 "0 0 0 0 0 0\n");
261 Matrix basis;
262
263 nullSpace(basis, mat);
264 ASSERT_EQ(basis, makeMatrix(3,
265 "-2 -3 0\n"
266 " 1 0 0\n"
267 " 0 -7 0\n"
268 " 0 -8 0\n"
269 " 0 1 0\n"
270 " 0 0 1\n"));
271}
272
273TEST(Matrix, NullSpace2) {
274 Matrix mat = make123();
275 Matrix basis;
276
277 nullSpace(basis, mat);
278 ASSERT_EQ(basis, makeMatrix(2,
279 " 1 1\n"
280 "-2 -1\n"
281 " 1 0\n"
282 " 0 1\n"));
283}
284
285TEST(Matrix, NullSpace3) {
286 Matrix mat = makeMatrix(6,
287 "13 -171 29 41 37 17\n"
288 "11 61 -278 131 19 23\n"
289 "-3 53 123 -317 41 7\n"
290 "11 97 23 47 -297 41\n"
291 "13 19 11 37 61 -143\n");
292 Matrix basis;
293
294 nullSpace(basis, mat);
295 ASSERT_EQ(basis, makeMatrix(1,
296 "36441469497\n"
297 " 6795794100\n"
298 " 5893319208\n"
299 " 4007175176\n"
300 " 5788247217\n"
301 " 8175064786\n"));
302}
303
304TEST(Matrix, Solve1) {
305 Matrix lhs = make123();
306 Matrix rhs = makeMatrix(2,
307 "5 5\n"
308 "14 13\n"
309 "26 23\n");
310 bool hasSolution = solve(lhs, lhs, rhs);
311
312 ASSERT_FALSE(hasSolution);
313 ASSERT_EQ(lhs, make123()); // no change if no solution
314}
315
316TEST(Matrix, Solve2) {
317 Matrix lhs = make123();
318 Matrix rhs = makeMatrix(1, "5\n14\n23\n");
319 Matrix sol;
320 bool hasSolution = solve(sol, lhs, rhs);
321
322 ASSERT_TRUE(hasSolution);
323 ASSERT_EQ(sol, makeMatrix(1, "1\n2\n0\n0"));
324}
325
326TEST(Matrix, Solve3) {
327 Matrix lhs = makeMatrix(1, "2");
328 Matrix rhs = makeMatrix(2, "-1 8");
329 Matrix sol;
330 bool hasSolution = solve(sol, lhs, rhs);
331
332 ASSERT_TRUE(hasSolution);
333 ASSERT_EQ(sol, makeMatrix(2, "-1/2\n4\n"));
334}
335
336TEST(Matrix, Print) {
337 const char* str =
338 " 13 -171 29 41 37 17\n"
339 " 11 61 -278 131 19 23\n"
340 " -3 53 123 -317 41 7\n"
341 " 11 97 23 47 -297 41\n"
342 " 13 19 11 37 61 -143\n";
343 ostringstream pr;
344 pr << makeMatrix(6, str);
345 ASSERT_EQ(pr.str(), str);
346}
347
348TEST(Matrix, Determinant) {
349 Matrix mat1 = makeMatrix
350 (3,
351 " 4 1 1\n"
352 "-1 -2 1\n"
353 " 2 -1 0\n");
354 ASSERT_EQ(determinant(mat1), 11);
355
356 Matrix mat2 = makeMatrix
357 (2,
358 " 0 3\n"
359 " 2 0\n");
360 ASSERT_EQ(determinant(mat2), -6);
361
362 Matrix mat3 = makeMatrix
363 (3,
364 " 0 1 0\n"
365 " 2 0 100\n"
366 " 0 0 7\n");
367 ASSERT_EQ(determinant(mat3), -14);
368
369 Matrix mat4 = makeMatrix
370 (1, "-2\n");
371 ASSERT_EQ(determinant(mat4), -2);
372}
373
374TEST(Matrix, IsParallelogram) {
375 // zeroes and variations of number of pointsx
376 for (size_t dim = 0; dim < 5; ++dim) {
381 }
382
383 // permutations
384 ASSERT_TRUE(isParallelogram(makeMatrix(2, "1 1\n 2 3\n 3 1\n 4 3\n")));
385 ASSERT_TRUE(isParallelogram(makeMatrix(2, "2 3\n 1 1\n 3 1\n 4 3\n")));
386 ASSERT_TRUE(isParallelogram(makeMatrix(2, "2 3\n 1 1\n 4 3\n 3 1\n")));
387 ASSERT_TRUE(isParallelogram(makeMatrix(2, "2 3\n 4 3\n 1 1\n 3 1\n")));
388 ASSERT_TRUE(isParallelogram(makeMatrix(2, "4 3\n 2 3\n 1 1\n 3 1\n")));
389 ASSERT_FALSE(isParallelogram(makeMatrix(2, "4 3\n 2 3\n 1 1\n 3 3\n")));
390
391 // higher dimension
392 ASSERT_TRUE(isParallelogram(makeMatrix(3,"1 1 4\n 2 3 6\n 3 1 7\n 4 3 9\n")));
393 ASSERT_FALSE(isParallelogram(makeMatrix(3,"1 1 5\n2 3 6\n 3 1 7\n 4 3 9\n")));
394
395 // lower dimension
396 ASSERT_TRUE(isParallelogram(makeMatrix(1, "1\n 2\n 3\n 4\n")));
397 ASSERT_FALSE(isParallelogram(makeMatrix(1, "1\n 1\n 3\n 4\n")));
398}
399
400TEST(Matrix, GetParallelogramArea) {
401 ASSERT_EQ(0, getParallelogramAreaSq(makeMatrix(1, "1\n1\n1\n1")));
402 ASSERT_EQ(0, getParallelogramAreaSq(makeMatrix(2, "1 2\n1 2\n3 5\n3 5")));
403 ASSERT_EQ(1, getParallelogramAreaSq(makeMatrix(2, "0 0\n0 1\n1 0\n1 1")));
404 ASSERT_EQ(4, getParallelogramAreaSq(makeMatrix(2, "0 0\n0 2\n1 0\n1 2")));
405 ASSERT_EQ(4, getParallelogramAreaSq(makeMatrix(2, "1 2\n1 4\n2 2\n2 4")));
407 (makeMatrix(3, "1 2 1\n1 4 1\n2 2 1\n2 4 1")));
408
410 (makeMatrix(3, "1 2 0\n1 4 2\n2 2 3\n2 4 5")));
411
413 (makeMatrix(3, "5 -1 6\n 13 -5 5\n -14 5 -7\n -6 1 -8")));
415 (makeMatrix(4, "-17 -15 -16 29\n -16 7 -24 18\n"
416 "-2 -10 27 -14\n -1 12 19 -25")));
417}
TEST(Matrix, Basic)
Definition: MatrixTest.cpp:59
void multiplyRow(Matrix &mat, size_t row, const mpq_class &mult)
Multiplies row row with mult.
Definition: Matrix.cpp:156
bool solve(Matrix &sol, const Matrix &lhs, const Matrix &rhs)
Sets sol to some matrix such that lhs*sol=rhs and returns true if such a matrix exists.
Definition: Matrix.cpp:348
mpq_class getParallelogramAreaSq(const Matrix &mat)
Returns the square of the area of the parallelogram whose vertices are the 4 rows of mat.
Definition: Matrix.cpp:456
bool isParallelogram(const Matrix &mat)
Returns true if the rows of mat are the (4) vertices of a parallelogram.
Definition: Matrix.cpp:452
void addMultiplyRow(Matrix &mat, size_t resultRow, size_t sourceRow, const mpq_class &mult)
Adds mult times row sourceRow to row resultRow of mat.
Definition: Matrix.cpp:147
bool rowReduce(Matrix &mat)
Reduces mat to row-echelon form, i.e.
Definition: Matrix.cpp:169
void swapRows(Matrix &mat, size_t row1, size_t row2)
Swaps row row1 and row row2 of mat.
Definition: Matrix.cpp:161
void nullSpace(Matrix &basis, const Matrix &matParam)
Sets the columns of basis to a basis of the null space of mat.
Definition: Matrix.cpp:296
mpq_class determinant(const Matrix &mat)
Returns the determinant of mat.
Definition: Matrix.cpp:410
void subMatrix(Matrix &sub, const Matrix &mat, size_t rowBegin, size_t rowEnd, size_t colBegin, size_t colEnd)
Sets sub to the sub-matrix of mat with rows in the interval [rowBegin, rowEnd) and columns in the int...
Definition: Matrix.cpp:225
void rowReduceFully(Matrix &mat)
Reduces mat to reduced row-echelon form, i.e.
Definition: Matrix.cpp:200
bool inverse(Matrix &inv, const Matrix &mat)
Sets inv to the inverse of mat.
Definition: Matrix.cpp:257
void transpose(Matrix &trans, const Matrix &mat)
Sets trans to the transpose of mat.
Definition: Matrix.cpp:129
#define ASSERT_TRUE(VALUE)
Definition: asserts.h:72
#define ASSERT_EQ(A, B)
Definition: asserts.h:147
#define ASSERT_FALSE(VALUE)
Definition: asserts.h:119
Definition: Matrix.h:26
void resize(size_t rowCount, size_t colCount)
Set the number of rows and columns.
Definition: Matrix.cpp:61
size_t getColCount() const
Definition: Matrix.h:31
size_t getRowCount() const
Definition: Matrix.h:30
#define TEST_SUITE(SUITE)
Definition: macroes.h:26
void swap(hashtable< _Val, _Key, _HF, _Extract, _EqKey, _All > &__ht1, hashtable< _Val, _Key, _HF, _Extract, _EqKey, _All > &__ht2)
Definition: hashtable.h:740