Bini D. A note on commutativity and approximation. Internal note IEI-B81-09, 1981. |

Abstract (English) |
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 Commutativity Tensor rank Matrix multiplication Polynomial evaluation |

1) Download Document PDF |

Open access Restricted Private