Prefix sum
From Wikipedia, the free encyclopedia
The prefix sum (also known as the scan, prefix reduction, or partial sum) is an operation on lists in which each element in the result list is obtained from the sum of the elements in the operand list up to its index. There are two types of prefix sum, inclusive prefix sum and exclusive prefix sum: in the inclusive prefix sum, all the operand elements are used; whereas in the exclusive prefix sum, the first element in the result list is the identity element (0 for add operation) and the last element of the operand list is not used.
Contents |
[edit] Formulae
Inclusive prefix sum: r = [a0,a0 + a1,a0 + a1 + a2,...,a0 + a1 + a2 + ... + an]
Exclusive prefix sum: r = [I,a0,a0 + a1,a0 + a1 + a2,...,a0 + a1 + a2 + ... + an − 1]
[edit] Message Passing Interface
Scans may be performed with any associative operation applicable to the elements of the list. As an example, the operations defined by the MPI standard are:
Constant | Meaning |
---|---|
MPI_MAX | return the maximum |
MPI_MIN | return the minimum |
MPI_SUM | return the sum |
MPI_PROD | return the product |
MPI_LAND | return the logical and |
MPI_BAND | return the bitwise and |
MPI_LOR | return the logical or |
MPI_BOR | return the bitwise or |
MPI_LXOR | return the logical exclusive or |
MPI_BXOR | return the bitwise exclusive or |
MPI_MINLOC | return the minimum and the location |
MPI_MAXLOC | return the maximum and the location |
In this case, the constants are used with the MPI_Scan function.