On the I/O complexity of hybrid algorithms for Integer Multiplication
share
Almost asymptotically tight lower bounds are derived for the I/O complexity IO(n,M) of a general class of hybrid algorithms computing the product of two integers, each represented with n digits in a given base s, in a two-level storage hierarchy with M words of fast memory, with different digits stored in different memory words. The considered hybrid algorithm combine the Toom-Cook-k (or Toom-k) fast integer multiplication approach with computational complexity Θ(c_kn^log_k (2k-1)), and "standard" integer multiplication algorithms which compute Ω(n^2) digit multiplications. We present an Ω((n/max{M,n_0})^log_k (2k-1)(max{1,n_0/M})^2M) lower bound for the I/O complexity a class of "uniform, non-stationary" hybrid algorithms when executed in a two-level storage hierarchy with M words of fast memory, where n_0 denotes the threshold size of sub-problems which are computed using standard algorithms with algebraic complexity Ω(n^2). The lower bound is derived for the more general class of "non-uniform, non-stationary" hybrid algorithms which allow recursive calls to have a different structure, even when they refer to the multiplication of integers of the same size and in the same recursive level including those where the value of k is allowed to vary with the level of recursion. As some hybrid algorithms from this class execute a number of I/O operations that is within a O(k^2) multiplicative term of the corresponding lower bounds, the proposed lower bounds are almost asymptotically tight and indeed tight for constant values of k. Extensions of the lower bounds for a parallel model with P processors are also discussed.
READ FULL TEXT
