Straight-line computation of the polynomial matrix inverse

Abstract

(eng) We present an inversion algorithm for nonsingular n x n matrices whose entries are degree d polynomials over a field. The algorithm is deterministic and requires O~(n^3d) field operations for a generic input. The ``soft Oh'' notation O~ indicates some missing log(nd) factors. The polynomial matrix inverse can thus be computed by a straight-line program whose size is - asymptotically and up to logarithmic factors - the size of its output.