Generalized Numeric Algorithms

Algorithms for numeric operations on view elements. Defined in stapl/algorithms/numeric.hpp. More...

Collaboration diagram for Generalized Numeric Algorithms:

Functions
template<typename View , typename Oper >
view_traits< View >::value_type	stapl::accumulate (View const &view, typename view_traits< View >::value_type init, Oper oper)
	Compute the sum of the elements and the initial value. More...
template<typename View >
view_traits< View >::value_type	stapl::accumulate (View const &view, typename view_traits< View >::value_type init)
	Compute the sum of the elements and the initial value. More...
template<typename View1 , typename View2 , typename Oper >
void	stapl::adjacent_difference (View1 const &view1, View2 &view2, Oper oper)
	Assign each element of the output the difference between the corresponding input element and the input element that precedes it. More...
template<typename View1 , typename View2 >
void	stapl::adjacent_difference (View1 const &view1, View2 &view2)
	Assign each element of the output the difference between the corresponding input element and the input element that precedes it. More...
template<typename View1 , typename View2 , typename Sum , typename Product >
view_traits< View1 >::value_type	stapl::inner_product (View1 const &view1, View2 const &view2, typename view_traits< View1 >::value_type init, Sum op1, Product op2)
	Compute the inner product of the elements of two input views. Inner product is defined as the sum of pair-wise products of the elements of two input views. More...
template<typename View1 , typename View2 >
view_traits< View1 >::value_type	stapl::inner_product (View1 const &view1, View2 const &view2, typename view_traits< View1 >::value_type init)
	Compute the inner product of the elements of two input views. Inner product is defined as the sum of pair-wise products of the elements of two input views. More...
template<typename View1 , typename View2 , typename View3 , typename Sum , typename Product >
view_traits< View1 >::value_type	stapl::weighted_inner_product (View1 const &view1, View2 const &view2, View3 const &wt, typename view_traits< View1 >::value_type init, Sum op1, Product op2)
	Compute a weighted inner product of the elements of two views, where each pair-wise product is multiplied by a weight factor before the sum of products is performed. More...
template<typename View1 , typename View2 , typename View3 >
view_traits< View1 >::value_type	stapl::weighted_inner_product (View1 const &view1, View2 const &view2, View3 const &wt, typename view_traits< View1 >::value_type init)
	Compute a weighted inner product of the elements of two views, where each pair-wise product is multiplied by a weight factor before the sum of products is performed. More...
template<typename View1 , typename View2 , typename Sum , typename Product >
View1::value_type	stapl::weighted_norm (View1 const &view1, View2 const &wt, Sum op1, Product op2)
	Compute a weighted normal of the elements of a view. More...
template<typename View1 , typename View2 >
View1::value_type	stapl::weighted_norm (View1 const &view1, View2 const &wt)
	Compute a weighted normal of the elements of a view. More...
template<typename View0 , typename View1 , typename BinaryOp >
void	stapl::partial_sum (View0 const &view0, View1 const &view1, BinaryOp binary_op, const bool shift)
	Computes the prefix sum of the elements of the input view and stores the result in the output view. More...
template<typename View0 , typename View1 >
void	stapl::partial_sum (View0 const &view0, View1 const &view1, const bool shift)
	Computes the prefix sum of the elements of the input view and stores the result in the output view. More...
template<typename View0 , typename View1 , typename BinaryFunction >
View0::value_type	stapl::partial_sum_accumulate (View0 const &view0, View1 const &view1, typename view_traits< View0 >::value_type init_value, BinaryFunction binary_op, const bool shift)
	Combination the prefix sum and accumulate of the elements of the input view. The prefix sum results are stored in the. More...
template<typename View0 , typename View1 >
View0::value_type	stapl::partial_sum_accumulate (View0 const &view0, View1 const &view1, typename view_traits< View0 >::value_type init_value, const bool shift)
	Combination the prefix sum and accumulate of the elements of the input view. The prefix sum results are stored in the. More...

Detailed Description

Algorithms for numeric operations on view elements. Defined in stapl/algorithms/numeric.hpp.

The generalized numeric algorithms provide a parallel version of several common numerical algorithms. The common version of each algorithm is provided, along with a generalized version that utilizes a BinaryFunc instead of the corresponding math operator. This BinaryFunc could be redefined to perform some different operation, while maintaining the data processing order that the common algorithm provides. For instance, p_accumulate could use a BinaryFunc to multiply, instead of sum, its input.

Warning

These algorithms assume that all numeric operations are associative. As such, they distribute data among processors and let the operations be performed in parallel, possibly with a merge taking place between processor partitions. Hence, the result could be slightly different than if the calculations had been performed linearly, as is the case with sequential STL code. The user must decide if the margin of error is acceptable for their application.

Function Documentation

accumulate() [1/2]

template<typename View , typename Oper >

view_traits< View >::value_type stapl::accumulate	(	View const &	view,
		typename view_traits< View >::value_type	init,
		Oper	oper
	)

Compute the sum of the elements and the initial value.

Parameters

view	One-dimensional view of elements to be accumulated.
init	Initial value that will be added to the sum of the elements.
oper	Binary functor implementing the accumulation operation.

Returns

Accumulation of initial value and the elements of the view.

If the view is empty the initial value is returned.

accumulate() [2/2]

template<typename View >

view_traits< View >::value_type stapl::accumulate	(	View const &	view,
		typename view_traits< View >::value_type	init
	)

Compute the sum of the elements and the initial value.

Parameters

view	One-dimensional view of elements to be accumulated.
init	Initial value that will be added to the sum of the elements.

This function calls the previous accumulate function, specifying that the stapl::plus functor be used as the binary operator for accumulation.

adjacent_difference() [1/2]

template<typename View1 , typename View2 , typename Oper >

void stapl::adjacent_difference	(	View1 const &	view1,
		View2 &	view2,
		Oper	oper
	)

Assign each element of the output the difference between the corresponding input element and the input element that precedes it.

Parameters

view1	One-dimensional view of elements whose difference with the preceding element will be computed.
view2	One-dimensional view where the differences between input elements will be written.
oper	Binary functor that implements the difference operation.

The first element of the output view is assigned the first element of the input view.

adjacent_difference() [2/2]

template<typename View1 , typename View2 >

void stapl::adjacent_difference	(	View1 const &	view1,
		View2 &	view2
	)

Assign each element of the output the difference between the corresponding input element and the input element that precedes it.

Template Parameters

View1	One-dimensional view over elements of a numeric type.
View2	One-dimensional view over elements of a numeric type to which View1::value_type is convertible.

Parameters

view1	One-dimensional view of elements whose difference with the preceding element will be computed.
view2	One-dimensional view where the differences between input elements will be written.

The first element of the output view is assigned the first element of the input view. This function invokes the previous adjacent_difference function specifying the stapl::minus functor be used as the operator.

inner_product() [1/2]

template<typename View1 , typename View2 , typename Sum , typename Product >

view_traits< View1 >::value_type stapl::inner_product	(	View1 const &	view1,
		View2 const &	view2,
		typename view_traits< View1 >::value_type	init,
		Sum	op1,
		Product	op2
	)

Compute the inner product of the elements of two input views. Inner product is defined as the sum of pair-wise products of the elements of two input views.

Parameters

view1	One-dimensional view of the first sequence of input elements.
view2	One-dimensional view of the second sequence of input elements.
init	Initial value that will be added to the sum of the products.
op1	Binary functor that implements the addition operation.
op2	Binary functor that implements the product operation.

Returns

The sum of the initial value and the pair-wise products.

The input views must have the same size.

inner_product() [2/2]

template<typename View1 , typename View2 >

view_traits< View1 >::value_type stapl::inner_product	(	View1 const &	view1,
		View2 const &	view2,
		typename view_traits< View1 >::value_type	init
	)

Compute the inner product of the elements of two input views. Inner product is defined as the sum of pair-wise products of the elements of two input views.

Parameters

view1	One-dimensional view of the first sequence of input elements.
view2	One-dimensional view of the second sequence of input elements.
init	Initial value that will be added to the sum of the products.

Returns

The sum of the initial value and the pair-wise products.

The input views must have the same size. This function invokes the previous inner_product function specifying stapl::multiplies for the product operator and stapl::plus for the addition operator.

weighted_inner_product() [1/2]

template<typename View1 , typename View2 , typename View3 , typename Sum , typename Product >

view_traits< View1 >::value_type stapl::weighted_inner_product	(	View1 const &	view1,
		View2 const &	view2,
		View3 const &	wt,
		typename view_traits< View1 >::value_type	init,
		Sum	op1,
		Product	op2
	)

Compute a weighted inner product of the elements of two views, where each pair-wise product is multiplied by a weight factor before the sum of products is performed.

Parameters

view1	One-dimensional view of the first sequence of input elements.
view2	One-dimensional view of the second sequence of input elements.
wt	One-dimensional view of the sequence of weights.
init	Initial value that will be added to the sum of the weighted products.
op1	Binary functor implementing addition.
op2	Binary functor implementing multiplication used to compute the product of two elements and the product of the weight and the result of the element product.

Returns

The sum of the initial value and the weighted pair-wise products.

The input views must have the same size.

weighted_inner_product() [2/2]

template<typename View1 , typename View2 , typename View3 >

view_traits< View1 >::value_type stapl::weighted_inner_product	(	View1 const &	view1,
		View2 const &	view2,
		View3 const &	wt,
		typename view_traits< View1 >::value_type	init
	)

Compute a weighted inner product of the elements of two views, where each pair-wise product is multiplied by a weight factor before the sum of products is performed.

Parameters

view1	One-dimensional view of the first sequence of input elements.
view2	One-dimensional view of the second sequence of input elements.
wt	One-dimensional view of the sequence of weights.
init	Initial value that will be added to the sum of the weighted products.

Returns

The sum of the initial value and the weighted pair-wise products.

The input views must have the same size. This function invokes the previous weighted_inner_product function specifying stapl::multiplies for the product operator and stapl::plus for the addition operator.

weighted_norm() [1/2]

template<typename View1 , typename View2 , typename Sum , typename Product >

View1::value_type stapl::weighted_norm	(	View1 const &	view1,
		View2 const &	wt,
		Sum	op1,
		Product	op2
	)

Compute a weighted normal of the elements of a view.

Parameters

view1	One-dimensional view of the sequence of input elements.
wt	One-dimensional view of the sequence of weights.
op1	Binary functor implementing addition.
op2	Binary functor implementing multiplication used to compute the product of an element with itself and the product of the weight and the element's square.

Returns

The square root of the sum of weighted squares of the input elements.

The input views must have the same size.

weighted_norm() [2/2]

template<typename View1 , typename View2 >

View1::value_type stapl::weighted_norm	(	View1 const &	view1,
		View2 const &	wt
	)

Compute a weighted normal of the elements of a view.

Parameters

view1	One-dimensional view of the sequence of input elements.
wt	One-dimensional view of the sequence of weights.

Returns

The square root of the sum of weighted squares of the input elements.

The input views must have the same size. This function invokes the previous weighted_norm function specifying stapl::multiplies for the product operator and stapl::plus for the addition operator.

partial_sum() [1/2]

template<typename View0 , typename View1 , typename BinaryOp >

void stapl::partial_sum	(	View0 const &	view0,
		View1 const &	view1,
		BinaryOp	binary_op,
		const bool	shift
	)

Computes the prefix sum of the elements of the input view and stores the result in the output view.

Parameters

view0	A one-dimensional view over the input elements that are of a numeric type.
view1	A one-dimensional view over the elements where the result of the partial sum will be written.
binary_op	The binary functor that will be used to sum elements.
shift	Indicates if the partial sum is inclusive or exclusive.

An inclusive partial sum assigns the value of the first input element to the first element in the output view, which is the definition of partial sum. An exclusive partial sum is a prescan [Blelloch 1990]. It sets the elements of the output view to the sum of all preceding elements in the input view, with the first element assigned the identity value for addition of the element type.

partial_sum() [2/2]

template<typename View0 , typename View1 >

void stapl::partial_sum	(	View0 const &	view0,
		View1 const &	view1,
		const bool	shift
	)

Computes the prefix sum of the elements of the input view and stores the result in the output view.

Parameters

view0	A one-dimensional view over the input elements that are of a numeric type.
view1	A one-dimensional view over the elements where the result of the partial sum will be written.
shift	Indicates if the partial sum is inclusive or exclusive.

This function calls the previous partial_sum function, specifying that the stapl::plus functor be used as the binary operator for addition.

partial_sum_accumulate() [1/2]

template<typename View0 , typename View1 , typename BinaryFunction >

View0::value_type stapl::partial_sum_accumulate	(	View0 const &	view0,
		View1 const &	view1,
		typename view_traits< View0 >::value_type	init_value,
		BinaryFunction	binary_op,
		const bool	shift
	)

Combination the prefix sum and accumulate of the elements of the input view. The prefix sum results are stored in the.

Parameters

view0	A one-dimensional view over the input elements that are of a numeric type.
view1	A one-dimensional view over the elements where the result of the partial sum will be written.
binary_op	The binary functor that will be used to sum elements.
init_value	the initial value needed for accumulate
shift	Indicates if the partial sum is inclusive or exclusive.

partial_sum_accumulate() [2/2]

template<typename View0 , typename View1 >

View0::value_type stapl::partial_sum_accumulate	(	View0 const &	view0,
		View1 const &	view1,
		typename view_traits< View0 >::value_type	init_value,
		const bool	shift
	)

Combination the prefix sum and accumulate of the elements of the input view. The prefix sum results are stored in the.

Parameters

view0	A one-dimensional view over the input elements that are of a numeric type.
view1	A one-dimensional view over the elements where the result of the partial sum will be written.
init_value	the initial value needed for accumulate
shift	Indicates if the partial sum is inclusive or exclusive.

This function calls the previous partial_sum_accumulate function, specifying that the stapl::plus functor be used as the binary operator for addition.