Parallel Algorithms for Multi-Indexed Recurrence Relations with Applications to211 DPCM Image Compression

摘要

Parallel solution of 1-indexed recurrence relations has received much attention,211u001ebut no effort has been made to design parallel algorithms for multi-indexed 211u001erecurrence relations, where the recurrence is in more than one index. Multi-211u001eindexed relations arise in JPEG-standard DPCM compression of images, which is an 211u001eincreasingly important area due to the explosion of imagery applications such as 211u001emultimedia and medical imaging. In the paper we design and analyze novel parallel 211u001ealgorithms for solving multi-indexed recurrence relations of arbitrary order. To 211u001ethat end, we develop three techniques: index sequencing, index decoupling, and 211u001edimension shifting.