Algorithms for the universal decomposition algebra

Romain Lebreton 1, * Éric Schost 2, *
* Corresponding author
2 ORCCA
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 metadatas

Cited literature [38 references]  Display  Hide  Download

https://hal-polytechnique.archives-ouvertes.fr/hal-00669806
Contributor : Romain Lebreton <>
Submitted on : Tuesday, February 14, 2012 - 4:52:00 PM
Last modification on : Wednesday, March 27, 2019 - 4:41:27 PM
Long-term archiving on : Thursday, November 22, 2012 - 12:25:30 PM

File

Algorithms_for_the_universal_d...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00669806, version 1

Collections

Citation

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

Share

Metrics

Record views

315

Files downloads

136