Data parallel evaluation-interpolation algorithm for polynomial matrix inversion (Q1801378)

The paper deals with a data parallel algorithm for the inversion of polynomial matrices (matrices, whose elements are polynomials). The inversion of such matrices is computationally laborious and needs data- parallel operations for speedup. The procedure consists of three main stages: the first one evaluates the given polynomial matrix at a certain number of required points to obtain a set of numerical matrices; in the second stage, the Moore-Penrose inverses of these matrices are found; in the third stage, having the values of the corresponding elements (these inverses) at those specified points, a rational interpolation scheme is used to reconstruct the inverse of the polynomial matrix at those given points. The algorithm generates the inverse matrix whose elements are continuous functions, in time complexity \(O(\max(tm,n^ 2))\) for an \((m\times m)\) polynomial matrix, whose determinant has an estimated degree \(n\), and \(t\) is the number of iterations to obtain an inverse. The implementation of the proposed algorithm has been done on the Connection Machine in \(CM\) FORTRAN using at most \((m^ 2(n+1))\) processors.