Accession Number : AD0758717

Title :   A Determinant Theorem with Applications to Parallel Algorithms,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Heller,Don

Report Date : MAR 1973

Pagination or Media Count : 19

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)

Descriptors :   (*MATRICES(MATHEMATICS), THEOREMS), DETERMINANTS(MATHEMATICS), COMPUTER PROGRAMMING, ALGORITHMS, ANALYTIC FUNCTIONS

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE