Data parallel evaluation-interpolation algorithm for polynomial matrix inversion

This paper describes a data parallel algorithm for the inversion of polynomial matrix using evaluation and rational interpolation. The algorithm generates the inverse matrix whose elements are continued fractions, in time complexity O(max(tm, n2)) for an (m × m) polynomial matrix, whose determinant has an estimated degree n, t is the number of iteration to obtain an inverse (or Moore-Penrose inverse). The implementation of the algorithm has been done on the Connection Machine in CM FORTRAN using at most (m2(n+1)) processors. This algorithm can be directly extended to invert arbitrary function matrices by proper choice of evaluation-interpolation points