Communication-Optimal Parallel Standard and Karatsuba Integer\n Multiplication in the Distributed Memory Model

We present COPSIM a parallel implementation of standard integer\nmultiplication for the distributed memory setting, and COPK a parallel\nimplementation of Karatsuba's fast integer multiplication algorithm for a\ndistributed memory setting. When using $\\mathcal{P}$ processors, each equipped\nwith a local non-shared memory, to compute the product of tho $n$-digits\ninteger numbers, under mild conditions, our algorithms achieve optimal speedup\nof the computational time. That is, $\\mathcal{O}\\left(n^2/\\mathcal{P}\\right)$\nfor COPSIM, and $\\mathcal{O}\\left(n^{\\log_2 3}/\\mathcal{P}\\right)$ for COPK.\nThe total amount of memory required across the processors is\n$\\mathcal{O}\\left(n\\right)$, that is, within a constant factor of the minimum\nspace required to store the input values. We rigorously analyze the\nInput/Output (I/O) cost of the proposed algorithms. We show that their\nbandwidth cost (i.e., the number of memory words sent or received by at least\none processors) matches asymptotically corresponding known I/O lower bounds,\nand their latency (i.e., the number of messages sent or received in the\nalgorithm's critical execution path) is asymptotically within a multiplicative\nfactor $\\mathcal{O}\\left(\\log^2_2 \\mathcal{P}\\right)$ of the corresponding\nknown I/O lower bounds. Hence, our algorithms are asymptotically optimal with\nrespect to the bandwidth cost and almost asymptotically optimal with respect to\nthe latency cost.\n