Time and Parallel Processor Bounds for Linear Recurrence Systems

We give new time and processor bounds for the parallel evaluation of linear recurrence systems. Such systems may be represented as x̄ =c̄ + Ax̄ where A is an n X n strictly lower triangular matrix and c is a constant column vector. We show that O og 2 2 n) time steps and n 3 / 8 + 0O 2 ) processors...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computers 1975-07, Vol.C-24 (7), p.701-717, Article 701
Main Authors: Shyh-Ching Chen, Kuck, D.J.
Format: Article
Language:English
Subjects:
Approximation algorithms
Bandwidth
General linear recurrences
Indexes
Linear systems
Manganese
Memory management
mth order linear recurrences
parallel computation
Pipeline processing
processor bounds
time bounds
triangular linear systems
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We give new time and processor bounds for the parallel evaluation of linear recurrence systems. Such systems may be represented as x̄ =c̄ + Ax̄ where A is an n X n strictly lower triangular matrix and c is a constant column vector. We show that O og 2 2 n) time steps and n 3 / 8 + 0O 2 ) processors are sufficient. We also show that mth order linear recurrences, i. e., where A has a bandwidth of m, can be computed within O(log 2 mlog 2 n) time steps with at most 3m 2 n/4 + O(mn) processors. In all cases, our bounds on time and processors are improvements on previous results, and the computer need only perform one type of operation at each time step (SIMD operation). By a simple transformation, the results can also be applied to the solution of any triangular linear system of equations Ax̄ = b̄.
ISSN:0018-9340
1557-9956
DOI:10.1109/T-C.1975.224291