52 file.open(fname.c_str());
54 "GF2mat_sparse_alist::read(): Could not open file \"" 55 << fname <<
"\" for reading");
62 "GF2mat_sparse_alist::read(): Wrong alist data (N or M)");
64 "GF2mat_sparse_alist::read(): Wrong alist data");
65 ss.seekg(0, std::ios::end);
73 "GF2mat_sparse_alist::read(): Wrong alist data (max_num_{n,m})");
76 "GF2mat_sparse_alist::read(): Wrong alist data");
77 ss.seekg(0, std::ios::end);
85 for (
int i = 0; i <
N; i++) {
88 "GF2mat_sparse_alist::read(): Wrong alist data (num_nlist(" 91 "GF2mat_sparse_alist::read(): Wrong alist data (num_nlist(" 94 ss.seekg(0, std::ios::end);
102 for (
int i = 0; i <
M; i++) {
105 "GF2mat_sparse_alist::read(): Wrong alist data (num_mlist(" 108 "GF2mat_sparse_alist::read(): Wrong alist data (num_mlist(" 111 ss.seekg(0, std::ios::end);
117 for (
int i = 0; i <
N; i++) {
123 "GF2mat_sparse_alist::read(): Wrong alist data (nlist(" 124 << i <<
"," << j <<
"))");
126 "GF2mat_sparse_alist::read(): Wrong alist data (nlist(" 127 << i <<
"," << j <<
"))");
129 ss.seekg(0, std::ios::end);
136 for (
int i = 0; i <
M; i++) {
142 "GF2mat_sparse_alist::read(): Wrong alist data (mlist(" 143 << i <<
"," << j <<
"))");
145 "GF2mat_sparse_alist::read(): Wrong alist data (mlist(" 146 << i <<
"," << j <<
"))");
148 ss.seekg(0, std::ios::end);
159 "GF2mat_sparse_alist::write(): alist data not ready for writing");
161 std::ofstream file(fname.c_str(), std::ofstream::out);
163 "GF2mat_sparse_alist::write(): Could not open file \"" 164 << fname <<
"\" for writing");
166 file <<
N <<
" " <<
M << std::endl;
169 for (
int i = 0; i <
num_nlist.length() - 1; i++)
173 for (
int i = 0; i <
num_mlist.length() - 1; i++)
177 for (
int i = 0; i <
N; i++) {
178 for (
int j = 0; j <
num_nlist(i) - 1; j++)
179 file <<
nlist(i, j) <<
" ";
183 for (
int i = 0; i <
M; i++) {
184 for (
int j = 0; j <
num_mlist(i) - 1; j++)
185 file <<
mlist(i, j) <<
" ";
197 for (
int i = 0; i <
M; i++) {
232 mlist.set_size(0, 0);
234 for (
int i = 0; i <
M; i++) {
236 for (
int j = 0; j <
N; j++) {
237 if (sbmat(i, j) ==
bin(1)) {
238 temp_row =
concat(temp_row, j + 1);
241 int trs = temp_row.size();
242 if (trs > tmp_cols) {
244 mlist.set_size(
M, tmp_cols,
true);
246 else if (trs < tmp_cols) {
247 temp_row.set_size(tmp_cols,
true);
249 mlist.set_row(i, temp_row);
255 nlist.set_size(0, 0);
257 for (
int j = 0; j <
N; j++) {
258 ivec temp_row = sbmat.
get_col(j).get_nz_indices() + 1;
259 int trs = temp_row.size();
260 if (trs > tmp_cols) {
262 nlist.set_size(
N, tmp_cols,
true);
264 else if (trs < tmp_cols) {
265 temp_row.set_size(tmp_cols,
true);
267 nlist.set_row(j, temp_row);
282 nwords((j >> shift_divisor) + 1)
302 for (
int i = 0; i < nrows; i++) {
309 nwords = (ncols >> shift_divisor) + 1;
312 for (
int i = 0; i < ncols; i++) {
321 nwords = (ncols >> shift_divisor) + 1;
324 for (
int i = 0; i < nrows; i++) {
325 for (
int j = 0; j < ncols; j++) {
336 nwords = (ncols >> shift_divisor) + 1;
338 for (
int i = 0; i < nrows; i++) {
339 for (
int j = 0; j < nwords; j++) {
344 for (
int j = 0; j < ncols; j++) {
345 for (
int i = 0; i < X.
get_col(j).nnz(); i++) {
347 set(X.
get_col(j).get_nz_index(i), j, b);
356 it_assert(m1 >= 0 && n1 >= 0 && m2 >= m1 && n2 >= n1,
357 "GF2mat::GF2mat(): indexes out of range");
361 nwords = (ncols >> shift_divisor) + 1;
364 for (
int i = 0; i < nrows; i++) {
365 for (
int j = 0; j < nwords; j++) {
370 for (
int i = 0; i < nrows; i++) {
371 for (
int j = 0; j < ncols; j++) {
372 bin b = X(i + m1, j + n1);
382 "GF2mat::GF2mat(): index out of range");
384 "GF2mat::GF2mat(): column index must be positive");
388 nwords = (ncols >> shift_divisor) + 1;
391 for (
int i = 0; i < nrows; i++) {
392 for (
int j = 0; j < nwords; j++) {
397 for (
int j = 0; j < ncols; j++) {
398 for (
int i = 0; i < X.
get_col(columns(j)).nnz(); i++) {
400 set(X.
get_col(columns(j)).get_nz_index(i), j, b);
410 nwords = (ncols >> shift_divisor) + 1;
420 for (
int i = 0; i < nrows; i++) {
421 for (
int j = 0; j < ncols; j++) {
422 if (
get(i, j) == 1) {
434 "GF2mat::bvecify() matrix must be a vector");
435 int n = (nrows == 1 ? ncols : nrows);
438 for (
int i = 0; i < n; i++) {
439 result(i) =
get(0, i);
443 for (
int i = 0; i < n; i++) {
444 result(i) =
get(i, 0);
454 "GF2mat::set_row(): dimension mismatch");
455 for (
int j = 0; j < ncols; j++) {
463 "GF2mat::set_col(): dimension mismatch");
464 for (
int i = 0; i < nrows; i++) {
473 for (
int i = 0; i < m; i++) {
481 it_assert(m1 >= 0 && n1 >= 0 && m2 >= m1 && n2 >= n1
482 && m2 < nrows && n2 < ncols,
483 "GF2mat::get_submatrix() index out of range");
484 GF2mat result(m2 - m1 + 1, n2 - n1 + 1);
486 for (
int i = m1; i <= m2; i++) {
487 for (
int j = n1; j <= n2; j++) {
488 result.
set(i - m1, j - n1,
get(i, j));
499 "GF2mat::concatenate_vertical(): dimension mismatch");
501 "GF2mat::concatenate_vertical(): dimension mismatch");
503 GF2mat result(nrows + X.nrows, ncols);
504 for (
int i = 0; i < nrows; i++) {
505 for (
int j = 0; j < nwords; j++) {
506 result.data(i, j) = data(i, j);
510 for (
int i = 0; i < X.nrows; i++) {
511 for (
int j = 0; j < nwords; j++) {
512 result.data(i + nrows, j) = X.data(i, j);
522 "GF2mat::concatenate_horizontal(): dimension mismatch");
524 GF2mat result(nrows, X.ncols + ncols);
525 for (
int i = 0; i < nrows; i++) {
526 for (
int j = 0; j < ncols; j++) {
527 result.
set(i, j,
get(i, j));
531 for (
int i = 0; i < nrows; i++) {
532 for (
int j = 0; j < X.ncols; j++) {
533 result.
set(i, j + ncols, X.
get(i, j));
543 for (
int j = 0; j < ncols; j++) {
544 result(j) =
get(i, j);
553 for (
int i = 0; i < nrows; i++) {
554 result(i) =
get(i, j);
567 for (
int i = 0; i < ncols; i++) {
572 it_info_debug(
"Performing T-factorization of GF(2) matrix... rows: " 573 << nrows <<
" cols: " << ncols <<
" .... " << std::endl);
576 for (
int j = 0; j < nrows; j++) {
580 for (i1 = j; i1 < nrows; i1++) {
581 for (j1 = j; j1 < ncols; j1++) {
582 if (U.
get(i1, j1) == 1) {
goto found; }
598 for (
int i1 = j + 1; i1 < nrows; i1++) {
599 if (U.
get(i1, j) == 1) {
600 int ptemp =
floor_i(100.0 * (i1 + j * nrows) / (nrows * nrows));
601 if (nrows > 250 && ptemp > pdone + 10) {
615 ivec &perm,
int rank,
620 for (c = 0; c < ncols; c++) {
625 it_error(
"GF2mat::T_fact_update_bitflip() - internal error");
628 for (
int i = 0; i < nrows; i++) {
629 if (T.
get(i, r) == 1) {
636 int temp_perm = perm(c);
637 for (
int j = c; j < ncols - 1; j++) {
639 perm(j) = perm(j + 1);
642 perm(ncols - 1) = temp_perm;
645 if (nrows >= ncols) {
648 for (
int i = c; i < nrows - 1; i++) {
652 U.
set_row(nrows - 1, lastrow_U);
653 T.
set_row(nrows - 1, lastrow_T);
656 for (
int j = c; j < ncols; j++) {
657 if (U.
get(nrows - 1, j) == 1) {
665 for (
int j =
rank - 1; j < nrows; j++) {
667 for (i1 = j; i1 < nrows; i1++) {
668 for (j1 = j; j1 < ncols; j1++) {
669 if (U.
get(i1, j1) == 1) {
686 for (
int i1 = j + 1; i1 < nrows; i1++) {
687 if (U.
get(i1, j) == 1) {
698 ivec &perm, bvec newcol)
const 702 it_assert(j0 > 0,
"GF2mat::T_fact_update_addcol(): dimension mismatch");
704 "GF2mat::T_fact_update_addcol(): dimension mismatch");
706 "GF2mat::T_fact_update_addcol(): dimension mismatch");
708 "GF2mat::T_fact_update_addcol(): dimension mismatch");
710 "GF2mat::T_fact_update_addcol(): dimension mismatch");
713 "GF2mat::T_fact_update_addcol(): factorization has incorrect rank");
720 for (i = j0; i < i0; i++) {
721 if (Utemp.
get(i, j0) == 1) {
728 perm.set_length(j0 + 1,
true);
734 for (
int i1 = j0 + 1; i1 < i0; i1++) {
735 if (Utemp.
get(i1, j0) == 1) {
750 it_assert(nrows == ncols,
"GF2mat::inverse(): Matrix must be square");
756 it_assert(
rank == ncols,
"GF2mat::inverse(): Matrix is not full rank");
759 for (
int i = ncols - 2; i >= 0; i--) {
760 for (
int j = ncols - 1; j > i; j--) {
761 if (U.
get(i, j) == 1) {
781 for (
int i = 0; i < nrows; i++) {
782 for (
int j = 0; j < nwords; j++) {
783 if (data(i, j) != 0) {
793 if (X.nrows != nrows) {
return false; }
794 if (X.ncols != ncols) {
return false; }
795 it_assert(X.nwords == nwords,
"GF2mat::operator==() dimension mismatch");
797 for (
int i = 0; i < nrows; i++) {
798 for (
int j = 0; j < nwords; j++) {
800 if (X.data(i, j) != data(i, j)) {
811 it_assert(i >= 0 && i < nrows,
"GF2mat::add_rows(): out of range");
812 it_assert(j >= 0 && j < nrows,
"GF2mat::add_rows(): out of range");
813 for (
int k = 0; k < nwords; k++) {
814 data(i, k) ^= data(j, k);
820 it_assert(i >= 0 && i < nrows,
"GF2mat::swap_rows(): index out of range");
821 it_assert(j >= 0 && j < nrows,
"GF2mat::swap_rows(): index out of range");
822 for (
int k = 0; k < nwords; k++) {
823 unsigned char temp = data(i, k);
824 data(i, k) = data(j, k);
831 it_assert(i >= 0 && i < ncols,
"GF2mat::swap_cols(): index out of range");
832 it_assert(j >= 0 && j < ncols,
"GF2mat::swap_cols(): index out of range");
849 it_assert(X.ncols == Y.nrows,
"GF2mat::operator*(): dimension mismatch");
850 it_assert(X.nwords > 0,
"Gfmat::operator*(): dimension mismatch");
851 it_assert(Y.nwords > 0,
"Gfmat::operator*(): dimension mismatch");
875 it_assert(
length(y) == X.ncols,
"GF2mat::operator*(): dimension mismatch");
876 it_assert(X.nwords > 0,
"Gfmat::operator*(): dimension mismatch");
905 it_assert(X.ncols == Y.ncols,
"GF2mat::mult_trans(): dimension mismatch");
906 it_assert(X.nwords > 0,
"GF2mat::mult_trans(): dimension mismatch");
907 it_assert(Y.nwords > 0,
"GF2mat::mult_trans(): dimension mismatch");
908 it_assert(X.nwords == Y.nwords,
"GF2mat::mult_trans(): dimension mismatch");
910 GF2mat result(X.nrows, Y.nrows);
912 for (
int i = 0; i < X.nrows; i++) {
913 for (
int j = 0; j < Y.nrows; j++) {
917 for (
int k = 0; k < X.nwords; k++) {
918 unsigned char r = X.data(kindx) & Y.data(kindy);
938 GF2mat result(ncols, nrows);
940 for (
int i = 0; i < nrows; i++) {
941 for (
int j = 0; j < ncols; j++) {
942 result.
set(j, i,
get(i, j));
950 it_assert(X.nrows == Y.nrows,
"GF2mat::operator+(): dimension mismatch");
951 it_assert(X.ncols == Y.ncols,
"GF2mat::operator+(): dimension mismatch");
952 it_assert(X.nwords == Y.nwords,
"GF2mat::operator+(): dimension mismatch");
953 GF2mat result(X.nrows, X.ncols);
955 for (
int i = 0; i < X.nrows; i++) {
956 for (
int j = 0; j < X.nwords; j++) {
957 result.data(i, j) = X.data(i, j) ^ Y.data(i, j);
967 "GF2mat::permute_cols(): dimensions do not match");
970 for (
int j = 0; j < ncols; j++) {
983 "GF2mat::permute_rows(): dimensions do not match");
986 for (
int i = 0; i < nrows; i++) {
988 for (
int j = 0; j < nwords; j++) {
989 data(i, j) = temp.data(perm(i), j);
993 for (
int j = 0; j < nwords; j++) {
994 data(perm(i), j) = temp.data(i, j);
1004 os <<
"---- GF(2) matrix of dimension " << X.nrows <<
"*" << X.ncols
1005 <<
" -- Density: " << X.
density() <<
" ----" << std::endl;
1007 for (i = 0; i < X.nrows; i++) {
1009 for (j = 0; j < X.ncols; j++) {
1010 os << X.
get(i, j) <<
" ";
1022 for (
int i = 0; i < nrows; i++) {
1023 for (
int j = 0; j < ncols; j++) {
1024 no_of_ones += (
get(i, j) == 1 ? 1 : 0);
1028 return ((
double) no_of_ones) / (nrows*ncols);
1035 uint64_t bytecount = 3 *
sizeof(uint64_t)
1036 + X.nrows * X.nwords *
sizeof(
char);
1042 for (
int i = 0; i < X.nrows; i++) {
1043 for (
int j = 0; j < X.nwords; j++) {
1055 if (h.
type ==
"GF2mat") {
1058 X.nrows =
static_cast<int>(tmp);
1060 X.ncols =
static_cast<int>(tmp);
1062 X.nwords =
static_cast<int>(tmp);
1063 X.data.
set_size(X.nrows, X.nwords);
1064 for (
int i = 0; i < X.nrows; i++) {
1065 for (
int j = 0; j < X.nwords; j++) {
1068 X.data(i, j) =
static_cast<unsigned char>(r);
1073 it_error(
"it_ifile &operator>>() - internal error");
Various functions on vectors and matrices - header file.
void set_size(int rows, int cols, bool copy=false)
Set size of matrix. If copy = true then keep the data before resizing.
void write(const std::string &fname) const
Write alist data to a file named fname.
void read_data_header(it_file_base::data_header &h)
Read data header and return the result in the variable h.
int rank(const Mat< T > &m, double tol=-1.0)
Calculate the rank of matrix m.
ITPP_EXPORT ivec zeros_i(int size)
A Int vector of zeros.
ivec num_nlist
Weight of each column n.
void permute_cols(ivec &perm, bool I)
Multiply a matrix from right with a permutation matrix (i.e., permute the columns).
int max_num_m
Maximum weight of rows.
int T_fact(GF2mat &T, GF2mat &U, ivec &P) const
TXP factorization.
double density() const
Compute the matrix density (fraction of elements equal to "1")
ivec num_mlist
Weight of each row m.
void set(int i, int j, bin s)
Set element i,j to s (0 or 1)
GF2mat inverse() const
Inversion.
int T_fact_update_bitflip(GF2mat &T, GF2mat &U, ivec &P, int rank, int r, int c) const
TXP factorization update, when bit is flipped.
void read(const std::string &fname)
Read alist data from a file named fname.
Class for dense GF(2) matrices.
void transpose(Sparse_Mat< T > &m) const
int rows() const
Get number of rows.
bin get(int i, int j) const
Getting element.
bool operator==(const GF2mat &X) const
Check if equal.
GF2mat mult_trans(const GF2mat &X, const GF2mat &Y)
Multiplication X*Y' where X and Y are GF(2) matrices.
imat nlist
List of integer coordinates in the n direction with non-zero entries.
std::ostream & operator<<(std::ostream &output, const bin &inbin)
Output stream of bin.
void from_sparse(const GF2mat_sparse &mat, bool transpose=false)
Import "alist" representation from GF2mat_sparse.
void set(int r, int c, T v)
Set element (r, c ) equal to v.
void get_col(int c, Sparse_Vec< T > &v) const
Returns column c of the Sparse_Mat in the Sparse_Vec v.
GF2mat concatenate_vertical(const GF2mat &X) const
Concatenate vertically (append X underneath)
void write_data_header(const std::string &type, uint64_t size)
Write the data header for a variable, specifying the type and size of the data to follow...
bool data_ok
Flag indicating that "alist" matrix data are properly set.
GF2mat gf2dense_eye(int m)
GF(2) Identity matrix.
#define it_assert(t, s)
Abort if t is not true.
int length(const Vec< T > &v)
Length of vector.
#define it_assert_debug(t, s)
Abort if t is not true and NDEBUG is not defined.
void set_size(int m, int n, bool copy=false)
Set size of GF(2) matrix. If copy = true, keep data before resizing.
void swap_cols(int i, int j)
Swap columns i and j.
bool T_fact_update_addcol(GF2mat &T, GF2mat &U, ivec &P, bvec newcol) const
TXP factorization update, when column is added.
ITPP_EXPORT GF2mat gf2dense_eye(int m)
GF(2) Identity matrix.
Definitions of converters between different vector and matrix types.
GF2mat get_submatrix(int m1, int n1, int m2, int n2) const
Submatrix from (m1,n1) to (m2,n2)
T min(const Vec< T > &in)
Minimum value of vector.
void low_level_read(char &x)
Read a char value at the current file pointer position.
#define it_info_debug(s)
Print information message if NDEBUG is not defined.
int M
Size of the matrix: M rows x N columns.
void clear()
Set matrix equal to the all zero matrix.
int cols() const
Get number of columns.
T max(const Vec< T > &v)
Maximum value of vector.
GF2mat operator+(const GF2mat &X, const GF2mat &Y)
GF(2) matrix addition.
void set_new(int r, int c, T v)
Set a new element with index (r, c ) equal to v.
void swap_rows(int i, int j)
Swap rows i and j.
The IT++ file format reading and writing class.
imat mlist
List of integer coordinates in the m direction with non-zero entries.
void operator=(const GF2mat &X)
Assignment operator.
The IT++ file format reading class.
void set_row(int i, bvec x)
Set row i to a binary vector x.
int floor_i(double x)
The nearest smaller integer.
GF2mat operator*(const GF2mat &X, const GF2mat &Y)
GF(2) matrix multiplication.
int row_rank() const
Returns the number of linearly independent rows.
GF2mat_sparse sparsify() const
Create a sparse GF(2) matrix from a dense GF(2) matrix.
void add_rows(int i, int j)
Add (or equivalently, subtract) rows.
Definitions of special vectors and matrices.
void low_level_write(char x)
Write a char value at the current file pointer position.
Binary arithmetic (boolean) class.
void compact()
Set the maximum number of non-zero elements in each column equal to the actual number of non-zero ele...
#define it_error(s)
Abort unconditionally.
void transpose(const Mat< T > &m, Mat< T > &out)
Transposition of the matrix m returning the transposed matrix in out.
GF2mat transpose() const
Transpose.
void set_col(int j, bvec x)
Set column j to a binary vector x.
bvec get_col(int j) const
Get column.
int rows() const
Returns the number of rows of the sparse matrix.
void addto_element(int i, int j, bin s)
Add s (0 or 1) to element (i,j)
int N
Size of the matrix: M rows x N columns.
Definition of a class for algebra on GF(2) (binary) matrices.
GF2mat()
Default constructor (gives an empty 1 x 1 matrix)
GF2mat concatenate_horizontal(const GF2mat &X) const
Concatenate horizontally (append X on the right side of matrix)
GF2mat_sparse_alist()
Default constructor.
bvec bvecify() const
Create a bvec from a GF(2) matrix (must have one column or one row)
std::istream & operator>>(std::istream &input, bin &outbin)
Input stream of bin.
int max_num_n
Maximum weight of columns.
GF2mat_sparse to_sparse(bool transpose=false) const
Convert "alist" representation to GF2mat_sparse.
void permute_rows(ivec &perm, bool I)
Multiply from left with permutation matrix (permute rows).
bvec get_row(int i) const
Get row.
bool is_zero() const
Check whether the matrix is identical to zero.
Mat< bin > bmat
bin matrix
int cols() const
Returns the number of columns of the sparse matrix.
const Array< T > concat(const Array< T > &a, const T &e)
Append element e to the end of the Array a.