Algebras Having Linear Multiplicative Complexities

DOI10.1145/322003.322014zbMath0382.68045OpenAlexW2032765816MaRDI QIDQ4160410

Charles M. Fiduccia, Yechezkel Zalcstein

Publication date: 1977

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322003.322014

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Related Items (28)

On Computing the Discrete Fourier Transform ⋮ The quadratic hull of a code and the geometric view on multiplication algorithms ⋮ Multiplicative complexity of direct sums of quadratic systems ⋮ Structure of algebras of commutative matrices ⋮ Classification of all the minimal bilinear algorithms for computing the coefficients of the product of two polynomials modulo a polynomial. I: The algebra \(G[u/<Q(u)^{\ell}>\), \(\ell >1\)] ⋮ The complexity of basic complex operations ⋮ On the algorithmic complexity of associative algebras ⋮ Bilinear complexity of algebras and the Chudnovsky-Chudnovsky interpolation method ⋮ New combinations of methods for the acceleration of matrix multiplication ⋮ Trilinear aggregating with implicit canceling for a new acceleration of matrix multiplication ⋮ Fast matrix multiplication without APA-algorithms ⋮ On the complexity of multiplication in finite fields ⋮ Algebraic complexities and algebraic curves over finite fields ⋮ Some bilinear forms whose multiplicative complexity depends on the field of constants ⋮ Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics ⋮ Some elementary proofs of lower bounds in complexity theory ⋮ Global properties of tensor rank ⋮ On multiplication in algebraic extension fields ⋮ On the multiplicative complexity of the discrete Fourier transform ⋮ Lower bounds of the complexity of linear algebras ⋮ On the direct sum conjecture in the straight line model ⋮ On the maximal multiplicative complexity of a family of bilinear forms ⋮ Closure, commutativity and minimal complexity of some spaces of matrices ⋮ On the tensor rank of multiplication in finite extensions of finite fields and related issues in algebraic geometry ⋮ Multiplicative complexity and algebraic structure ⋮ Lower bounds in algebraic computational complexity ⋮ Algebraic and computational properties of a set of (0,1) matrices with prescribed sum ⋮ On the direct sum conjecture

This page was built for publication: Algebras Having Linear Multiplicative Complexities