Alin Bostan
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.
- S. Abramov and E. Zima. A universal program to uncouple linear systems. In Proceedings of CMCP'96, pages 16--26, 1997.Google Scholar
- S. A. Abramov. EG-eliminations. J. Differ. Equations Appl., 5(4-5):393--433, 1999.Google ScholarCross Ref
- K. Adjamagbo. Sur l'effectivité du lemme du vecteur cyclique. C. R. Acad. Sci. Paris Sér. I Math., 306(13):543--546, 1988.Google Scholar
- E. H. Bareiss. Sylvester's identity and multistep integer-preserving Gaussian elimination. Math. Comp., 22:565--578, 1968.Google Scholar
- M. A. Barkatou. An algorithm for computing a companion block diagonal form for a system of linear differential equations. Appl. Algebra Engrg. Comm. Comput., 4(3):185--195, 1993.Google ScholarDigital Library
- M. Bronstein and M. Petkovšek. An introduction to pseudo-linear algebra. Theor. Comput. Sci., 157(1):3--33, 1996. Google ScholarDigital Library
- D. G. Cantor and E. Kaltofen. On fast multiplication of polynomials over arbitrary algebras. Acta Inform., 28(7):693--701, 1991. Google ScholarDigital Library
- R. C. Churchill and J. Kovacic. Cyclic vectors. In Differential algebra and related topics, pages 191--218. 2002.Google ScholarCross Ref
- T. Cluzeau. Factorization of differential systems in characteristic p. In Proc. ISSAC'03, pages 58--65. ACM, 2003. Google ScholarDigital Library
- F. T. Cope. Formal Solutions of Irregular Linear Differential Equations. Part II. Amer. J. Math., 58(1):130--140, 1936.Google ScholarCross Ref
- A. Dabèche. Formes canoniques rationnelles d'un système différentiel à point singulier irrégulier. In Équations différentielles et systèmes de Pfaff dans le champ complexe, volume 712 of Lecture Notes in Math., pages 20--32. 1979.Google Scholar
- A. M. Danilevski. The numerical solution of the secular equation. Matem. sbornik, 44(2):169--171, 1937. (in Russian).Google Scholar
- P. Deligne. Équations différentielles à points singuliers réguliers. Lecture Notes in Math., Vol. 163. Springer, 1970.Google Scholar
- L. E. Dickson. Algebras and their arithmetics. Univ. of Chicago Press, Chicago, 1923. Chicago, 1923.Google Scholar
- B. Dwork and P. Robba. Effective p-adic bounds for solutions of homogeneous linear differential equations. Trans. Amer. Math. Soc., 259(2):559--577, 1980.Google Scholar
- S. Gerhold. Uncoupling systems of linear Ore operator equations. Master's thesis, RISC, J. Kepler Univ. Linz, 2002.Google Scholar
- M. Giesbrecht and A. Heinle. A polynomial-time algorithm for the Jacobson form of a matrix of Ore polynomials. In Computer Algebra in Scientific Computing, CASC'12, volume 7442 of Lecture Notes in Comput. Sci., LNCS, pages 117--128. Springer, 2012. Google ScholarDigital Library
- A. Hilali. Characterization of a linear differential system with a regular singularity. In Computer algebra, volume 162 of Lecture Notes in Comput. Sci., pages 68--77. Springer, 1983. Google ScholarDigital Library
- N. Jacobson. Pseudo-linear transformations. Ann. of Math. (2), 38(2):484--507, 1937.Google ScholarCross Ref
- A. Loewy. Über lineare homogene Differentialsysteme und ihre Sequenten. Sitzungsb. d. Heidelb. Akad. d. Wiss., Math.-naturw. Kl., 17:1--20, 1913.Google Scholar
- A. Loewy. Über einen Fundamentalsatz für Matrizen oder lineare homogene Differentialsysteme. Sitzungsb. d. Heidelb. Akad. d. Wiss., Math.-naturw. Kl., 5:1--20, 1918.Google Scholar
- L. Pech. Algorithmes pour la sommation et l'intégration symboliques. Master's thesis, 2009.Google Scholar
- E. G. C. Poole. Introduction to the theory of linear differential equations. Oxford Univ. Press, London, 1936.Google Scholar
- L. Schlesinger. Vorlesungen über lineare Differentialgleichungen. B. G. Teubner, Leipzig, 1908.Google Scholar
- A. Schönhage and V. Strassen. Schnelle Multiplikation groß er Zahlen. Computing, 7:281--292, 1971.Google ScholarCross Ref
- A. Storjohann. High-order lifting and integrality certification. J. Symbolic Comput., 36(3--4):613--648, 2003. Google ScholarDigital Library
- V. Strassen. Gaussian elimination is not optimal. Numerische Mathematik, 13:354--356, 1969.Google ScholarDigital Library
- V. Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. In STOC'12, pages 887--898, 2012. Google ScholarDigital Library
- J. H. M. Wedderburn. Non-commutative domains of integrity. J. Reine Angew. Math., 167:129--141, 1932.Google ScholarCross Ref
- B. Zürcher. Rationale Normalformen von pseudo-linearen Abbildungen. Master's thesis, ETH Zürich, 1994.Google Scholar
Index Terms
- Complexity estimates for two uncoupling algorithms
Recommendations
Approximation of the solution of certain nonlinear ODEs with linear complexity
We study the positive stationary solutions of a standard finite-difference discretization of the semilinear heat equation with nonlinear Neumann boundary conditions. We prove that there exists a unique solution of such a discretization, which ...
Randomized and quantum complexity of nonlinear two-point BVPs
We deal with the complexity of nonlinear BVPs with nonlinear two-point boundary conditions. We consider the randomized and quantum models of computation. We assume that the right-hand side function is r times differentiable with all derivatives bounded ...
Algorithmic complexity of recursive and inductive algorithms
Super-recursive algorithms and hypercomputationThe main goal of this paper is to compare recursive algorithms such as Turing machines with such super-recursive algorithms as inductive Turing machines. This comparison is made in a general setting of dual complexity measures such as Kolmogorov or ...
Reviews
James Harold Davenport
Uncoupling is the process of producing one (or several uncoupled) equivalent higher-order differential equation(s) from a matrix of first-order (coupled) differential equations Y = MY , where Y =( y 1, ... , y n) T is a (column) vector of unknown functions, and M is an n × n matrix of rational functions. Generically, one gets one n th order differential equation, but if M is diagonal, one would like to see as output a system of n uncoupled first-order equations. More generally, if M is gauge-similar to a block-diagonal matrix, one would like to see one equation per block. The authors consider the case where M is a matrix of rational functions in the independent variable. The authors let d be the degree of M , which they define as the maximum of the degree of the numerator and denominator. In fact this is a common denominator, so is in fact written as: and therefore has degree four as far as the authors are concerned. This is a relatively common convention in the field, but the authors could have made it more explicit. The two methods considered in the paper are the classic characteristic vector method (CVM) and the Danilevski-Barkatou-Zürcher algorithm (DBZ). Folklore says that CVM is very complicated, and a naive analysis of DBZ shows the complexity to be exponential in n . Hence, uncoupling methods have not received much attention in terms of complexity theory For CVM, one can either pick a starting vector at random (with a small probability of failure) or generate one that is guaranteed to succeed. The authors show that the output of CVM has size Θ( n 3d) (a result very well matched by their experiments), and give a new variant of the CVM algorithm whose running time is Θ( n θ+1d), where θ is the exponent of matrix multiplication. Hence, if θ were 2, this algorithm would be optimal, which the authors express by calling their algorithm quasi-optimal. For DBZ, the authors give the algorithm and the complexity analysis, which is naive because in fact there is substantial cancellation, analogous to Bareiss-Dodgson cancellation in fraction-free Gaussian elimination [1,2]. Rather than prove an equivalent theorem on the precise form of the intermediate results, however, the authors relate DBZ (generic case) to CVM, and hence can use the Θ( n 3d) result from above. The complexity of DBZ (generic case) is shown to be O ( n 5d ). In the nongeneric case, they conjecture that the complexity is worse than exponential, but they have not been able to find any examples demonstrating this. I agree with the authors that this careful analysis should help rehabilitate uncoupling as a technique. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments