Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Algorithms for the universal decomposition algebra

Romain Lebreton 1, * Éric Schost 2, * 
* Corresponding author
Computer Science Department
Abstract : Let k be a field and let f be a polynomial of degree n in k [T]. The symmetric relations are the polynomials in k [X1, ..., Xn] that vanish on all permutations of the roots of f in the algebraic closure of k. These relations form an ideal Is; the universal decomposition algebra is the quotient algebra A := k [X1, ..., Xn]/Is. We show how to obtain efficient algorithms to compute in A. We use a univariate representation of A, i.e. an explicit isomorphism of the form A=k [T]/Q (T), since in this representation, arithmetic operations in A are known to be quasi-optimal. We give details for two related algorithms, to find the isomorphism above, and to compute the characteristic polynomial of any element of A.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [38 references]  Display  Hide  Download
Contributor : Romain Lebreton Connect in order to contact the contributor
Submitted on : Tuesday, February 14, 2012 - 4:52:00 PM
Last modification on : Thursday, March 5, 2020 - 6:24:48 PM
Long-term archiving on: : Thursday, November 22, 2012 - 12:25:30 PM


Files produced by the author(s)


  • HAL Id : hal-00669806, version 1



Romain Lebreton, Éric Schost. Algorithms for the universal decomposition algebra. 2012. ⟨hal-00669806⟩



Record views


Files downloads