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

From MaRDI portal





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
    0 references
    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
    0 references

    Identifiers