An application of lattice basis reduction to polynomial identities for algebraic structures
type: Item
instance of: scholarly article
title: An application of lattice basis reduction to polynomial identities for algebraic structures
zbMATH Open document ID: 1173.17001
author: Murray R. Bremner
author: Luiz Antonio Peresi
published in: Linear Algebra and its Applications
publication date: 2008-12-12T00:00:00Z
review text: In this paper, the authors study computationally how to simplify the polynomial identities describing the trilineat operations classified by the authors in [Commun. Algebra 35, No. 9, 2932--2959 (2007; Zbl 1172.17003)]. The authors give a lattice basis reduction to simplify these identities equivalent to the ones obtained considering row canonical forms. To do so, the polynomial identities are represented as the nullspace of a large matrix \(E\) with entries in \(\mathbb Z\) (the expansion matrix). From the row canonical form of \(E\) over \(\mathbb Q\), an integral basis for the nullspace is extracted as a vector space over \(\mathbb Q\). Next they obtain a basis for the nullspace lattice by using the Hermite normal form of the transpose \(E^t\) and a matrix \(U\) such that \(U\cdot E^t=H\). If \(n\) is the dimension of the nullspace of \(E\) over \(\mathbb Q\), the last \(n\) rows of \(U\) form an integral basis for the nullspace lattice. To simplify these basis vectors, the LLL algorithm is used. The paper applies this approach for obtaining simpler polynomial identities for the most difficult case in the classification of trilinear operations. The authors show the pseudo-code of several algorithms applied to compute the lattice basis reduction.
Mathematics Subject Classification ID: 17-08
Mathematics Subject Classification ID: 17A40
Mathematics Subject Classification ID: 68W30
zbMATH DE Number: 5382406
zbMATH Keywords: nonassociative algebra
zbMATH Keywords: LLL algorithm
zbMATH Keywords: Hermite normal form
zbMATH Keywords: lattice basis reduction
zbMATH Keywords: trilinear operations
zbMATH Keywords: polynomial identities
reviewed by: Angel Francisco Tenorio Villalon
MaRDI profile type: Publication
full work available at URL: j.laa.2008.09.003
OpenAlex ID: W2035855915
cites work: Q4023361
cites work: Identities for generalized Lie and Jordan products on totally associative triple systems
cites work: Classification of Trilinear Operations
cites work: Q3139838
cites work: Factoring polynomials with rational coefficients
DOI: 10.1016/J.LAA.2008.09.003
Recommended article: On lattice reduction for polynomial matrices
Recommended article: Q3005271
Recommended article: Q3840198
Recommended article: A generalization of the LLL-algorithm over Euclidean rings or orders
Recommended article: Lattice basis reduction for indefinite forms and an application
Recommended article: Q3092534
Recommended article: A hierarchy of polynomial time lattice basis reduction algorithms
Recommended article: Q3727379
Recommended article: Q3303764
Recommended article: Heuristics on lattice basis reduction in practice
description: scientific article; zbMATH DE number 5382406