
Accession Number : ADA112974
Title : The Additive and Logical Complexities of Linear and Bilinear Arithmetic Algorithms,
Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE
Personal Author(s) : Pan,V Ya
PDF Url : ADA112974
Report Date : Jun 1981
Pagination or Media Count : 23
Abstract : It is shown that CA(+ or ) + do(D(A)) + ir(D(A)) = omega(K + Q)log(K + Q) and CA(+ or ) + do(D(A)) = omega(K + Q)log(K + Q) in the cases of DFT, vector convolution, and matrix multiplication. Here CA(+ or ) is the additive complexity of a (bi)linear algorithm A for the given problem, D(A) and D(A) are the two acyclic digraphs that represent A, each of them is obtained from another one by reversing directions of all edges, ir(D) and do(D) 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 inputvariables. Do(D(A)), do(D(A)), and ir(D(A)) characterize the logical complexity of A. Also lower bounds on C(A)(+ or ) + do(D(A)) and on C(A)(+ or ) are expressed in terms of algebraic quantities such as the ranks of matrices and of multidimensional tensors associated with the problems. (Author)
Descriptors : *Linear algebra, *Algorithms, Discrete fourier transforms, Arithmetic, Vector analysis, Polynomials
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE