Fast algorithms for zero-dimensional polynomial systems using duality (Q1422204)

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.