Compression using efficient multicasting

Many multiprocessor systems have the ability to broadcast and/or multicast information efficiently. However, this ability is often overlooked when des igning algorithms for these systems. In this paper, we introduce a new comp ression technique that uses efficient multicasting to significantly reduce the amount of information Communicated during parallel and distributed comp utation, resulting in significantly faster algorithms for Fast Fourier Tran sforms and sorting on shared memory parallel models with limited bandwidth. These algorithms demonstrate the importance of taking advantage of efficie nt multicasting. The compression technique uses a new, natural variant of R amsey theory, which may be of independent interest. (C) 2001 Academic Press .