Introduce reduction operations into Blaze

[Klaus Iglberger]

Description

The Blaze library should provide reduction operations. More specifically, it should be possible to ...

• ... reduce dense and sparse vectors to scalars
• ... reduce dense and sparse matrices to scalars
• ... reduce dense and sparse matrices row-wise to column vectors
• ... reduce dense and sparse matrices column-wise to row vectors

Initially, Blaze should support sum() and prod() reductions. Conceptually, this could work as follows:

Vector example

// Creating the vector ( 1 2 3 4 )
blaze::StaticVector<int,4UL> x( 1, 2, 3, 4 );

// Reduction to a scalar value
const int s = sum ( x );  // Results in 10
const int p = prod( x );  // Results in 24

Matrix example

// Creating the matrix
// ( 2 1 3 )
// ( 1 4 1 )
// ( 5 1 6 )
blaze::StaticMatrix<int,3UL,3UL> A( 2, 1, 3,
                                    1, 4, 1
                                    5, 1, 6 );

// Reduction to a scalar value
const int s = sum ( A );  // Results in 24
const int p = prod( A );  // Results in 720

// Reduction to a column vector
blaze::StaticVector<int,3UL,blaze::columnVector> col;
col = sum<byRow> ( A );  // Results in ( 6 6 12 )
col = prod<byRow>( A );  // Results in ( 6 4 30 )

// Reduction to a row vector
blaze::StaticVector<int,3UL,blaze::rowVector> row;
row = sum<byColumn> ( A );  // Results in ( 8 6 10 );
row = prod<byColumn>( A );  // Results in ( 10 4 18 )

Tasks

• implement reduction operations for dense and sparse vectors
• implement reduction operations for dense and sparse matrices
• provide a full documentation of reduction operations
• 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 reduction operation functionality

[Marcin Junczys-Dowmunt]

How about an efficient softmax for the neural network people?

[Klaus Iglberger]

Great idea, thanks a lot.

[Klaus Iglberger]

Issue #122 was marked as a duplicate of this issue.

[gergol]

Just wanted to bump this as I think this is extremely useful functionality (or it's absence is even a show-stopper for many use cases) . Perhaps a more generic approach with optional custom reduction kernel could be considered. (Eigen tensor has this for example).

[Klaus Iglberger]

Hi Gergol!

Thanks for the note. This topic is pretty high on our list and we will try to provide a fast and flexible solution within the next months.

Best regards,

Klaus!

[gergol]

Thanks for the info, that's great news!

[Klaus Iglberger]

Hi Marcin!

Thanks again for sharing the idea to introduce a softmax() function. In order to preserve the idea and to share an initial implementation, we have created the follow-up issue #192. Please feel free to watch this issue to keep track of our progress.

Best regards,

Klaus!

[Klaus Iglberger]

Summary

The feature has been implemented, tested, optimized, and documented as required. It is immediately available via cloning the Blaze repository and will be officially released in Blaze 3.4.

Vector Reduction Operations

reduce()

The reduce() function performs a total reduction of the elements of the given dense vector or the non-zero elements of the given sparse vector. The following examples demonstrate the total reduction of a dense and sparse vector:

blaze::DynamicVector<double> a;
// ... Resizing and initialization

const double totalsum1 = reduce( a, blaze::Add() );
const double totalsum2 = reduce( a, []( double a, double b ){ return a + b; } );

blaze::CompressedVector<double> a;
// ... Resizing and initialization

const double totalmin1 = reduce( a, blaze::Min() );
const double totalmin2 = reduce( a, []( double a, double b ){ return blaze::min( a, b ); } );

As demonstrated in the examples it is possible to pass any binary callable as custom reduction operation. However, for instance in the case of lambdas the vectorization of the reduction operation is compiler dependent and might not perform at peak performance. However, it is also possible to create vectorized custom operations. See Custom Operations for a detailed overview of the possibilities of custom operations.

Please note that the evaluation order of the reduce() function is unspecified. Thus the behavior is non-deterministic if the given reduction operation is not associative or not commutative. Also, the operation is undefined if the given reduction operation modifies the values.

sum()

The sum() function reduces the elements of the given dense vector or the non-zero elements of the given sparse vector by means of addition:

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

const int totalsum = sum( a );  // Results in 10

blaze::CompressedVector<int> a{ 1, 2, 3, 4 };

const int totalsum = sum( a );  // Results in 10

Please note that the evaluation order of the sum() function is unspecified.

prod()

The prod() function reduces the elements of the given dense vector or the non-zero elements of the given sparse vector by means of multiplication:

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

const int totalprod = prod( a );  // Results in 24

blaze::CompressedVector<int> a{ 1, 2, 3, 4 };

const int totalprod = prod( a );  // Results in 24

Please note that the evaluation order of the prod() function is unspecified.

min()

The unary min() function returns the smallest element of the given dense vector or the smallest non-zero element of the given sparse vector. It can only be used for element types that support the smaller-than relationship. In case the given vector currently has a size of 0, the returned value is the default value (e.g. 0 in case of fundamental data types).

blaze::DynamicVector<int> a{ 1, -2, 3, 0 };

const int totalmin = min( a );  // Results in -2

blaze::CompressedVector<int> a{ 1, 0, 3, 0 };

const int totalmin = min( a );  // Results in 1

Note: In case the sparse vector is not completely filled, the implicit zero elements are NOT taken into account. In the previous example the compressed vector has only 2 non-zero elements. However, the minimum of the vector is 1.

max()

This unary max() function returns the largest element of the given dense vector or the largest non-zero element of the given sparse vector. It can only be used for element types that support the smaller-than relationship. In case the given vector currently has a size of 0, the returned value is the default value (e.g. 0 in case of fundamental data types).

blaze::DynamicVector<int> a{ 1, -2, 3, 0 };

const int totalmax = max( a );  // Results in 3

blaze::CompressedVector<int> a{ -1, 0, -3, 0 };

const int totalmin = max( a );  // Results in -1

Note: In case the sparse vector is not completely filled, the implicit zero elements are NOT taken into account. In the previous example the compressed vector has only 2 non-zero elements. However, the maximum of the vector is -1.

Matrix Reduction Operations

reduce()

The reduce() function performs either a total reduction, a rowwise reduction or a columnwise reduction of the elements of the given dense matrix or the non-zero elements of the given sparse matrix. The following examples demonstrate the total reduction of a dense and sparse matrix:

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

const double totalsum1 = reduce( A, blaze::Add() );
const double totalsum2 = reduce( A, []( double a, double b ){ return a + b; } );

blaze::CompressedMatrix<double> A;
// ... Resizing and initialization

const double totalsum1 = reduce( A, blaze::Add() );
const double totalsum2 = reduce( A, []( double a, double b ){ return a + b; } );

By specifying blaze::columnwise or blaze::rowwise the reduce() function performs a column-wise or row-wise reduction, respectively. In case blaze::columnwise is specified, the (non-zero) elements of the matrix are reduced column-wise and the result is a row vector. In case blaze::rowwise is specified, the (non-zero) elements of the matrix are reduced row-wise and the result is a column vector:

blaze::DynamicMatrix<double> A;
blaze::CompressedMatrix<double> B;
blaze::DynamicVector<double,rowVector> colsum1, colsum2;
// ... Resizing and initialization

colsum1 = reduce<columnwise>( A, blaze::Add() );
colsum2 = reduce<columnwise>( B, []( double a, double b ){ return a + b; } );

blaze::DynamicMatrix<double> A;
blaze::CompressedMatrix<double> B;
blaze::DynamicVector<double,columnVector> rowsum1, rowsum2;
// ... Resizing and initialization

rowsum1 = reduce<rowwise>( A, blaze::Add() );
rowsum2 = reduce<rowwise>( B, []( double a, double b ){ return a + b; } );

As demonstrated in the examples it is possible to pass any binary callable as custom reduction operation. However, for instance in the case of lambdas the vectorization of the reduction operation is compiler dependent and might not perform at peak performance. However, it is also possible to create vectorized custom operations. See Custom Operations for a detailed overview of the possibilities of custom operations.

Please note that the evaluation order of the reduce() function is unspecified. Thus the behavior is non-deterministic if the given reduction operation is not associative or not commutative. Also, the operation is undefined if the given reduction operation modifies the values.

sum()

The sum() function reduces the elements of the given dense vector or the non-zero elements of the given sparse vector by means of addition:

blaze::DynamicMatrix<int> A{ { 1, 2 }, { 3, 4 } };

const int totalsum = sum( A );  // Results in 10

blaze::CompressedMatrix<int> a{ { 1, 2 }, { 3, 4 } };

const int totalsum = sum( A );  // Results in 10

By specifying blaze::columnwise or blaze::rowwise the sum() function performs a column-wise or row-wise summation, respectively. In case blaze::columnwise is specified, the (non-zero) elements of the matrix are summed up column-wise and the result is a row vector. In case blaze::rowwise is specified, the (non-zero) elements of the matrix are summed up row-wise and the result is a column vector:

using blaze::columnwise;

blaze::DynamicMatrix<int> A{ { 1, 0, 2 }, { 1, 3, 4 } };
blaze::CompressedMatrix<int> B{ { 1, 0, 2 }, { 1, 3, 4 } };
blaze::DynamicVector<int,rowVector> colsum1, colsum2;

colsum1 = sum<columnwise>( A );  // Results in ( 2, 3, 6 )
colsum2 = sum<columnwise>( B );  // Same result

using blaze::rowwise;

blaze::DynamicMatrix<int> A{ { 1, 0, 2 }, { 1, 3, 4 } };
blaze::CompressedMatrix<int> B{ { 1, 0, 2 }, { 1, 3, 4 } };
blaze::DynamicVector<int,columnVector> rowsum1, rowsum2;

rowsum1 = sum<rowwise>( A );  // Results in ( 3, 8 )
rowsum2 = sum<rowwise>( B );  // Same result

Please note that the evaluation order of the \c sum() function is unspecified.

prod()

The prod() function reduces the elements of the given dense vector or the non-zero elements of the given sparse vector by means of multiplication:

blaze::DynamicMatrix<int> A{ { 1, 2 }, { 3, 4 } };

const int totalprod = prod( A );  // Results in 24

blaze::CompressedMatrix<int> A{ { 1, 2 }, { 3, 4 } };

const int totalprod = prod( A );  // Results in 24

By specifying blaze::columnwise or blaze::rowwise the prod() function performs a column-wise or row-wise multiplication, respectively. In case blaze::columnwise is specified, the (non-zero) elements of the matrix are multiplied column-wise and the result is a row vector. In case blaze::rowwise is specified, the (non-zero) elements of the matrix are multiplied row-wise and the result is a column vector:

using blaze::columnwise;

blaze::DynamicMatrix<int> A{ { 1, 0, 2 }, { 1, 3, 4 } };
blaze::CompressedMatrix<int> B{ { 1, 0, 2 }, { 1, 3, 4 } };
blaze::DynamicVector<int,rowVector> colprod1, colprod2;

colprod1 = prod<columnwise>( A );  // Results in ( 1, 0, 8 )
colprod2 = prod<columnwise>( A );  // Results in ( 1, 3, 8 )

using blaze::rowwise;

blaze::DynamicMatrix<int> A{ { 1, 0, 2 }, { 1, 3, 4 } };
blaze::CompressedMatrix<int> B{ { 1, 0, 2 }, { 1, 3, 4 } };
blaze::DynamicVector<int,columnVector> rowprod1, rowprod2;

rowprod1 = prod<rowwise>( A );  // Results in ( 0, 12 )
rowprod2 = prod<rowwise>( A );  // Results in ( 2, 12 )

Please note that the evaluation order of the prod() function is unspecified.

min()

The min() function returns the smallest element of the given dense matrix or the smallest non-zero element of the given sparse matrix. This function can only be used for element types that support the smaller-than relationship. In case the given matrix currently has either 0 rows or 0 columns, the returned value is the default value (e.g. 0 in case of fundamental data types).

blaze::DynamicMatrix<int> A{ { 1, 2 }, { 3, 4 } };

const int totalmin = min( A );  // Results in 1

blaze::CompressedMatrix<int> A{ { 1, 0 }, { 3, 0 } };

const int totalmin = min( A );  // Results in 1

Note: In case the sparse matrix is not completely filled, the implicit zero elements are NOT taken into account. In the previous example the compressed matrix has only 2 non-zero elements. However, the minimum of this matrix is 1.

By specifying blaze::columnwise or blaze::rowwise the min() function determines the smallest (non-zero) element in each row or column, respectively. In case blaze::columnwise is specified, the smallest (non-zero) element of each column is determined and the result is a row vector. In case blaze::rowwise is specified, the smallest (non-zero) element of each row is determined and the result is a column vector.

using blaze::columnwise;

blaze::DynamicMatrix<int> A{ { 1, 0, 2 }, { 1, 3, 4 } };
blaze::CompressedMatrix<int> B{ { 1, 0, 2 }, { 1, 3, 4 } };
blaze::DynamicVector<int,rowVector> colmin1, colmin2;

colmin1 = min<columnwise>( A );  // Results in ( 1, 0, 2 )
colmin2 = min<columnwise>( B );  // Results in ( 1, 3, 2 )

using blaze::rowwise;

blaze::DynamicMatrix<int> A{ { 1, 0, 2 }, { 1, 3, 4 } };
blaze::CompressedMatrix<int> B{ { 1, 0, 2 }, { 1, 3, 4 } };
blaze::DynamicVector<int,columnVector> rowmin1, rowmin2;

rowmin1 = min<rowwise>( A );  // Results in ( 0, 1 )
rowmin2 = min<rowwise>( B );  // Results in ( 1, 1 )

Note: In case the sparse matrix is not completely filled, the implicit zero elements are NOT taken into account.

max()

The max() function returns the largest element of the given dense matrix or the largest non-zero element of the given sparse matrix. This function can only be used for element types that support the smaller-than relationship. In case the given matrix currently has either 0 rows or 0 columns, the returned value is the default value (e.g. 0 in case of fundamental data types).

blaze::DynamicMatrix<int> A{ { 1, 2 }, { 3, 4 } };

const int totalmax = max( A );  // Results in 4

blaze::CompressedMatrix<int> A{ { -1, 0 }, { -3, 0 } };

const int totalmax = max( A );  // Results in -1

Note: In case the sparse matrix is not completely filled, the implicit zero elements are NOT taken into account. In the previous example the compressed matrix has only 2 non-zero elements. However, the maximum of this matrix is -1.

By specifying blaze::columnwise or blaze::rowwise the max() function determines the largest (non-zero) element in each row or column, respectively. In case \c blaze::columnwise is specified, the largest (non-zero) element of each column is determined and the result is a row vector. In case blaze::rowwise is specified, the largest (non-zero) element of each row is determined and the result is a column vector.

using blaze::columnwise;

blaze::DynamicMatrix<int> A{ { 1, 0, 2 }, { 1, 3, 4 } };
blaze::CompressedMatrix<int> B{ { -1, 0, -2 }, { -1, -3, -4 } };
blaze::DynamicVector<int,rowVector> colmax1, colmax2;

colmax1 = max<columnwise>( A );  // Results in ( 1, 3, 4 )
colmax2 = max<columnwise>( B );  // Results in ( -1, -3, -2 )

using blaze::rowwise;

blaze::DynamicMatrix<int> A{ { 1, 0, 2 }, { 1, 3, 4 } };
blaze::CompressedMatrix<int> B{ { -1, 0, -2 }, { -1, -3, -4 } };
blaze::DynamicVector<int,columnVector> rowmax1, rowmax2;

rowmax1 = max<rowwise>( A );  // Results in ( 2, 4 )
rowmax2 = max<rowwise>( B );  // Results in ( -1, -1 )

Note: In case the sparse matrix is not completely filled, the implicit zero elements are NOT taken into account.