Popov Form Computation for Matrices of Ore Polynomials
Mohamed Khochtali, Johan Rosenkilde, Arne Storjohann · 2017
Let F[∂ ; σ, δ] be a ring of Ore polynomials over a field. We give a new deterministic algorithm for computing the Popov form P of a non-singular matrix A ∈ F[∂ ; σ, δ]n x n. Our main focus is to ensure controlled growth in the size of coefficients from F in the case F = K(z), and even K = Q. Our algorithms are based on constructing from A a linear system over F and performing a structured fraction-free Gaussian elimination. The algorithm is output sensitive, with a cost that depends on the orthogonality defect of the input matrix: the sum of the row degrees in A minus the sum of the row degrees in P. The resulting bit-complexity for the differential and shift polynomial case over Q(z) improves upon the previous best.