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 input-variables. 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