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.

[edit] See also

[edit] External link

Languages