Fast Computation of Shifted Popov Forms of Polynomial Matrices via Systems of Modular Polynomial Equations
share
We give a Las Vegas algorithm which computes the shifted Popov form of an m × 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. Using partial linearization, we reduce the problem to the case d <σ/m where σ is the generic determinant bound, with σ / m bounded from above by both the average row degree and the average column degree of the matrix. The cost above becomes O(m^ωσ/m ), improving upon the cost of the fastest previously known algorithm for row reduction, which is deterministic. Our algorithm first builds a system of modular equations whose solution set is the row space of the input matrix, and then finds the basis in shifted Popov form of this set. We give a deterministic algorithm for this second step supporting arbitrary moduli in O(m^ω-1σ) field operations, where m is the number of unknowns and σ is the sum of the degrees of the moduli. This extends previous results with the same cost bound in the specific cases of order basis computation and M-Padé approximation, in which the moduli are products of known linear factors.
READ FULL TEXT