Schönhage-Strassen Algorithm with MapReduce for Multiplying Terabit Integers (April 29, 2011)
Tsz-Wo Sze · 2011
We present MapReduce-SSA, an integer multiplication al- gorithm using the ideas from Schalgorithm (SSA) on MapReduce. SSA is one of the most commonly used large integer multiplication algorithms. MapReduce is a programming model invented for distributed data pro- cessing on large clusters. MapReduce-SSA is designed for multiplying integers in terabit scale on clusters of commod- ity machines. As parts of MapReduce-SSA, two algorithms, MapReduce-FFT and MapReduce-Sum, are created for com- puting discrete Fourier transforms and summations. These mathematical algorithms match the model of MapReduce seamlessly.