https://hal-polytechnique.archives-ouvertes.fr/hal-00669806Lebreton, RomainRomainLebretonLIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau] - X - École polytechnique - CNRS - Centre National de la Recherche ScientifiqueSchost, ÉricÉricSchostORCCA - Computer Science Department - UWO - University of Western OntarioAlgorithms for the universal decomposition algebraHAL CCSD2012Algorithmscomplexityuniversal decomposition algebralagrange resolventcauchy modulesdivided differencesinvariants[INFO.INFO-SC] Computer Science [cs]/Symbolic Computation [cs.SC]Lebreton, Romain2012-02-14 16:52:002023-02-08 17:10:512012-02-14 16:54:04enPreprints, Working Papers, ...application/pdf1Let 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.