Optimal Karatsuba-like formulae for certain bilinear forms in GF(2)
type: Item
instance of: scholarly article
title: Optimal Karatsuba-like formulae for certain bilinear forms in GF(2)
zbMATH Open document ID: 1153.15022
published in: Linear Algebra and its Applications
publication date: 2008-10-06T00:00:00Z
review text: Given some field \(F\) and a known bilinear form belonging to \(F,\) the construction of optimal algorithms for computing such a bilinear form enjoys a large literature. Here the author chooses \(F\) to be the \(GF(2)\), the field with only two elements, and presents several combinatorial approaches for finding optimal Karatsuba-like formulae for fast computing of certain bilinear forms in \(GF(2)\). Two exhaustive search algorithms are proposed which exploit an explicit construction of trilinear decompositions. All considered examples are symmetric but results about non-symmetric case are promised in a separate paper.
reviewed by: Raffaella Pavani
Mathematics Subject Classification ID: 15B33
Mathematics Subject Classification ID: 15A69
zbMATH DE Number: 5349170
zbMATH Keywords: optimal algorithms
zbMATH Keywords: Karatsuba
zbMATH Keywords: polynomial multiplication
zbMATH Keywords: trilinear decomposition
author: Ivan Oseledets
MaRDI profile type: Publication
full work available at URL: j.laa.2008.06.004
OpenAlex ID: W1999900513
cites work: Q4314299
cites work: Q4094392
cites work: Comments on "Five, Six, and Seven-Term Karatsuba-Like Formulae
cites work: Q4364562
cites work: Optimal evaluation of pairs of bilinear forms
cites work: Five, six, and seven-term Karatsuba-like formulae
cites work: Q5676984
cites work: Gaussian elimination is not optimal
DOI: 10.1016/J.LAA.2008.06.004
description: scientific article; zbMATH DE number 5349170