Data parallel evaluation-interpolation algorithm for polynomial matrix inversion

Abstract

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, n²)) 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 (m²(n+1)) processors. This algorithm can be directly extended to invert arbitrary function matrices by proper choice of evaluation-interpolation points.