Abstract
In this paper we construct algorithms and investigate the time required for the parallel evaluation of rational expressions using small numbers of processors. We define algorithms which compute a polynomial with n operations in 3n/(2p+ 1) + Q(p2) time units with p processors and a general rational expression with n operations in 5n/(2p+ 3) +0(p2) time units. These algorithms are suitable for implementation on computers with restricted data access.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 933-937 |
| Number of pages | 5 |
| Journal | IEEE Transactions on Computers |
| Volume | C-26 |
| Issue number | 10 |
| DOIs | |
| State | Published - Oct 1977 |
| Externally published | Yes |
Keywords
- Computational complexity
- Parallel algorithms
- Polynomial expressions
- Rational expressions
- Recursive doubling
ASJC Scopus subject areas
- Software
- Theoretical Computer Science
- Hardware and Architecture
- Computational Theory and Mathematics