Complexity Estimates for Two Uncoupling Algorithms

Abstract : Uncoupling algorithms transform a linear differential system of first order into one or several scalar differential equations. We examine two approaches to uncoupling: the cyclic-vector method (CVM) and the Danilevski-Barkatou-Zürcher algorithm (DBZ). We give tight size bounds on the scalar equations produced by CVM, and design a fast variant of CVM whose complexity is quasi-optimal with respect to the output size. We exhibit a strong structural link between CVM and DBZ enabling to show that, in the generic case, DBZ has polynomial complexity and that it produces a single equation, strongly related to the output of CVM. We prove that algorithm CVM is faster than DBZ by almost two orders of magnitude, and provide experimental results that validate the theoretical complexity analyses.
Document type :
Conference papers
Complete list of metadatas

Cited literature [29 references]  Display  Hide  Download

https://hal.inria.fr/hal-00780010
Contributor : Alin Bostan <>
Submitted on : Tuesday, April 23, 2013 - 12:23:07 AM
Last modification on : Friday, January 4, 2019 - 5:32:56 PM
Long-term archiving on: Monday, April 3, 2017 - 8:28:48 AM

Files

BoChPa13.pdf
Files produced by the author(s)

Identifiers

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, Northeastern University, Boston, Massachusetts, USA, Jul 2013, Boston, United States. pp.85-92, ⟨10.1145/2465506.2465941⟩. ⟨hal-00780010v2⟩

Share

Metrics

Record views

356

Files downloads

345