Fast Computation of Shifted Popov Forms of Polynomial Matrices via Systems of Modular Polynomial Equations
Vincent Neiger · 2016
We give a Las Vegas algorithm which computes the shifted Popov form of an m x m nonsingular polynomial matrix of degree d in expected ~O(mω d) field operations, where ω is the exponent of matrix multiplication and ~O(·) indicates that logarithmic factors are omitted. This is the first algorithm in ~O(mω d) for shifted row reduction with arbitrary shifts.