Istituto di Scienza e Tecnologie dell'Informazione     
Bini D. A note on commutativity and approximation. Internal note IEI-B81-09, 1981.
The action of commutativity and approximation 1S analyzed for some problem in Computational Complexity. Lower bound criteria to the approximate and commutative approximate complexity are given in terms of border rank and commutative border rank of a given tensor. Upper bounds for matrix-vector product approximate complexity are given. In particular (nm+m) multiplication need and suffice to approximate n x m matrix-vector product, 6 multiplications suffice (5 need) to approximate 2x2 matrix product by using approximation. An application to polynomial evaluation shows that n+3 multip1ications suffice (n need [6]) to approximate any polynomial of degree n at a point. For what concerns matrix multiplication comp1exity it is introduced a number θ<=ω (ω is the exponent of matrix multiplication complexity) which measures the of complexity of the best commutative approximate algorithm for matrix multiplication. It is shown the bound θ<=2.3211... and conditions under which θ=ω are given.
Subject Approximate Complexity
Tensor rank
Matrix multiplication
Polynomial evaluation

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional