  The diagonal of a multivariate power series F is the univariate power series
Diag(F) generated by the diagonal terms of F. Diagonals form an important class
of power series; they occur frequently in number theory, theoretical physics
and enumerative combinatorics. We study algorithmic questions related to
diagonals in the case where F is the Taylor expansion of a bivariate rational
function. It is classical that in this case Diag(F) is an algebraic function.
We propose an algorithm that computes an annihilating polynomial for Diag(F).
We give a precise bound on the size of this polynomial and show that
generically, this polynomial is the minimal polynomial and that its size
reaches the bound. The algorithm runs in time quasi-linear in this bound, which
grows exponentially with the degree of the input rational function. We then
address the related problem of enumerating directed lattice walks. The insight
given by our study leads to a new method for expanding the generating power
series of bridges, excursions and meanders. We show that their first N terms
can be computed in quasi-linear complexity in N, without first computing a very
large polynomial equation.
