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=(y1, ... ,yn)T is a (column) vector of unknown functions, and M is an n × n matrix of rational functions. Generically, one gets one nth 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 Θ(n3d) (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 Θ(n3d) result from above. The complexity of DBZ (generic case) is shown to be O(n5d). 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.
