Some parallel models and algorithms for solving recurrence equations.

摘要

Recurrence equations are extremely useful in the design of algorithms for many computational problems such as those in the areas of linear algebra, digital signal processing, and molecular biology. Examples of specific problems are string editing, pattern matching, parsing of linear context-free languages, string shuffling and transductions. Thus efficient algorithms for solving recurrence equations lead to efficient solutions of such problems. In this thesis, we investigate several models of parallel computation suitable for solving recurrence equations. The models that we study are the one-way linear iterative array (OLIA), the parallel random-access machine (PRAM), and the two-dimensional on-line tessellation acceptor (2-OTA). An OLIA is a systolic array in which the data movement is one-way, from left to right. For inputs of length n, the array uses n identical finite-state processors, but the design of a processor is independent of input length. A 2-OTA is a model of parallel computation that is useful in solving recurrence equations. It is a wave-front real-time two-dimensional cellular (mesh-connected) array in which data flows from the upper-left corner to the lower-right corner. We present efficient algorithms for solving recurrence equations on these models. We also study the relationships between the models as well as their complexity. Our results answer several open questions in the literature.