Minimizing Processor Count for Fault Tolerant Toom-Cook Algorithms

Long integer multiplication is a fundamental kernel in various scientific areas, including numerical linear algebra, cryptography, and quantum computing. Toom-Cook-k algorithms run in Θ(nlogk (2k-1)) and are often favored in practice over the Θ (n2) schoolbook algorithm. Faults are a major bottleneck in large-scale computing. The growing size of machines and decreasing operating voltages led to a reduction in the mean time between failures, with modern exascale systems experiencing an error per second. While standard fault-tolerant solutions, such as checkpoint-restart and replication, are straightforward to implement, they incur significant overhead and limit overall system utilization. Algorithm-based fault-tolerant solutions offer a more efficient alternative by leveraging the algorithm's structure, for instance, by incorporating erasure codes into the algorithm. Nissim, Schwartz, and Spiizer (2024) proposed an algorithm-based fault-tolerant solution for the parallel Toom-Cook algorithm. Their solution incurs minor arithmetic and communication costs overheads, but requires a considerable number of additional processors.