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

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1981
Accession Number
ADA112974

Entities

People

  • V. Ya. Pan

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Additives (Chemicals)
  • Algorithms
  • Arithmetic
  • Coefficients
  • Computational Complexity
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Convolution
  • Discrete Fourier Transforms
  • Diseases And Disorders
  • Equations
  • Mathematics
  • Polynomials
  • Sequences
  • United States

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Approximation Theory.