High-order lifting and integrality certification

AbstractReductions to polynomial matrix multiplication are given for some classical problems involving a nonsingular input matrix over the ring of univariate polynomials with coefficients from a field. High-order lifting is used to compute the determinant, the Smith form, and a rational system solution with about the same number of field operations as required to multiply together two matrices having the same dimension and degree as the input matrix. Integrality certification is used to verify correctness of the output. The algorithms are space efficient