On commutativity and approximation
type: Item
instance of: scholarly article
title: On commutativity and approximation
zbMATH Open document ID: 0548.68036
DOI: 10.1016/0304-3975(83)90068-3
published in: Theoretical Computer Science
publication date: 1984-01-01T00:00:00Z
review text: The paper deals with lower and upper bounds on the algebraic complexity of bilinear forms based on the rank of the corresponding tensors. It defines the ''commutative border rank'' (cbrk) of a tensor, which is a modification of the definition of ''rank'' so that it can be applied to algorithms that a) only need to approximate the solution and b) make use of commutativity. The following upper and lower bounds on algebraic complexity are derived, using corresponding bounds on cbrk: (i) \(m(n+1)/2\) multiplications are necessary and sufficient for n,m-matrix-vector product. (ii) 6 multiplications are sufficient and 5 are necessary for 2,2-matrix multiplication. (iii) \((n/2)+2\) multiplications are sufficient for approximating the value of a polynomial of degree n at a given point. The last section of the paper gives possible bounds on the exponent of matrix multiplication complexity.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W30
zbMATH DE Number: 3874605
zbMATH Keywords: tensor rank
zbMATH Keywords: polynomial evaluation
zbMATH Keywords: approximate algorithm
zbMATH Keywords: approximate complexity
zbMATH Keywords: commutative border rank
zbMATH Keywords: algebraic complexity
zbMATH Keywords: matrix-vector product
zbMATH Keywords: matrix multiplication
author: Dario A. Bini
reviewed by: Helmut Alt
MaRDI profile type: Publication
full work available at URL: 0304-3975(83)90068-3
OpenAlex ID: W2021882883
cites work: Q3890107
cites work: \(0(n^{2.7799})\) complexity for \(n\times n\) approximate matrix multiplication
cites work: Approximate Solutions for the Bilinear Form Computational Problem
cites work: On the Asymptotic Complexity of Matrix Multiplication
cites work: On the Complexity of Bilinear Forms with Commutativity
cites work: Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics
cites work: Partial and Total Matrix Multiplication
cites work: Polynomials with Rational Coefficients Which are Hard to Compute
cites work: Q4047029
cites work: Some elementary proofs of lower bounds in complexity theory
cites work: On the number of multiplications necessary to compute certain functions
description: scientific article; zbMATH DE number 3874605