Improved cost estimates are given for the problem of computing the inverse of an n x n matrix of univariate polynomials over a field. A deterministic algorithm is demonstrated that has worst case complexity (n(3)s)(1+...
详细信息
Improved cost estimates are given for the problem of computing the inverse of an n x n matrix of univariate polynomials over a field. A deterministic algorithm is demonstrated that has worst case complexity (n(3)s)(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 c(1) (log ns)(c2) for positive real constants c(1) and c(2). As an application we show how to compute the largest invariant factor of the input matrix in (n(omega)s)(1+o(1)) field operations, where omega is the exponent of matrix multiplication. (C) 2014 Elsevier Inc. All rights reserved.
暂无评论