Complexity estimates for two uncoupling algorithms

DOI10.1145/2465506.2465941MaRDI QIDQ2963220zbMATH OpenOpenAlexFDO

Authors Alin Bostan, Elie de Panafieu, Frédéric Chyzak

Publication date 10 February 2017

Published in Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.5414, https://hal.inria.fr/hal-00780010/file/BoChPa13.pdf

zbMATH Keywords

complexitycyclic-vector methodDanilevski-Barkatou-Zürcher algorithmgauge equivalenceuncoupling

Mathematics Subject Classification ID

Abstract differential equations (12H20) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

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"urcher 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.

Recommendations

• On the problem of uncoupling systems of linear differential equations
• scientific article; zbMATH DE number 1057762
• scientific article; zbMATH DE number 1262458
• scientific article; zbMATH DE number 4155781
• Fast algorithms for polynomial solutions of linear differential equations

Cited in

(11)

• Resolving sequences of operators for linear ordinary differential and difference systems of arbitrary order
• Large Scale Analytic Calculations in Quantum Field Theories
• Analytic computing methods for precision calculations in quantum field theory
• Analytic integration methods in quantum field theory: an introduction
• The SAGEX review on scattering amplitudes Chapter 4: Multi-loop Feynman integrals
• Hypergeometric structures in Feynman integrals
• The first-order factorizable contributions to the three-loop massive operator matrix elements \(A_{Qg}^{(3)}\) and \(\Delta A_{Qg}^{(3)}\)
• The inverse Mellin transform via analytic continuation
• D-finiteness: a success story
• A unified approach for degree bound estimates of linear differential operators
• Degree bounds for linear differential equations and recurrences

This page was built for publication: Complexity estimates for two uncoupling algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2963220)