Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Parallel Algorithms for Multi-Indexed Recurrence Relations With Applications to DPCM Image Compression

Published

Author(s)

Abdou S. Youssef

Abstract

Parallel solution of 1-indexed recurrence relations has received much attention, but no effort has been made to design parallel algorithms for multi-indexed recurrence relations, where the recurrence is in more than one index. Multi-indexed relations arise in JPEG-standard DPCM compression of images, which is an increasingly important area due to the explosion of imagery applications such as multimedia and medical imaging. In this paper we design and analyze novel parallel algorithms for solving multi-indexed recurrence relations of arbitrary order. To that end, we develop three techniques: index sequencing, index decoupling, and dimension shifting. Index sequencing leads to a parallel algorithm of O(n log n) time on n processors, where the input size is n2. Index decoupling applies in limited situations, one of which is a commonly used special case of DPCM, and leads to a parallel algorithm of O(log n) time for n x n images on n x n processors. Dimension shifting is a universal technique for multi-indexed relations, and involves reducing the number of indices to 1 while clustering the terms of the relation into vectors. This is accomplished by means of special vector operators that we define and study. Our parallel algorithm for doing the dimension shifting and for solving the resulting 1-indexed recurrence relation takes O(log2 N) time on meshes of partitionable buses or hypercubes, where N is the data input-output size.
Citation
- 6115
Report Number
6115

Keywords

compression, convolution, dimension shifting, DPCM, Fourier transform, parallel algorithms, recurrence relations

Citation

Youssef, A. (1998), Parallel Algorithms for Multi-Indexed Recurrence Relations With Applications to DPCM Image Compression, - 6115, National Institute of Standards and Technology, Gaithersburg, MD (Accessed June 9, 2023)
Created December 1, 1998, Updated October 16, 2008