Article ID Journal Published Year Pages File Type
4608566 Journal of Complexity 2015 12 Pages PDF
Abstract
Improved cost estimates are given for the problem of computing the inverse of an n×n matrix of univariate polynomials over a field. A deterministic algorithm is demonstrated that has worst case complexity (n3s)1+o(1) field operations, where s≥1 is an upper bound for the average column degree of the input matrix. Here, the “+o(1)” in the exponent indicates a missing factor c1(logns)c2 for positive real constants c1 and c2. As an application we show how to compute the largest invariant factor of the input matrix in (nωs)1+o(1) field operations, where ω is the exponent of matrix multiplication.
Related Topics
Physical Sciences and Engineering Mathematics Analysis
Authors
, , ,