Fast algorithms for zero-dimensional polynomial systems using duality
type: Item
instance of: scholarly article
title: Fast algorithms for zero-dimensional polynomial systems using duality
zbMATH Open document ID: 1058.68122
author: Alin Bostan
author: Bruno Salvy
author: Éric Schost
published in: Applicable Algebra in Engineering, Communication and Computing
publication date: 2004-02-05T00:00:00Z
review text: Many algorithms dealing with zero-dimensional polynomial systems are based on linear algebra over the associated quotient algebra. The goal of this paper is to speed this linear algebra phase, provided the multiplicative structure of the quotient algebra is somehow known. More precisely, given an element \(u\) in the algebra, if the multiplication table (or matrix of multiplication by \(u\)) of the quotient algebra is known, the authors manage to obtain the minimal polynomial of \(u\) and the parametrizations efficiently. This is accomplished by associating to every element \(u\) in the dual of the quotient algebra and a linear form \(\ell\) a formal power series whose common denominator is generally the minimal polynomial of the chosen element \(u\). The desired parametrizations can also be read out from the coefficients of this power series. The algorithms described are probabilistic (that is, their correctness depends on a random choice of numbers) and the probability of success is computed.
reviewed by: Juan Sabia
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 68W40
Mathematics Subject Classification ID: 13P10
zbMATH DE Number: 2038434
zbMATH Keywords: symbolic computation
zbMATH Keywords: algebraic computation
zbMATH Keywords: polynomial system
zbMATH Keywords: duality
zbMATH Keywords: linear recurrence sequences
zbMATH Keywords: generating series
describes a project that uses: Magma
describes a project that uses: ISOLATE
describes a project that uses: FGb
describes a project that uses: Kronecker
MaRDI profile type: Publication
full work available at URL: s00200-003-0133-5
OpenAlex ID: W1968561983
DOI: 10.1007/S00200-003-0133-5
Recommended article: Fast computation of zeros of polynomial systems with bounded degree under finite-precision
Recommended article: Fast linear homotopy to find approximate zeros of polynomial systems
Recommended article: Zero decomposition algorithms for systems of polynomial equations
Recommended article: Fast algorithms for polynomial solutions of linear differential equations
Recommended article: On the Complexity of Solving Zero-Dimensional Polynomial Systems via Projection
Recommended article: Optimal and nearly optimal algorithms for approximating polynomial zeros
Recommended article: A globally convergent parallel algorithm for zeros of polynomial systems
Recommended article: Asymptotically fast polynomial matrix algorithms for multivariable systems
Recommended article: Q3611053
Recommended article: An algorithm for solving zero-dimensional parametric systems of polynomial homogeneous equations
description: scientific article; zbMATH DE number 2038434