  Mahler equations relate evaluations of the same function $f$ at iterated
$b$th powers of the variable. They arise in particular in the study of
automatic sequences and in the complexity analysis of divide-and-conquer
algorithms. Recently, the problem of solving Mahler equations in closed form
has occurred in connection with number-theoretic questions. A difficulty in the
manipulation of Mahler equations is the exponential blow-up of degrees when
applying a Mahler operator to a polynomial. In this work, we present algorithms
for solving linear Mahler equations for series, polynomials, and rational
functions, and get polynomial-time complexity under a mild assumption.
Incidentally, we develop an algorithm for computing the gcrd of a family of
linear Mahler operators.
