Toom-Cook-\(k\) (\(2 \le k \in \mathbb{N}\)) is a family of fast algorithms for multiplying long integers using \(O\left(n^{\log_k(2k-1)}\right)\) arithmetic operations, offering asymptotical improvement over the naïve quadratic-time schoolbook approach. Despite this advantage, Toom-Cook algorithms often involve nontrivial divisions, divisions by elements that are not powers of \(2\), which can be both computationally expensive and numerically unstable, especially in cryptography or quantum computing applications. Reducing or eliminating these divisions is therefore of significant theoretical and practical interest.

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.

Abstract Matrix chain multiplication is widely used in high-performance computing environments. Different parenthesis assignments, which determine the multiplication order, produce the same output but may significantly affect the runtime. Thus, finding the optimal parentheses assignment is crucial. Several algorithms, such as Godbole (1973) and Hu & Shing (1982), have been proposed to address this optimization problem. However, they only focus on minimizing arithmetic operations and disregard inter-processor communication. In many cases, the inter-processor communication cost dominates the total runtime, which makes existing algorithms sub-optimal. Schwartz and Weiss (2019) generalized Godbole’s algorithm to support fast (sub-cubic) matrix multiplication algorithms and demonstrated cases where optimizing arithmetic cost leads to sub-optimal communication cost and vice-versa. We extend their work and show that the runtime of a chain multiplication with a given parentheses assignment additionally depends on processor allocation and available resources. We present a parentheses assignment algorithm that minimizes the total runtime and outperforms previous techniques by a factor of $$\varOmega \left( t^{\frac{1}{3}} \right) $$ Ω t 1 3 (where t is the chain size). Moreover, our algorithm demonstrates up to 7.8x speedup in simulations. To the best of our knowledge, this is the first study that discusses resource allocation in the context of matrix chain multiplication.

Exascale machines have a small mean time between failures, necessitating fault tolerance. Out-of-the-box fault-tolerant solutions, such as checkpoint-restart and replication, apply to any algorithm but incur significant overhead costs. Long integer multiplication is a fundamental kernel in numerical linear algebra and cryptography. The naive, schoolbook multiplication algorithm runs in Θ(n2) while Toom-Cook algorithms runs in Θ(nlogk (2k-1)) for 2 ≤ k. We obtain the first efficient fault-tolerant parallel Toom-Cook algorithm. While asymptotically faster FFT-based algorithms exist, Toom-Cook algorithms are often favored in practice on small scale and on supercomputers. Our algorithm enables fault tolerance with negligible overhead costs. Compared to existing, general-purpose, fault-tolerant solutions, our algorithm reduces the arithmetic and communication (bandwidth) overhead costs by a factor of Θ(P/(2k-1)) (where P is the number of processors). To this end, we adapt the fault-tolerant BFS-DFS method of Birnbaum et al. (2020) for fast matrix multiplication and combine it with a coding strategy tailored for Toom-Cook. This eliminates the need for recomputations, resulting in a much faster algorithm.

Communication costs, between processors and across the memory hierarchy, often dominate the runtime of algorithms. Can we trade these costs for recomputations? Most algorithms do not utilize recomputation for this end, and most communication cost lower bounds assume no recomputation, hence do not address this fundamental question. Recently, Bilardi and De Stefani (2017), and Bilardi, Scquizzato, and Silvestri (2018) showed that recomputations cannot reduce communication costs in Strassen's fast matrix multiplication and in fast Fourier transform. We extend the former bound and show that recomputations cannot reduce communication costs for a few other fast matrix multiplication algorithms.