  We consider space-saving versions of several important operations on
univariate polynomials, namely power series inversion and division, division
with remainder, multi-point evaluation, and interpolation. Now-classical
results show that such problems can be solved in (nearly) the same asymptotic
time as fast polynomial multiplication. However, these reductions, even when
applied to an in-place variant of fast polynomial multiplication, yield
algorithms which require at least a linear amount of extra space for
intermediate results. We demonstrate new in-place algorithms for the
aforementioned polynomial computations which require only constant extra space
and achieve the same asymptotic running time as their out-of-place
counterparts. We also provide a precise complexity analysis so that all
constants are made explicit, parameterized by the space usage of the underlying
multiplication algorithms.
