Permutations and Reordering
The following example shows how to use permutations:
#include <iostream> #include <boost/numeric/mtl/mtl.hpp> int main(int, char**) { using namespace mtl; double array[][3]= {{1., 2., 3.}, {4., 5., 6.}, {7., 8., 9.}}; dense2D<double> A(array), A2, A3; // Creating a permutation matrix from a vector (or an array respectively) int indices[]= {1, 2, 0}; matrix::traits::permutation<>::type P= matrix::permutation(indices); std::cout << "\nP =\n" << P; // Permutating rows A2= P * A; std::cout << "\nP * A =\n" << A2; // Permutating columns A3= A2 * trans(P); std::cout << "\nA2 * trans(P) =\n" << A3; dense_vector<double> v(array[2]), w(P * v); std::cout << "\nP * v =\n" << w << "\n"; return 0; }
The function matrix::permutation returns a sparse matrix computed from a permutation vector. The permutation vector is defined as where entries come from, i.e. v[i] == j means that the i-th entry/row/column after the permutation was the j-th entry/row/column before the permutation. If your vector is defined in the inverse manner -- i.e. i.e. v[i] == j signifies that the i-th entry/row/column before the permutation becomes the j-th entry/row/column after the permutation -- your permutation matrix is the transposed of what MTL4 computes: P= trans(matrix::permutation(v)).
Reordering is a generalization of permutation. The entries in the reorder vector/array are defined in the same fashion as in the permutation vector. However, the number of entries is not required to be equal to the set size of projectes indices. Therefore, the projected matrix/vector may have less rows or columns:
#include <iostream> #include <boost/numeric/mtl/mtl.hpp> int main(int, char**) { using namespace mtl; double array[][3]= {{1., 2., 3.}, {4., 5., 6.}, {7., 8., 9.}}; dense2D<double> A(array), B2, B3; // Creating a reordering matrix from a vector (or an array respectively) int indices[]= {2, 1}; matrix::traits::reorder<>::type R= matrix::reorder(indices); std::cout << "\nR =\n" << R; // Reorder rows B2= R * A; std::cout << "\nR * A =\n" << B2; // Reorder columns B3= B2 * trans(R); std::cout << "\nB2 * trans(R) =\n" << B3; dense_vector<double> v(array[2]), w(R * v); std::cout << "\nR * v =\n" << w << "\n"; return 0; }
Indices may appear repeatedly in the reorder vector implying that the respective rows/columns appear multiple times in the resulting matrix/vector:
#include <iostream> #include <boost/numeric/mtl/mtl.hpp> int main(int, char**) { using namespace mtl; double array[][3]= {{1., 2., 3.}, {4., 5., 6.}, {7., 8., 9.}}; dense2D<double> A(array), B2, B3; // Creating a reordering matrix from a vector (or an array respectively) int indices[]= {2, 1, 1, 2}; matrix::traits::reorder<>::type R= matrix::reorder(indices); std::cout << "\nR =\n" << R; // Reorder rows B2= R * A; std::cout << "\nR * A =\n" << B2; // Reorder columns B3= B2 * trans(R); std::cout << "\nB2 * trans(R) =\n" << B3; dense_vector<double> v(array[2]), w(R * v); std::cout << "\nR * v =\n" << w << "\n"; return 0; }
Reordering matrices can also be used to compress matrices as in the following example:
#include <iostream> #include <boost/numeric/mtl/mtl.hpp> int main(int, char**) { using namespace mtl; double array[][3]= {{1., 0., 3.}, {4., 0., 6.}, {7., 0., 9.}, {0., 0., 0.}}; dense2D<double> A(array), B2, B3; // Creating a compression (reordering) matrix from a vector (or an array respectively) int non_zero_rows[]= {0, 1, 2}, non_zero_columns[]= {0, 2}; // To be sure, we give the number of columns for a consistent size! matrix::traits::reorder<>::type RR= matrix::reorder(non_zero_rows, 4), RC= matrix::reorder(non_zero_columns); std::cout << "A =\n" << A << "\nRR =\n" << RR << "\nRC =\n" << RC; // Compress rows B2= RR * A; std::cout << "\nRR * A, i.e. compress row of A =\n" << B2; // Compress columns B3= B2 * trans(RC); std::cout << "\nB2 * trans(RC), i.e. compress columns of B2 =\n" << B3; // Decompress rows dense2D<double> C1(trans(RR) * B3); std::cout << "\ntrans(RR) * B3, i.e. row decompression of B3 =\n" << C1; // Decompress columns dense2D<double> C2(C1 * RC); std::cout << "\nC1 * RC, i.e. column decompression of C1 (should be A) =\n" << C2; return 0; }
The multiplication from right allows for eliminating empty rows and from left with the transposed for removing empty columns. The transposed of the compression matrices enable the decompression to yield the original matrices. If memory is an issue, one can also keep the compression vectors and the size of the original matrix and create the compression matrix on the fly.
dense2D<double> C1(trans(matrix::reorder(non_zero_rows, 4)) * B3), C2(C1 * matrix::reorder(non_zero_columns, 3));
For the definition of the row compression matrix we needed the explicit specification of the number of columns because the reorder matrix has by default the maximal entry plus one as column number (i.e. the minimum that is necessary). The number of columns of any reorder matrix -- not only compression -- must be equal the number of rows of the original matrix when multiplied from left and equal the original number of columns when multiplied from right as transposed. This is implicitly given when the last row or column is part of the resulting matrix. If you are not sure about this fact or the compression vector is calculated specify the reorder matrix' columnn number explicitly.
Return to Sub-matrices Table of Content Proceed to Banded Matrix View, Upper and Lower Triangular Views
Permutations and Reordering -- MTL 4 -- Peter Gottschling and Andrew Lumsdaine
-- Gen. with
rev. 7542
on Sat Aug 11 2012 by doxygen 1.7.6.1 -- © 2010 by SimuNova UG.