1. Blaze Avatar Blaze
  2. Blaze
  3. blaze
  4. Issues

Introduce non-contiguous views into Blaze

Issue #48 resolved
Klaus Iglberger created an issue

Description

So far the Blaze library only provides contiguous views on vectors (subvectors) and matrices (submatrices, rows, and columns). However, in many applications it is necessary to select specific rows, columns or elements from a vector or matrix. Therefore Blaze should also provide non-contiguous views on vectors and matrices.

Conceptual Example

Vector example

using blaze::StaticVector;

// Creating the vector ( 3 1 7 8 2 4 )
StaticVector<int,6UL> x{ 1, 2, 3, 4, 5, 6 };

// Selecting all elements with even index results in the vector ( 3 7 2 )
StaticVector<int,3UL> y = blaze::subvector( x, { 0, 2, 4 } );

// Selecting all elements with odd index results in the vector ( 1 8 4 )
StaticVector<int,3UL> z = blaze::subvector( x, { 1, 3, 5 } );

Matrix example

using blaze::StaticMatrix;

// Creating the matrix
// ( 2 1 3 7 )
// ( 1 4 1 2 )
// ( 5 1 6 8 )
StaticMatrix<int,3UL,4UL> A{ { 2, 1, 3, 7 },
                             { 1, 4, 1, 2 },
                             { 5, 1, 6, 8 } };

// Selecting the rows 0 and 2 results in the matrix
// ( 2 1 3 7 )
// ( 5 1 6 8 )
StaticMatrix<int,2UL,4UL> B = rows( A, { 0, 2 } );

// Selecting the columns 1 and 3 results in the matrix
// ( 1 7 )
// ( 4 2 )
// ( 1 8 )
StaticMatrix<int,3UL,2UL> C = columns( A, { 1, 3 } );

// Selecting both rows 0 and 2 and columns 1 and 3 results in the matrix
// ( 1 7 )
// ( 1 8 )
StaticMatrix<int,2UL,2UL> D = submatrix( A, { 0, 2 }, { 1, 3 } );

Tasks

  • implement non-contiguous subvector views for vectors
  • implement non-contiguous row views for matrices
  • implement non-contiguous column views for matrices
  • implement non-contiguous submatrix views for matrices
  • provide a full documentation for all non-contiguous views
  • ensure compatibility with all existing vector and matrix classes
  • ensure compatibility with all existing vector and matrix expressions
  • guarantee maximum performance for all operations
  • add test cases for the entire non-contiguous view functionality

Comments (12)

  1. Mark Lohry

    Klaus, I would find this extremely useful if I could create views that could be in random order (not necessarily increasing indices). e.g. from your matrix row example, I'd want to be able to do

    StaticMatrix<int,3UL,4UL> B = rows( A, { 0, 2, 1} );

    to create a view that looks like

    { { 2, 1, 3, 7 },
  { 5, 1, 6, 8 },
  { 1, 4, 1, 2 } }

    With unstructured mesh data I run into this frequently where I have to loop through a list of indices to address the rows needed one at a time. This would need to work for the DynamicVector/Matrix classes.

  2. Klaus Iglberger reporter

    Hi Mark!

    Thanks for the great suggestion. Based on our initial prototypes, this idea should work very well. Therefore we will definitely try to enable this feature.

    Best regards,

    Klaus!

  3. Mark Lohry

    Great to hear it! To be more verbose, I have a lot of code that ends up looking like this:

    void f( const vector<unsigned>& idx_left,
           const vector<unsigned>& idx_right,
           const Matrix& m_left,
           Matrix& m_right ){
 for (size_t i=0; i!=idx_left.size(); ++i){
     m_right.row( idx_right[i] ) = someFunction( m_left.row( idx_left[i] ) );
  }
}

    Where idx_right/idx_left indices will be in arbitrary order. I've never seen it in a C++ library, but Fortran arrays handle this natively and it's really nice:

    program main
real :: m_left(5), m_right(5), m_sum(3)
integer :: idx_left(3), idx_right(3)
m_left = (/10,20,30,40,50/)
m_right = (/100,200,300,400,500/)
idx_left = (/5,2,4/)
idx_right = (/1,5,1/)
write(*,*) m_left
write(*,*) idx_left, m_left(idx_left)
write(*,*) m_right
write(*,*) idx_right, m_right(idx_right)
call sum_submatrices( m_left(idx_left), m_right(idx_right), m_sum )
write(*,*) m_sum
end program main
subroutine sum_submatrices(left,right,output)
real :: left(3),right(3),output(3)
output = left + right
end subroutine sum_submatrices

    This comes up everywhere when dealing with unstructured mesh connectivity.

  6. Klaus Iglberger reporter

    Element Selections

    Element selections have been implemented, tested, optimized, and documented as required. The feature is immediately available via cloning the Blaze repository and will be officially released in Blaze 3.3.

    Element selections provide views on arbitrary compositions of elements of dense and sparse vectors. These views act as a reference to the selected elements and represent them as another dense or sparse vector. This reference is valid and can be used in every way any other dense or sparse vector can be used as long as the vector containing the elements is not resized or entirely destroyed. The element selection also acts as an alias to the vector elements in the specified range: Changes made to the elements (e.g. modifying values, inserting or erasing elements) are immediately visible in the vector and changes made via the vector are immediately visible in the elements.

    Setup of Element Selections

    An element selection can be created very conveniently via the elements() function. It can be included via the header file

    #include <blaze/math/Elements.h>

    The indices of the elements to be selected can be specified either at compile time or at runtime (by means of an initializer list, array or vector):

    blaze::DynamicVector<double,blaze::rowVector> x;
// ... Resizing and initialization

// Selecting the elements 4, 6, 8, and 10 (compile time arguments)
auto e1 = elements<4UL,6UL,8UL,10UL>( x );

// Selecting the elements 3, 2, and 1 (runtime arguments via an initializer list)
const std::initializer_list<size_t> list{ 3UL, 2UL, 1UL };
auto e2 = elements( x, { 3UL, 2UL, 1UL } );
auto e3 = elements( x, list );

// Selecting the elements 1, 2, 3, 3, 2, and 1 (runtime arguments via a std::array)
const std::array<size_t> array{ 1UL, 2UL, 3UL, 3UL, 2UL, 1UL };
auto e4 = elements( x, array );
auto e5 = elements( x, array.data(), array.size() );

// Selecting the element 4 fives times (runtime arguments via a std::vector)
const std::vector<size_t> vector{ 4UL, 4UL, 4UL, 4UL, 4UL };
auto e6 = elements( x, vector );
auto e7 = elements( x, vector.data(), vector.size() );

    Note that it is possible to alias the elements of the underlying vector in any order. Also note that it is possible to use the same index multiple times. The elements() function returns an expression representing the view on the selected elements. The type of this expression depends on the given arguments, primarily the type of the vector and the compile time arguments. If the type is required, it can be determined via decltype or via the ElementsExprTrait class template:

    using VectorType = blaze::DynamicVector<int>;

using ElementsType1 = decltype( blaze::elements<4UL,12UL>( std::declval<VectorType>() ) );
using ElementsType2 = blaze::ElementsExprTrait<VectorType,4UL,12UL>::Type;

    The resulting view can be treated as any other dense or sparse vector, i.e. it can be assigned to, it can be copied from, and it can be used in arithmetic operations. An element selection created from a row vector can be used as any other row vector, an element selection created from a column vector can be used as any other column vector. The view can also be used on both sides of an assignment: It can either be used as an alias to grant write access to specific elements of a vector primitive on the left-hand side of an assignment or to grant read-access to specific elements of a vector primitive or expression on the right-hand side of an assignment. The following example demonstrates this in detail:

    blaze::DynamicVector<double,blaze::rowVector> x;
blaze::CompressedVector<double,blaze::rowVector> y;
blaze::DynamicMatrix<double,blaze::rowMajor> A;
// ... Resizing and initialization

// Selecting the elements 1, 3, 5, and 7
auto e = elements( x, { 3UL, 5UL, 7UL, 9UL } );

// Setting the elements 1, 3, 5, and 7 of x to the 2nd row of matrix A
e = row( A, 2UL );

// Setting the elements 2, 4, 6, and 8 of x to y
elements( x, { 2UL, 4UL, 6UL, 8UL } ) = y;

// Setting the 3rd row of A to the elements 5, 4, 3, and 2 of x
row( A, 3UL ) = elements( x, { 5UL, 4UL, 3UL, 2UL } );

// Rotating the result of the addition between y and the 1st row of A
x = elements( y + row( A, 1UL ), { 2UL, 3UL, 0UL, 1UL } )

    Please note that using an element selection, which refers to an index multiple times, on the left-hand side of an assignment leads to undefined behavior:

    blaze::DynamicVector<int,blaze::rowVector> a{ 1, 2, 3 };
blaze::DynamicVector<int,blaze::rowVector> b{ 1, 2, 3, 4 };

auto e = elements( a, { 1, 1, 1, 1 } );  // Selecting the element 1 four times
e = b;  // Undefined behavior

    In this example both vectors have the same size, which results in a correct vector assignment, but the final value of the element at index 1 is unspecified.

    Element Access

    The elements of an element selection can be directly accessed via the subscript operator. The indices to access an element selection are zero-based:

    blaze::DynamicVector<double,blaze::rowVector> v;
// ... Resizing and initialization

// Selecting the elements 2, 4, 6, and 8
auto e = elements( v, { 2UL, 4UL, 6UL, 8UL } );

// Setting the 1st element of the element selection, which corresponds to
// the element at index 4 in vector v
e[1] = 2.0;

    Alternatively, the elements of an element selection can be traversed via iterators. Just as with vectors, in case of non-const element selections, begin() and end() return an iterator, which allows to manipulate the elements, in case of constant element selections an iterator to immutable elements is returned:

    blaze::DynamicVector<int,blaze::rowVector> v( 256UL );
// ... Resizing and initialization

// Creating an element selection including specific elements of dense vector v
auto e = elements( v, { 0UL, 3UL, 6UL, 9UL, 12UL } );

// Traversing the elements via iterators to non-const elements
for( auto it=e.begin(); it!=e.end(); ++it ) {
   *it = ...;  // OK: Write access to the dense vector value.
   ... = *it;  // OK: Read access to the dense vector value.
}

// Traversing the elements via iterators to const elements
for( auto it=e.cbegin(); it!=e.cend(); ++it ) {
   *it = ...;  // Compilation error: Assignment to the value via iterator-to-const is invalid.
   ... = *it;  // OK: Read access to the dense vector value.
}

    blaze::CompressedVector<int,blaze::rowVector> v( 256UL );
// ... Resizing and initialization

// Creating an element selection including specific elements of sparse vector v
auto e = elements( v, { 0UL, 3UL, 6UL, 9UL, 12UL } );

// Traversing the elements via iterators to non-const elements
for( auto it=e.begin(); it!=e.end(); ++it ) {
   it->value() = ...;  // OK: Write access to the value of the non-zero element.
   ... = it->value();  // OK: Read access to the value of the non-zero element.
   it->index() = ...;  // Compilation error: The index of a non-zero element cannot be changed.
   ... = it->index();  // OK: Read access to the index of the sparse element.
}

// Traversing the elements via iterators to const elements
for( auto it=e.cbegin(); it!=e.cend(); ++it ) {
   it->value() = ...;  // Compilation error: Assignment to the value via iterator-to-const is invalid.
   ... = it->value();  // OK: Read access to the value of the non-zero element.
   it->index() = ...;  // Compilation error: The index of a non-zero element cannot be changed.
   ... = it->index();  // OK: Read access to the index of the sparse element.
}

    Element Insertion

    Inserting/accessing elements in a sparse element selection can be done by several alternative functions. The following example demonstrates all options:

    blaze::CompressedVector<double,blaze::rowVector> v( 256UL );  // Non-initialized vector of size 256

std::vector<size_t> indices;
// ... Selecting indices of the sparse vector

auto e = elements( v, indices );

// The subscript operator provides access to the selected elements of the sparse vector,
// including the zero elements. In case the subscript operator is used to access an element
// that is currently not stored in the sparse vector, the element is inserted.
e[42] = 2.0;

// The second operation for inserting elements via the element selection is the set() function.
// In case the element is not contained in the vector it is inserted into the vector, if it is
// already contained in the vector its value is modified.
e.set( 45UL, -1.2 );

// An alternative for inserting elements into the vector is the insert() function. However, it
// inserts the element only in case the element is not already contained in the vector.
e.insert( 50UL, 3.7 );

// Just as in case of vectors, elements can also be inserted via the append() function. In case
// of element selections, append() also requires that the appended element's index is strictly
// larger than the currently largest non-zero index of the selection and that the selections's
// capacity is large enough to hold the new element. Note however that due to the nature of an
// element selection, which is an alias to arbitrary elements of a sparse vector, the append()
// function does not work as efficiently for an element selection as it does for a vector.
e.reserve( 10UL );
e.append( 51UL, -2.1 );

    Common Operations

    An element selection can be used like any other dense or sparse vector. For instance, the number of selected elements can be obtained via the size() function, the current capacity via the capacity() function, and the number of non-zero elements via the nonZeros() function. However, since element selections are references to a specific range of a vector, several operations are not possible, such as resizing and swapping. The following example shows this by means of an element selection on a dense vector:

    blaze::DynamicVector<int,blaze::rowVector> v( 42UL );
// ... Resizing and initialization

// Selecting the elements 5 and 10
auto e = elements( v, { 5UL, 10UL } );

e.size();          // Returns the number of elements in the element selection
e.capacity();      // Returns the capacity of the element selection
e.nonZeros();      // Returns the number of non-zero elements contained in the element selection

e.resize( 84UL );  // Compilation error: Cannot resize an element selection

auto e2 = elements( v, { 15UL, 10UL } );
swap( e, e2 );   // Compilation error: Swap operation not allowed

    Arithmetic Operations

    Both dense and sparse element selections can be used in all arithmetic operations that any other dense or sparse vector can be used in. The following example gives an impression of the use of dense element selections within arithmetic operations. All operations (addition, subtraction, multiplication, scaling, ...) can be performed on all possible combinations of dense and sparse element selections with fitting element types:

    blaze::DynamicVector<double,blaze::rowVector> d1, d2, d3;
blaze::CompressedVector<double,blaze::rowVector> s1, s2;

// ... Resizing and initialization

blaze::DynamicMatrix<double,blaze::rowMajor> A;

std::initializer_list<size_t> indices1{ 0UL, 3UL, 6UL,  9UL, 12UL, 15UL, 18UL, 21UL };
std::initializer_list<size_t> indices2{ 1UL, 4UL, 7UL, 10UL, 13UL, 16UL, 19UL, 22UL };
std::initializer_list<size_t> indices3{ 2UL, 5UL, 8UL, 11UL, 14UL, 17UL, 20UL, 23UL };

auto e( elements( d1, indices1 ) );  // Selecting the every third element of d1 in the range [0..21]

e = d2;                         // Dense vector assignment to the selected elements
elements( d1, indices2 ) = s1;  // Sparse vector assignment to the selected elements

d3 = e + d2;                         // Dense vector/dense vector addition
s2 = s1 + elements( d1, indices2 );  // Sparse vector/dense vector addition
d2 = e * elements( d1, indices3 );   // Component-wise vector multiplication

elements( d1, indices2 ) *= 2.0;      // In-place scaling of the second selection of elements
d2 = elements( d1, indices3 ) * 2.0;  // Scaling of the elements in the third selection of elements
d2 = 2.0 * elements( d1, indices3 );  // Scaling of the elements in the third selection of elements

elements( d1, indices1 ) += d2;  // Addition assignment
elements( d1, indices2 ) -= s2;  // Subtraction assignment
elements( d1, indices3 ) *= e;   // Multiplication assignment

double scalar = elements( d1, indices2 ) * trans( s1 );  // Scalar/dot/inner product between two vectors

A = trans( s1 ) * elements( d1, { 3UL, 6UL } );  // Outer product between two vectors
  8. Evan Berkowitz

    This will be great! Is there an ETA for this?

    It'd be nice to have (possibly optimized) strided views, which are non-contiguous but still structured views without having to construct the list of indices oneself.

  9. Klaus Iglberger reporter

    Row Selections

    Row selections provide views on arbitrary compositions of rows of dense and sparse matrices. These views act as a reference to the selected rows and represent them as another dense or sparse matrix. This reference is valid and can be used in every way any other dense or sparse matrix can be used as long as the matrix containing the rows is not resized or entirely destroyed. The row selection also acts as an alias to the matrix elements in the specified range: Changes made to the rows (e.g. modifying values, inserting or erasing elements) are immediately visible in the matrix and changes made via the matrix are immediately visible in the rows.

    Setup of Row Selections

    A row selection can be created very conveniently via the rows() function. It can be included via the header file

    #include <blaze/math/Rows.h>

    The indices of the rows to be selected can be specified either at compile time or at runtime (by means of an initializer list, array or vector):

    blaze::DynamicMatrix<double,blaze::rowMajor> A;
// ... Resizing and initialization

// Selecting the rows 4, 6, 8, and 10 (compile time arguments)
auto rs1 = rows<4UL,6UL,8UL,10UL>( A );

// Selecting the rows 3, 2, and 1 (runtime arguments via an initializer list)
const std::initializer_list<size_t> list{ 3UL, 2UL, 1UL };
auto rs2 = rows( A, { 3UL, 2UL, 1UL } );
auto rs3 = rows( A, list );

// Selecting the rows 1, 2, 3, 3, 2, and 1 (runtime arguments via a std::array)
const std::array<size_t> array{ 1UL, 2UL, 3UL, 3UL, 2UL, 1UL };
auto rs4 = rows( A, array );
auto rs5 = rows( A, array.data(), array.size() );

// Selecting the row 4 fives times (runtime arguments via a std::vector)
const std::vector<size_t> vector{ 4UL, 4UL, 4UL, 4UL, 4UL };
auto rs6 = rows( A, vector );
auto rs7 = rows( A, vector.data(), vector.size() );

    Note that it is possible to alias the rows of the underlying matrix in any order. Also note that it is possible to use the same index multiple times. The rows() function returns an expression representing the view on the selected rows. The type of this expression depends on the given arguments, primarily the type of the matrix and the compile time arguments. If the type is required, it can be determined via decltype or via the RowsExprTrait class template:

    using MatrixType = blaze::DynamicMatrix<int>;

using RowsType1 = decltype( blaze::rows<3UL,0UL,4UL,8UL>( std::declval<MatrixType>() ) );
using RowsType2 = blaze::RowsExprTrait<MatrixType,3UL,0UL,4UL,8UL>::Type;

    The resulting view can be treated as any other dense or sparse matrix, i.e. it can be assigned to, it can be copied from, and it can be used in arithmetic operations. Note, however, that a row selection will always be treated as a row-major matrix, regardless of the storage order of the matrix containing the rows. The view can also be used on both sides of an assignment: It can either be used as an alias to grant write access to specific rows of a matrix primitive on the left-hand side of an assignment or to grant read-access to specific rows of a matrix primitive or expression on the right-hand side of an assignment. The following example demonstrates this in detail:

    blaze::DynamicMatrix<double,blaze::rowMajor> A;
blaze::DynamicMatrix<double,blaze::columnMajor> B;
blaze::CompressedMatrix<double,blaze::rowMajor> C;
// ... Resizing and initialization

// Selecting the rows 1, 3, 5, and 7 of A
auto rs = rows( A, { 1UL, 3UL, 5UL, 7UL } );

// Setting rows 1, 3, 5, and 7 of A to row 4 of B
rs = rows( B, { 4UL, 4UL, 4UL, 4UL } );

// Setting the rows 2, 4, 6, and 8 of A to C
rows( A, { 2UL, 4UL, 6UL, 8UL } ) = C;

// Setting the first 4 rows of A to the rows 5, 4, 3, and 2 of C
submatrix( A, 0UL, 0UL, 4UL, A.columns() ) = rows( C, { 5UL, 4UL, 3UL, 2UL } );

// Rotating the result of the addition between rows 1, 3, 5, and 7 of A and C
B = rows( rs + C, { 2UL, 3UL, 0UL, 1UL } );

    Element Access

    The elements of a row selection can be directly accessed via the function call operator:

    blaze::DynamicMatrix<double,blaze::rowMajor> A;
// ... Resizing and initialization

// Creating a view on the first four rows of A in reverse order
auto rs = rows( A, { 3UL, 2UL, 1UL, 0UL } );

// Setting the element (0,0) of the row selection, which corresponds
// to the element at position (3,0) in matrix A
rs(0,0) = 2.0;

    Alternatively, the elements of a row selection can be traversed via (const) iterators. Just as with matrices, in case of non-const row selection, begin() and end() return an iterator, which allows to manipuate the elements, in case of constant row selection an iterator to immutable elements is returned:

    blaze::DynamicMatrix<int,blaze::rowMajor> A( 256UL, 512UL );
// ... Resizing and initialization

// Creating a reference to a selection of rows of matrix A
auto rs = rows( A, { 16UL, 32UL, 64UL, 128UL } );

// Traversing the elements of the 0th row via iterators to non-const elements
for( auto it=rs.begin(0); it!=rs.end(0); ++it ) {
   *it = ...;  // OK: Write access to the dense value.
   ... = *it;  // OK: Read access to the dense value.
}

// Traversing the elements of the 1st row via iterators to const elements
for( auto it=rs.cbegin(1); it!=rs.cend(1); ++it ) {
   *it = ...;  // Compilation error: Assignment to the value via iterator-to-const is invalid.
   ... = *it;  // OK: Read access to the dense value.
}

    blaze::CompressedMatrix<int,blaze::rowMajor> A( 256UL, 512UL );
// ... Resizing and initialization

// Creating a reference to a selection of rows of matrix A
auto rs = rows( A, { 16UL, 32UL, 64UL, 128UL } );

// Traversing the elements of the 0th row via iterators to non-const elements
for( auto it=rs.begin(0); it!=rs.end(0); ++it ) {
   it->value() = ...;  // OK: Write access to the value of the non-zero element.
   ... = it->value();  // OK: Read access to the value of the non-zero element.
   it->index() = ...;  // Compilation error: The index of a non-zero element cannot be changed.
   ... = it->index();  // OK: Read access to the index of the sparse element.
}

// Traversing the elements of the 1st row via iterators to const elements
for( auto it=rs.cbegin(1); it!=rs.cend(1); ++it ) {
   it->value() = ...;  // Compilation error: Assignment to the value via iterator-to-const is invalid.
   ... = it->value();  // OK: Read access to the value of the non-zero element.
   it->index() = ...;  // Compilation error: The index of a non-zero element cannot be changed.
   ... = it->index();  // OK: Read access to the index of the sparse element.
}

    Element Insertion

    Inserting/accessing elements in a sparse row selection can be done by several alternative functions. The following example demonstrates all options:

    blaze::CompressedMatrix<double,blaze::rowMajor> A( 256UL, 512UL );  // Non-initialized matrix of size 256x512

auto rs = rows( A, { 10UL, 20UL, 30UL, 40UL } );  // View on the rows 10, 20, 30, and 40 of A

// The function call operator provides access to all possible elements of the sparse row
// selection, including the zero elements. In case the function call operator is used to
// access an element that is currently not stored in the sparse row selection, the element
// is inserted into the row selection.
rs(2,4) = 2.0;

// The second operation for inserting elements is the set() function. In case the element is
// not contained in the row selection it is inserted into the row selection, if it is already
// contained in the row selection its value is modified.
rs.set( 2UL, 5UL, -1.2 );

// An alternative for inserting elements into the row selection is the insert() function.
// However, it inserts the element only in case the element is not already contained in the
// row selection.
rs.insert( 2UL, 6UL, 3.7 );

// Just as in the case of sparse matrices, elements can also be inserted via the append()
// function. In case of row selections, append() also requires that the appended element's
// index is strictly larger than the currently largest non-zero index in the according row
// of the row selection and that the according row's capacity is large enough to hold the new
// element. Note however that due to the nature of a row selection, which may be an alias to
// an arbitrary collection of rows, the append() function does not work as efficiently for
// a row selection as it does for a matrix.
rs.reserve( 2UL, 10UL );
rs.append( 2UL, 10UL, -2.1 );

    Common Operations

    A view on specific rows of a matrix can be used like any other dense or sparse matrix. For instance, the current size of the matrix, i.e. the number of rows or columns can be obtained via the rows() and columns() functions, the current total capacity via the capacity() function, and the number of non-zero elements via the nonZeros() function. However, since row selections are views on specific rows of a matrix, several operations are not possible, such as resizing and swapping:

    blaze::DynamicMatrix<int,blaze::rowMajor> A( 42UL, 42UL );
// ... Resizing and initialization

// Creating a view on the rows 8, 16, 24, and 32 of matrix A
auto rs = rows( A, { 8UL, 16UL, 24UL, 32UL } );

rs.rows();      // Returns the number of rows of the row selection
rs.columns();   // Returns the number of columns of the row selection
rs.capacity();  // Returns the capacity of the row selection
rs.nonZeros();  // Returns the number of non-zero elements contained in the row selection

rs.resize( 10UL, 8UL );  // Compilation error: Cannot resize a row selection

auto rs2 = rows( A, 9UL, 17UL, 25UL, 33UL );
swap( rs, rs2 );  // Compilation error: Swap operation not allowed

    Arithmetic Operations

    Both dense and sparse row selections can be used in all arithmetic operations that any other dense or sparse matrix can be used in. The following example gives an impression of the use of dense row selctions within arithmetic operations. All operations (addition, subtraction, multiplication, scaling, ...) can be performed on all possible combinations of dense and sparse matrices with fitting element types:

    blaze::DynamicMatrix<double,blaze::rowMajor> D1, D2, D3;
blaze::CompressedMatrix<double,blaze::rowMajor> S1, S2;

blaze::CompressedVector<double,blaze::columnVector> a, b;

// ... Resizing and initialization

std::initializer_list<size_t> indices1{ 0UL, 3UL, 6UL,  9UL, 12UL, 15UL, 18UL, 21UL };
std::initializer_list<size_t> indices2{ 1UL, 4UL, 7UL, 10UL, 13UL, 16UL, 19UL, 22UL };
std::initializer_list<size_t> indices3{ 2UL, 5UL, 8UL, 11UL, 14UL, 17UL, 20UL, 23UL };

auto rs = rows( D1, indices1 );  // Selecting the every third row of D1 in the range [0..21]

rs = D2;                    // Dense matrix assignment to the selected rows
rows( D1, indices2 ) = S1;  // Sparse matrix assignment to the selected rows

D3 = rs + D2;                    // Dense matrix/dense matrix addition
S2 = S1 - rows( D1, indices2 );  // Sparse matrix/dense matrix subtraction
D2 = rs % rows( D1, indices3 );  // Dense matrix/dense matrix Schur product
D2 = rows( D1, indices2 ) * D1;  // Dense matrix/dense matrix multiplication

rows( D1, indices2 ) *= 2.0;      // In-place scaling of the second selection of rows
D2 = rows( D1, indices3 ) * 2.0;  // Scaling of the elements in the third selection of rows
D2 = 2.0 * rows( D1, indices3 );  // Scaling of the elements in the third selection of rows

rows( D1, indices1 ) += D2;  // Addition assignment
rows( D1, indices2 ) -= S1;  // Subtraction assignment
rows( D1, indices3 ) %= rs;  // Schur product assignment

a = rows( D1, indices1 ) * b;  // Dense matrix/sparse vector multiplication

    Row Selections on Column-Major Matrices

    Especially noteworthy is that row selections can be created for both row-major and column-major matrices. Whereas the interface of a row-major matrix only allows to traverse a row directly and the interface of a column-major matrix only allows to traverse a column, via views it is possible to traverse a row of a column-major matrix or a column of a row-major matrix. For instance:

    blaze::DynamicMatrix<int,blaze::columnMajor> A( 64UL, 32UL );
// ... Resizing and initialization

// Creating a reference to the 1st and 3rd row of a column-major matrix A
auto rs = rows( A, { 1UL, 3UL } );

// Traversing row 0 of the selection, which corresponds to the 1st row of matrix A
for( auto it=rs.begin( 0UL ); it!=rs.end( 0UL ); ++it ) {
   // ...
}

    However, please note that creating a row selection on a matrix stored in a column-major fashion can result in a considerable performance decrease in comparison to a row selection on a matrix with row-major storage format. This is due to the non-contiguous storage of the matrix elements. Therefore care has to be taken in the choice of the most suitable storage order:

    // Setup of two column-major matrices
blaze::DynamicMatrix<double,blaze::columnMajor> A( 128UL, 128UL );
blaze::DynamicMatrix<double,blaze::columnMajor> B( 128UL, 128UL );
// ... Resizing and initialization

// The computation of the 15th, 30th, and 45th row of the multiplication between A and B ...
blaze::DynamicMatrix<double,blaze::rowMajor> x = rows( A * B, { 15UL, 30UL, 45UL } );

// ... is essentially the same as the following computation, which multiplies
// the 15th, 30th, and 45th row of the column-major matrix A with B.
blaze::DynamicMatrix<double,blaze::rowMajor> x = rows( A, { 15UL, 30UL, 45UL } ) * B;

    Although Blaze performs the resulting matrix/matrix multiplication as efficiently as possible using a row-major storage order for matrix A would result in a more efficient evaluation.

  10. Klaus Iglberger reporter

    Column Selections

    Column selections provide views on arbitrary compositions of columns of dense and sparse matrices. These views act as a reference to the selected columns and represent them as another dense or sparse matrix. This reference is valid and can be used in every way any other dense or sparse matrix can be used as long as the matrix containing the columns is not resized or entirely destroyed. The column selection also acts as an alias to the matrix elements in the specified range: Changes made to the columns (e.g. modifying values, inserting or erasing elements) are immediately visible in the matrix and changes made via the matrix are immediately visible in the columns.

    Setup of Column Selections

    A column selection can be created very conveniently via the columns() function. It can be included via the header file

    #include <blaze/math/Columns.h>

    The indices of the columns to be selected can be specified either at compile time or at runtime (by means of an initializer list, array or vector):

    blaze::DynamicMatrix<double,blaze::columnMajor> A;
// ... Resizing and initialization

// Selecting the columns 4, 6, 8, and 10 (compile time arguments)
auto cs1 = columns<4UL,6UL,8UL,10UL>( A );

// Selecting the columns 3, 2, and 1 (runtime arguments via an initializer list)
const std::initializer_list<size_t> list{ 3UL, 2UL, 1UL };
auto cs2 = columns( A, { 3UL, 2UL, 1UL } );
auto cs3 = columns( A, list );

// Selecting the columns 1, 2, 3, 3, 2, and 1 (runtime arguments via a std::array)
const std::array<size_t> array{ 1UL, 2UL, 3UL, 3UL, 2UL, 1UL };
auto cs4 = columns( A, array );
auto cs5 = columns( A, array.data(), array.size() );

// Selecting the column 4 fives times (runtime arguments via a std::vector)
const std::vector<size_t> vector{ 4UL, 4UL, 4UL, 4UL, 4UL };
auto cs6 = columns( A, vector );
auto cs7 = columns( A, vector.data(), vector.size() );

    Note that it is possible to alias the columns of the underlying matrix in any order. Also note that it is possible to use the same index multiple times. The columns() function returns an expression representing the view on the selected columns. The type of this expression depends on the given arguments, primarily the type of the matrix and the compile time arguments. If the type is required, it can be determined via decltype or via the ColumnsExprTrait class template:

    using MatrixType = blaze::DynamicMatrix<int>;

using ColumnsType1 = decltype( blaze::columns<3UL,0UL,4UL,8UL>( std::declval<MatrixType>() ) );
using ColumnsType2 = blaze::ColumnsExprTrait<MatrixType,3UL,0UL,4UL,8UL>::Type;

    The resulting view can be treated as any other dense or sparse matrix, i.e. it can be assigned to, it can be copied from, and it can be used in arithmetic operations. Note, however, that a column selection will always be treated as a column-major matrix, regardless of the storage order of the matrix containing the columns. The view can also be used on both sides of an assignment: It can either be used as an alias to grant write access to specific columns of a matrix primitive on the left-hand side of an assignment or to grant read-access to specific columns of a matrix primitive or expression on the right-hand side of an assignment. The following example demonstrates this in detail:

    blaze::DynamicMatrix<double,blaze::columnMajor> A;
blaze::DynamicMatrix<double,blaze::rowMajor> B;
blaze::CompressedMatrix<double,blaze::columnMajor> C;
// ... Resizing and initialization

// Selecting the columns 1, 3, 5, and 7 of A
auto cs = columns( A, { 1UL, 3UL, 5UL, 7UL } );

// Setting columns 1, 3, 5, and 7 of A to column 4 of B
cs = columns( B, { 4UL, 4UL, 4UL, 4UL } );

// Setting the columns 2, 4, 6, and 8 of A to C
columns( A, { 2UL, 4UL, 6UL, 8UL } ) = C;

// Setting the first 4 columns of A to the columns 5, 4, 3, and 2 of C
submatrix( A, 0UL, 0UL, A.rows(), 4UL ) = columns( C, { 5UL, 4UL, 3UL, 2UL } );

// Rotating the result of the addition between columns 1, 3, 5, and 7 of A and C
B = columns( cs + C, { 2UL, 3UL, 0UL, 1UL } );

    Element access

    The elements of a column selection can be directly accessed via the function call operator:

    blaze::DynamicMatrix<double,blaze::columnMajor> A;
// ... Resizing and initialization

// Creating a view on the first four columns of A in reverse order
auto cs = columns( A, { 3UL, 2UL, 1UL, 0UL } );

// Setting the element (0,0) of the column selection, which corresponds
// to the element at position (0,3) in matrix A
cs(0,0) = 2.0;

    Alternatively, the elements of a column selection can be traversed via (const) iterators. Just as with matrices, in case of non-const column selection, begin() and end() return an iterator, which allows to manipuate the elements, in case of constant column selection an iterator to immutable elements is returned:

    blaze::DynamicMatrix<int,blaze::columnMajor> A( 512UL, 256UL );
// ... Resizing and initialization

// Creating a reference to a selection of columns of matrix A
auto cs = columns( A, { 16UL, 32UL, 64UL, 128UL } );

// Traversing the elements of the 0th column via iterators to non-const elements
for( auto it=cs.begin(0); it!=cs.end(0); ++it ) {
   *it = ...;  // OK: Write access to the dense value.
   ... = *it;  // OK: Read access to the dense value.
}

// Traversing the elements of the 1st column via iterators to const elements
for( auto it=cs.cbegin(1); it!=cs.cend(1); ++it ) {
   *it = ...;  // Compilation error: Assignment to the value via iterator-to-const is invalid.
   ... = *it;  // OK: Read access to the dense value.
}

    blaze::CompressedMatrix<int,blaze::columnMajor> A( 512UL, 256UL );
// ... Resizing and initialization

// Creating a reference to a selection of columns of matrix A
auto cs = columns( A, { 16UL, 32UL, 64UL, 128UL } );

// Traversing the elements of the 0th column via iterators to non-const elements
for( auto it=cs.begin(0); it!=cs.end(0); ++it ) {
   it->value() = ...;  // OK: Write access to the value of the non-zero element.
   ... = it->value();  // OK: Read access to the value of the non-zero element.
   it->index() = ...;  // Compilation error: The index of a non-zero element cannot be changed.
   ... = it->index();  // OK: Read access to the index of the sparse element.
}

// Traversing the elements of the 1st column via iterators to const elements
for( auto it=cs.cbegin(1); it!=cs.cend(1); ++it ) {
   it->value() = ...;  // Compilation error: Assignment to the value via iterator-to-const is invalid.
   ... = it->value();  // OK: Read access to the value of the non-zero element.
   it->index() = ...;  // Compilation error: The index of a non-zero element cannot be changed.
   ... = it->index();  // OK: Read access to the index of the sparse element.
}

    Element Insertion

    Inserting/accessing elements in a sparse column selection can be done by several alternative functions. The following example demonstrates all options:

    blaze::CompressedMatrix<double,blaze::columnMajor> A( 512UL, 256UL );  // Non-initialized matrix of size 512x256

auto cs = columns( A, { 10UL, 20UL, 30UL, 40UL } );  // View on the columns 10, 20, 30, and 40 of A

// The function call operator provides access to all possible elements of the sparse column
// selection, including the zero elements. In case the function call operator is used to
// access an element that is currently not stored in the sparse column selection, the element
// is inserted into the column selection.
cs(2,4) = 2.0;

// The second operation for inserting elements is the set() function. In case the element is
// not contained in the column selection it is inserted into the column selection, if it is
// already contained in the column selection its value is modified.
cs.set( 2UL, 5UL, -1.2 );

// An alternative for inserting elements into the column selection is the insert() function.
// However, it inserts the element only in case the element is not already contained in the
// column selection.
cs.insert( 2UL, 6UL, 3.7 );

// Just as in the case of sparse matrices, elements can also be inserted via the append()
// function. In case of column selections, append() also requires that the appended element's
// index is strictly larger than the currently largest non-zero index in the according column
// of the column selection and that the according column's capacity is large enough to hold the
// new element. Note however that due to the nature of a column selection, which may be an alias
// to an arbitrary collection of columns, the append() function does not work as efficiently
// for a column selection as it does for a matrix.
cs.reserve( 2UL, 10UL );
cs.append( 2UL, 10UL, -2.1 );

    Common Operations

    A view on specific columns of a matrix can be used like any other dense or sparse matrix. For instance, the current size of the matrix, i.e. the number of rows or columns can be obtained via the rows() and columns() functions, the current total capacity via the capacity() function, and the number of non-zero elements via the nonZeros() function. However, since column selections are views on specific columns of a matrix, several operations are not possible, such as resizing and swapping:

    blaze::DynamicMatrix<int,blaze::columnMajor> A( 42UL, 42UL );
// ... Resizing and initialization

// Creating a view on the columns 8, 16, 24, and 32 of matrix A
auto cs = columns( A, { 8UL, 16UL, 24UL, 32UL } );

cs.rows();      // Returns the number of rows of the column selection
cs.columns();   // Returns the number of columns of the column selection
cs.capacity();  // Returns the capacity of the column selection
cs.nonZeros();  // Returns the number of non-zero elements contained in the column selection

cs.resize( 10UL, 8UL );  // Compilation error: Cannot resize a column selection

auto cs2 = columns( A, 9UL, 17UL, 25UL, 33UL );
swap( cs, cs2 );  // Compilation error: Swap operation not allowed

    Arithmetic Operations

    Both dense and sparse column selections can be used in all arithmetic operations that any other dense or sparse matrix can be used in. The following example gives an impression of the use of dense column selctions within arithmetic operations. All operations (addition, subtraction, multiplication, scaling, ...) can be performed on all possible combinations of dense and sparse matrices with fitting element types:

    blaze::DynamicMatrix<double,blaze::columnMajor> D1, D2, D3;
blaze::CompressedMatrix<double,blaze::columnMajor> S1, S2;

blaze::CompressedVector<double,blaze::columnVector> a, b;

// ... Resizing and initialization

std::initializer_list<size_t> indices1{ 0UL, 3UL, 6UL,  9UL, 12UL, 15UL, 18UL, 21UL };
std::initializer_list<size_t> indices2{ 1UL, 4UL, 7UL, 10UL, 13UL, 16UL, 19UL, 22UL };
std::initializer_list<size_t> indices3{ 2UL, 5UL, 8UL, 11UL, 14UL, 17UL, 20UL, 23UL };

auto cs = columns( D1, indices1 );  // Selecting the every third column of D1 in the range [0..21]

cs = D2;                       // Dense matrix assignment to the selected columns
columns( D1, indices2 ) = S1;  // Sparse matrix assignment to the selected columns

D3 = cs + D2;                       // Dense matrix/dense matrix addition
S2 = S1 - columns( D1, indices2 );  // Sparse matrix/dense matrix subtraction
D2 = cs % columns( D1, indices3 );  // Dense matrix/dense matrix Schur product
D2 = columns( D1, indices2 ) * D1;  // Dense matrix/dense matrix multiplication

columns( D1, indices2 ) *= 2.0;      // In-place scaling of the second selection of columns
D2 = columns( D1, indices3 ) * 2.0;  // Scaling of the elements in the third selection of columns
D2 = 2.0 * columns( D1, indices3 );  // Scaling of the elements in the third selection of columns

columns( D1, indices1 ) += D2;  // Addition assignment
columns( D1, indices2 ) -= S1;  // Subtraction assignment
columns( D1, indices3 ) %= cs;  // Schur product assignment

a = columns( D1, indices1 ) * b;  // Dense matrix/sparse vector multiplication

    Column Selections on a Row-Major Matrix

    Especially noteworthy is that column selections can be created for both row-major and column-major matrices. Whereas the interface of a row-major matrix only allows to traverse a row directly and the interface of a column-major matrix only allows to traverse a column, via views it is possible to traverse a row of a column-major matrix or a column of a row-major matrix. For instance:

    blaze::DynamicMatrix<int,blaze::rowMajor> A( 64UL, 32UL );
// ... Resizing and initialization

// Creating a reference to the 1st and 3rd column of a column-major matrix A
auto cs = columns( A, { 1UL, 3UL } );

// Traversing column 0 of the selection, which corresponds to the 1st column of matrix A
for( auto it=cs.begin( 0UL ); it!=cs.end( 0UL ); ++it ) {
   // ...
}

    However, please note that creating a column selection on a matrix stored in a row-major fashion can result in a considerable performance decrease in comparison to a column selection on a matrix with column-major storage format. This is due to the non-contiguous storage of the matrix elements. Therefore care has to be taken in the choice of the most suitable storage order:

    // Setup of two row-major matrices
blaze::DynamicMatrix<double,blaze::rowMajor> A( 128UL, 128UL );
blaze::DynamicMatrix<double,blaze::rowMajor> B( 128UL, 128UL );
// ... Resizing and initialization

// The computation of the 15th, 30th, and 45th column of the multiplication between A and B ...
blaze::DynamicMatrix<double,blaze::columnMajor> x = columns( A * B, { 15UL, 30UL, 45UL } );

// ... is essentially the same as the following computation, which multiplies
// A with the 15th, 30th, and 45th column of the row-major matrix B.
blaze::DynamicMatrix<double,blaze::columnMajor> x = A * column( B, { 15UL, 30UL, 45UL } );

    Although Blaze performs the resulting matrix/matrix multiplication as efficiently as possible using a column-major storage order for matrix A would result in a more efficient evaluation.

  11. Klaus Iglberger reporter

    Element selections, row selections, and column selections have been implemented, tested, optimized, and documented as required. They are immediately available via cloning the Blaze repository and will be officially released in Blaze 3.3.

  13. Log in to comment
Assignee
Type
enhancement
Priority
major
Status
resolved
Votes
2
Watchers
6
Jira: the preferred issue tracker for Bitbucket. Join the team!