A formal algebraic model for divide-and-conquer algorithms is presented. The model reveals the internal structure of divide-and-conquer functions, leads to high-level and functional-styled algorithms specification, and simplifies complexity analysis. Algorithms developed under the model contain vast amounts of parallelism and can be mapped fairly easily to parallel computers.
1. Introduction
Divide-and-conquer is a well-known strategy for designing parallel algorithms: A problem is recursively subdivided into relatively independent components, which are in turn operated on in parallel [Aho et al. 1974, Jamieson et al. 1987, Preparata and Vuillemin 1981, Ullman 1984]. The method is both simple--even the most novice programmers find it easy to grasp---and effective--it is the basis for many of the best known parallel algorithms.
However, despite the widespread use of divide-and-conquer, it has received very little formal treatment in the literature. In this paper we develop a formal algebraic model of divide-and-conquer. Our motivation stems from the desire to answer the following questions:
9 What is the class of problems that can be attacked by divide-and-conquer?
9 What are the structural and domain properties of "'divide" and "combine" functions?
9 Are there other inherent constituents of divide-and-conquer algorithms aside from divide and combine functions?
We begin in the next section by noticing that morphisms in basic algebra [Dornhoff and Hohn 1978] resemble the fundamental structure of divide-and-conquer. However, many problems that we would like to solve by divide-and-conquer are almost, but not quite, morphisms. Therefore, we introduce the notion of adjust functions which allow "This research was supported in part by DOE grant DOE FG02-86ER25012.