Factorization properties of lattices over the integers
type: Item
instance of: scholarly article
title: Factorization properties of lattices over the integers
zbMATH Open document ID: 0824.11073
DOI: 10.1016/0024-3795(93)00069-C
author: Azaria Paz
author: Mody Lempel
published in: Linear Algebra and its Applications
publication date: 1995-11-15T00:00:00Z
review text: Let \(L\), \(L_ 1\), \(L_ 2\) denote \(n\)-dimensional lattices over the integers. Then \(L\) can be factored as \(L= L_ 1 L_ 2\) if every vector of \(L\) is a combination of basis vectors of \(L_ 2\), where the combination coefficients form a vector of \(L_ 1\). In this paper, three polynomial time algorithms are given to factor a lattice \(L\). The first algorithm factors a lattice \(L\) into cyclic lattices. The second factors cyclic lattices into simple lattices. (Cyclic and simple are defined in the paper.) The third factors simple lattices into prime lattices, which are lattices where the basis matrix has prime determinant. Several other algorithms for lattices are also given. In the appendix, the authors also present an extended GCD algorithm in the style of \textit{W. A. Blankinship} [Am. Math. Mon. 70, 742-745 (1963; Zbl 0116.268)].
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 11H06
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 11A05
zbMATH DE Number: 731883
zbMATH Keywords: factorization
zbMATH Keywords: integral lattices
zbMATH Keywords: polynomial time algorithms
zbMATH Keywords: extended GCD algorithm
reviewed by: Jonathan P. Sorenson
MaRDI profile type: Publication
cites work: A New Version of the Euclidean Algorith
cites work: Algorithm and bound for the greatest common divisor of n integers
cites work: Systems of distinct representatives and linear algebra
cites work: On the inherent intractability of certain coding problems (Corresp.)
cites work: Q5611106
cites work: Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis
cites work: Q3751649
cites work: Q3336683
cites work: Factoring polynomials with rational coefficients
cites work: Integer Programming with a Fixed Number of Variables
cites work: The complexity of computing the covering radius of a code
cites work: On the complexity of some coding problems (Corresp.)
cites work: Q3784192
full work available at URL: 0024-3795(93)00069-c
OpenAlex ID: W2090290054
description: scientific article; zbMATH DE number 731883