A Determinant Theorem with Applications to Parallel Algorithms,
Abstract
The author states and proves an expansion theorem for the determinant of any Hessenberg matrix. The expansion is expressed as a vector-matrix-vector product which can be efficiently evaluated on a parallel machine. The computation of the first N terms of a sequence defined by a general linear recurrence is considered. On a sequential machine this problem is O(N sup 2), with N processors it is O(N), and with O(N sup 4) processors it is O(log squared N) using this expansion. Other applications include locating roots of analytic functions and proving doubling formulas for linear recurrences with constant coefficients. (Author Modified Abstract)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1973
- Accession Number
- AD0758717
Entities
People
- Don Heller
Organizations
- Carnegie Mellon University