Computing Characteristic Polynomials of Matrices of Structured Polynomials

摘要

We present a parallel modular algorithm for finding characteristic polynomials of matrices with integer coefficient bivariate polynomials. For each prime, evaluation and interpolation gives us the bridge between polynomial matrices and matrices over a finite field so that the Hessenberg algorithm can be used.