Data parallel evaluation-interpolation algorithm for polynomial matrix inversion (Q1801378)
From MaRDI portal
![]() | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Data parallel evaluation-interpolation algorithm for polynomial matrix inversion |
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Data parallel evaluation-interpolation algorithm for polynomial matrix inversion |
scientific article |
Statements
Data parallel evaluation-interpolation algorithm for polynomial matrix inversion (English)
0 references
10 March 1994
0 references
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.
0 references
polynomial matrix inversion
0 references
data parallel algorithm
0 references
polynomial matrices
0 references
Moore-Penrose inverses
0 references
rational interpolation scheme
0 references
Connection Machine
0 references