-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathReduceMatrix.cpp
More file actions
104 lines (83 loc) · 3.24 KB
/
ReduceMatrix.cpp
File metadata and controls
104 lines (83 loc) · 3.24 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include "ReduceMatrix.h"
void ReduceMatrix(std::vector<std::bitset<wordSize>> &nullMat,
std::vector<std::size_t> &myCols,
std::size_t nCols, std::size_t nRows) {
const std::size_t matSize = nullMat.size();
const std::size_t adjustedCols = (nCols + wordSize - 1) / wordSize;
std::size_t rowInd = 0;
for (std::size_t j = 0; j < nCols; ++j) {
std::vector<std::size_t> rows;
for (std::size_t d = j / wordSize, i = rowInd + d,
m = j % wordSize; i < matSize; i += adjustedCols) {
if (nullMat[i].test(m)) {
rows.push_back(i - d);
}
}
if (!rows.empty()) {
std::vector<std::size_t> cols;
auto&& firstRow = rows.front();
if (firstRow != rowInd) {
for (std::size_t k = j / wordSize; k < adjustedCols; ++k) {
std::swap(nullMat[firstRow + k], nullMat[rowInd + k]);
}
}
if (rows.size() > 1) {
for (std::size_t k = j / wordSize; k < adjustedCols; ++k) {
if (nullMat[rowInd + k].any()) {
cols.push_back(k);
}
}
for (std::size_t i = 1; i < rows.size(); ++i) {
auto&& r = rows[i];
for (auto k: cols) {
nullMat[r + k] ^= nullMat[rowInd + k];
}
}
}
rowInd += adjustedCols;
}
}
if (rowInd < matSize && rowInd != 0) {
nullMat.resize(rowInd);
}
if (rowInd > 0) {
for (std::size_t i = 0, k = 0; i < rowInd; ) {
bool allZero = true;
for (std::size_t j = 0; j < adjustedCols; ++j) {
if (nullMat[i + j].any()) {
allZero = false;
break;
}
}
if (allZero) {
rowInd -= nCols;
} else {
if (!nullMat[i + k / wordSize].test(k % wordSize)) {
for (std::size_t d2 = (k + 1) / wordSize;
d2 < adjustedCols; ++d2) {
if (nullMat[i + d2].any()) {
const std::size_t d1 = k / wordSize;
const std::size_t col1 = k % wordSize;
std::size_t col2 = 0;
while (!nullMat[i + d2].test(col2))
++col2;
for (std::size_t m = 0;
m < rowInd; m += adjustedCols) {
if (nullMat[m + d1].test(col1) !=
nullMat[m + d2].test(col2)) {
nullMat[m + d1].flip(col1);
nullMat[m + d2].flip(col2);
}
}
std::swap(myCols[d2 * wordSize + col2], myCols[k]);
break;
}
}
}
i += adjustedCols;
++k;
}
}
nullMat.resize(rowInd);
}
}