Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9501317 | Journal of Complexity | 2005 | 15 Pages |
Abstract
We present an inversion algorithm for nonsingular nÃn matrices whose entries are degree d polynomials over a field. The algorithm is deterministic and, when n is a power of two, requires Oâ¼(n3d) field operations for a generic input; the soft-O notation Oâ¼ indicates some missing log(nd) factors. Up to such logarithmic factors, this asymptotic complexity is of the same order as the number of distinct field elements necessary to represent the inverse matrix.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Analysis
Authors
Claude-Pierre Jeannerod, Gilles Villard,