Computing Popov Forms of Polynomial Matrices

[摘要] This thesis gives a deterministic algorithm to transform a row reduced matrix to canon-ical Popov form. Given as input a row reduced matrix R over K[x], K a field, our algorithmcomputes the Popov form in about the same time as required to multiply together overK[x] two matrices of the same dimension and degree as R. Randomization can be used toextend the algorithm for rectangular input matrices of full row rank. Thus we give a LasVegas algorithm that computes the Popov decomposition of matrices of full row rank. We also show that the problem of transforming a row reduced matrix to Popov form is at leastas hard as polynomial matrix multiplication.

[发布机构] University of Waterloo

[关键词] Computer Science