### Exact Computations on Polynomial and Integer Matrices

**Gilles Villard**

CNRS / École Normale Supérieure de Lyon

One may consider that the algebraic complexity of basic linear algebra over
an abstract field K is well known. Indeed, if w is the exponent of matrix multiplication
over a field K, for instance computing the determinant, the matrix inverse,
the rank or the characteristic polynomial of an n x n matrix can be done in
softO(n^w) operations in K (the same holds for the solution of many other problems).
Over more concrete domains like K[x] or Z, the impact of data size (degree or
bit length) on the problem's complexity is much less known. Until recently,
it was even considered that an extra factor n was involved, leading to typical
costs in softO(n.n^w log|A|) for instance for computing the determinant exactly
(log|A| is the degree of the entries over K[x] or the bit length of the entries
over Z).

For reducing the complexity, a main concern is to exploit the interplay of
the algebraic structure with the intermediate expression swell. Several authors
have successfully addressed the question during the last three years. The aim
of this talk is to survey these studies, especially around the determinant and
the matrix inverse. It is now known that the determinant of an integer matrix
can be computed in softO(n^w log|A|) [Storjohann 2003]. It is also known that
the inversion of a generic polynomial matrix can be computed in softO(n^3 d)
[Jeannerod & Villard 2002]. Since the latter estimates are roughly the current
estimates for matrix multiplication over K[x] and Z, two natural questions arise.
If MM(n,d) is the cost for multiplying two n x n matrices of degree d over K,
which problems can be solved in softO(MM(n,d)) operations in K? If MM(n,log|A|)
is the cost for multiplying two n x n integer matrices, which problems can be
solved in softO(MM(n,log|A|)) bit operations?

Return to Program