English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We present COPSIM a parallel implementation of standard integermultiplication for the distributed memory setting, and COPK a parallelimplementation of Karatsuba's fast integer multiplication algorithm for adistributed memory setting. When using $\mathcal{P}$ processors, each equippedwith a local non-shared memory, to compute the product of tho $n$-digitsinteger numbers, under mild conditions, our algorithms achieve optimal speedupof the computational time. That is, $\mathcal{O}\left(n^2/\mathcal{P}\right)$for COPSIM, and $\mathcal{O}\left(n^{\log_2 3}/\mathcal{P}\right)$ for COPK.The total amount of memory required across the processors is$\mathcal{O}\left(n\right)$, that is, within a constant factor of the minimumspace required to store the input values. We rigorously analyze theInput/Output (I/O) cost of the proposed algorithms. We show that theirbandwidth cost (i.e., the number of memory words sent or received by at leastone processors) matches asymptotically corresponding known I/O lower bounds,and their latency (i.e., the number of messages sent or received in thealgorithm's critical execution path) is asymptotically within a multiplicativefactor $\mathcal{O}\left(\log^2_2 \mathcal{P}\right)$ of the correspondingknown I/O lower bounds. Hence, our algorithms are asymptotically optimal withrespect to the bandwidth cost and almost asymptotically optimal with respect tothe latency cost.

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