Accession Number:

AD0758717

Title:

A Determinant Theorem with Applications to Parallel Algorithms,

Descriptive Note:

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1973-03-01

Pagination or Media Count:

19.0

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 ON sup 2, with N processors it is ON, and with ON sup 4 processors it is Olog 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

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE