Complexity Estimates for Two Uncoupling Algorithms

Résumé : Les algorithmes de découplage transforment un système différentiel linéaire de premier ordre en une ou plusieurs équations différentielles scalaires. Nous examinons deux approches pour le découplage : la méthode du vecteur cyclique (CVM) et l'algorithme de Danilevski-Barkatou-Zürcher (DBZ). Nous donnons des bornes fines sur la taille des équations scalaires produites par CVM, et nous concevons une variante rapide de CVM, dont la complexité est quasi-optimale par rapport à la taille de la sortie. Nous exhibons un lien structurel fort entre CVM et DBZ permettant de montrer que, dans le cas générique, DBZ a une complexité polynomiale et qu'il produit une seule équation, fortement liée à la sortie de CVM. Nous démontrons que l'algorithme CVM est plus rapide que DBZ par au moins deux ordres de grandeur, and nous fournissons des résultats expérimentaux qui valident les analyses de complexité théoriques.
Type de document :
Communication dans un congrès
ISSAC'13 - 38th International Symposium on Symbolic and Algebraic Computation, Jul 2013, Boston, United States. pp.85-92, 2013, 〈10.1145/2465506.2465941〉
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00780010
Contributeur : Alin Bostan <>
Soumis le : mardi 23 avril 2013 - 00:23:07
Dernière modification le : mercredi 9 mai 2018 - 12:48:06
Document(s) archivé(s) le : lundi 3 avril 2017 - 08:28:48

Fichiers

BoChPa13.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Alin Bostan, Frédéric Chyzak, Élie De Panafieu. Complexity Estimates for Two Uncoupling Algorithms. ISSAC'13 - 38th International Symposium on Symbolic and Algebraic Computation, Jul 2013, Boston, United States. pp.85-92, 2013, 〈10.1145/2465506.2465941〉. 〈hal-00780010v2〉

Partager

Métriques

Consultations de la notice

281

Téléchargements de fichiers

169