Abstract
A great number of algorithms can be implemented in terms of reductions, a very common functional pattern. In most cases, reductions are easily parallelizable.
There are however many important reduction applications for which a parallel implementation cannot be directly derived from their natural functional form due to non-associative reduction operators.
We present a transformation capable of deriving a parallel implementation for many reductions with non-associative operators by leveraging the associativity of matrix multiplications defined over semirings.
