Parallel Algorithms for Solving Triangular Linear Systems with Small Parallelism,
Abstract
The problem of solving triangular linear systems of size n on a parallel computer with small parallelism is considered. Assume that the time is measured by the number of parallel steps of any arithmetic operation. It is shown that the problem can be done in time n squared/k + O(n) with k processors for k < or = O(n), O(n sup (2-r) log n) with O(n sup r) processors for 1 < r < 3/2, and O(n sup (1-r/3) (log sup 2)n) with O(n sup r) processors for 3/2 < or = r < or = 3. The results are obtained by using two principles of reducing parallel algorithms with large parallelism to parallel algorithms with small parallelism. The two principles for the reduction are expected to be useful for other problems.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1974
- Accession Number
- ADA006867
Entities
People
- H. T. Kung
- L. Hyafil
Organizations
- Carnegie Mellon University