Accession Number:

ADA112974

Title:

The Additive and Logical Complexities of Linear and Bilinear Arithmetic Algorithms,

Descriptive Note:

Corporate Author:

STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1981-06-01

Pagination or Media Count:

23.0

Abstract:

It is shown that CA or - doDA irDA omegaK QlogK Q and CA or - doDA omegaK QlogK Q in the cases of DFT, vector convolution, and matrix multiplication. Here CA or - is the additive complexity of a bilinear algorithm A for the given problem, DA and DA are the two acyclic digraphs that represent A, each of them is obtained from another one by reversing directions of all edges, irD and doD are two numbers that are introduced to measure the structural deficiencies of an acyclic digraph D. K and Q are the numbers of outputs and input-variables. DoDA, doDA, and irDA characterize the logical complexity of A. Also lower bounds on CA or - doDA and on CA or - are expressed in terms of algebraic quantities such as the ranks of matrices and of multidimensional tensors associated with the problems. Author

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE