### The Organization of Computations for Uniform Recurrence EquationsThe Organization of Computations for Uniform Recurrence Equations

Access Restriction
Subscribed

 Author Karp, Richard M. ♦ Miller, Raymond E. ♦ Winograd, Shmuel Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1967 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract A set equations in the quantities $\textit{ai}(\textit{p}),$ where $\textit{i}$ = 1, 2, · · ·, $\textit{m}$ and $\textit{p}$ ranges over a set $\textit{R}$ of lattice points in $\textit{n}-space,$ is called a system of uniform recurrence equations if the following property holds: If $\textit{p}$ and $\textit{q}$ are in $\textit{R}$ and $\textit{w}$ is an integer $\textit{n}-vector,$ then $\textit{ai}(\textit{p})$ depends directly on $\textit{aj}(\textit{p}$ - $\textit{w})$ if and only if $\textit{ai}(\textit{q})$ depends directly on $\textit{aj}(\textit{q}$ - $\textit{w}).$ Finite-difference approximations to systems of partial differential equations typically lead to such recurrence equations. The structure of such a system is specified by a dependence graph G having $\textit{m}$ vertices, in which the directed edges are labeled with integer $\textit{n}-vectors.$ For certain choices of the set $\textit{R},$ necessary and sufficient conditions on $\textit{G}$ are given for the existence of a schedule to compute all the quantities $\textit{ai}(\textit{p})$ explicitly from their defining equations. Properties of such schedules, such as the degree to which computation can proceed “in parallel,” are characterized. These characterizations depend on a certain iterative decomposition of a dependence graph into subgraphs. Analogous results concerning implicit schedules are also given. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1967-07-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 14 Issue Number 3 Page Count 28 Starting Page 563 Ending Page 590

#### Open content in new tab

Source: ACM Digital Library