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?