  Polynomial system solving is a classical problem in mathematics with a wide
range of applications. This makes its complexity a fundamental problem in
computer science. Depending on the context, solving has different meanings. In
order to stick to the most general case, we consider a representation of the
solutions from which one can easily recover the exact solutions or a certified
approximation of them. Under generic assumption, such a representation is given
by the lexicographical Gr\"obner basis of the system and consists of a set of
univariate polynomials. The best known algorithm for computing the
lexicographical Gr\"obner basis is in $\widetilde{O}(d^{3n})$ arithmetic
operations where $n$ is the number of variables and $d$ is the maximal degree
of the equations in the input system. The notation $\widetilde{O}$ means that
we neglect polynomial factors in $n$. We show that this complexity can be
decreased to $\widetilde{O}(d^{\omega n})$ where $2 \leq \omega < 2.3727$ is
the exponent in the complexity of multiplying two dense matrices. Consequently,
when the input polynomial system is either generic or reaches the B\'ezout
bound, the complexity of solving a polynomial system is decreased from
$\widetilde{O}(D^3)$ to $\widetilde{O}(D^\omega)$ where $D$ is the number of
solutions of the system. To achieve this result we propose new algorithms which
rely on fast linear algebra. When the degree of the equations are bounded
uniformly by a constant we propose a deterministic algorithm. In the unbounded
case we present a Las Vegas algorithm.
