
Accession Number : AD0758717
Title : A Determinant Theorem with Applications to Parallel Algorithms,
Corporate Author : CARNEGIEMELLON 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 vectormatrixvector 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