Fraction-free algorithm for the computation of diagonal forms matrices over Ore domains using Gröbner bases

This paper is a sequel to “Computing diagonal form and Jacobson normal form of a matrix using Gröbner bases” (Levandovskyy and Schindelar, 2011). We present a new fraction-free algorithm for the computation of a diagonal form of a matrix over a certain non-commutative Euclidean domain over a computable field with the help of Gröbner bases. This algorithm is formulated in a general constructive framework of non-commutative Ore localizations of G-algebras (OLGAs). We use the splitting of the computation of a normal form for matrices over Ore localizations into the diagonalization and the normalization processes. Both of them can be made fraction-free. For a given matrix M over an OLGA R, we provide a diagonalization algorithm to compute U,V and D with fraction-free entries such that UMV=D holds and D is diagonal. The fraction-free approach allows to obtain more information on the associated system of linear functional equations and its solutions, than the classical setup of an operator algebra with coefficients in rational functions. In particular, one can handle distributional solutions together with, say, meromorphic ones. We investigate Ore localizations of common operator algebras over K[x] and use them in the unimodularity analysis of transformation matrices U,V. In turn, this allows to lift the isomorphism of modules over an OLGA Euclidean domain to a smaller polynomial subring of it. We discuss the relation of this lifting with the solutions of the original system of equations. Moreover, we prove some new results concerning normal forms of matrices over non-simple domains. Our implementation in the computer algebra system Singular:Plural follows the fraction-free strategy and shows impressive performance, compared with methods which directly use fractions. In particular, we experience a moderate swell of coefficients and obtain simple transformation matrices. Thus the method we propose is well suited for solving nontrivial practical problems.