High-order lifting and integrality certification
type: Item
instance of: scholarly article
title: High-order lifting and integrality certification
zbMATH Open document ID: 1059.15020
DOI: 10.1016/S0747-7171(03)00097-X
author: Arne Storjohann
published in: Journal of Symbolic Computation
publication date: 2004-08-20T00:00:00Z
review text: The author studies some classical problems that involve a nonsingular matrix \(A\in K[x]^{n\times n}\) over the ring \(K[x]\) of univariate polynomials with coefficients from a field \(K\) and proves that they can be solved at approximately the same cost as that for matrix multiplication. The most fundamental of these is linear system solving, i.e. to compute the solution to \(Ax=b\) where \(b\in K[x]^{n\times n}\). The second is integrality certification, i.e. to answer the following question: If \(B\in K[x]^{n\times m}\) is given, can every column of \(B\) be expressed as a \(K[x]\)-linear combination of the columns of \(A\)? The third problem is determinant computation. For this the author proposes a Las Vegas probabilistic algorithm whose expected number of operations is an order of magnitude smaller than the best known deterministic method. In the same time the Smith form of the matrix is computed.
Mathematics Subject Classification ID: 15B33
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 65F30
Mathematics Subject Classification ID: 15A21
Mathematics Subject Classification ID: 15A06
Mathematics Subject Classification ID: 15A15
zbMATH DE Number: 2093532
zbMATH Keywords: determinant
zbMATH Keywords: Smith canonical form
zbMATH Keywords: linear system
zbMATH Keywords: polynomial matrix
zbMATH Keywords: integrality certification
zbMATH Keywords: Las Vegas probabilistic algorithm
reviewed by: Willy J. F. Govaerts
MaRDI profile type: Publication
cites work: Exact solution of linear equations using p-adic expansions
cites work: Q4660659
cites work: Asymptotically Fast Triangularization of Matrices over Rings
cites work: Fast projection methods for minimal design problems in linear system theory
cites work: Parallel algorithms for matrix normal forms
cites work: Q3875204
cites work: Certified dense linear system solving
cites work: Rational solutions of singular linear systems
cites work: On lattice reduction for polynomial matrices
cites work: Fast construction of irreducible polynomials over finite fields
cites work: Q4227283
cites work: Q4047029
cites work: Q4227350
cites work: Modern computer algebra
description: scientific article; zbMATH DE number 2093532