Fast In-place Accumulation

This paper deals with simultaneously fast and in-place algorithms for
formulae where the result has to be linearly accumulated;
in other-words, some output variables are also input variables, linked
by a linear dependency.

Fundamental examples include the in-place accumulated multiplication of
polynomials or matrices, C += AB.

The difficulty is to combine in-place computations with fast algorithms:
those usually come at the expense of (potentially large) extra temporary
space, but with accumulation the output variables are not even available
to store intermediate values.

We first propose a novel automatic design of fast and in-place
accumulating algorithms for any bilinear formulae (and thus for
polynomial and matrix multiplication) and then extend it to any linear
accumulation of a collection of functions.

For this, we relax the in-place model to any algorithm allowed to modify
its inputs, provided that those are restored to their initial state
afterwards.

This allows us, in fine, to derive unprecedented in-place accumulating
algorithms for Strassen-like matrix multiplication, fast accumulating
and over-place Toeplitz system solving, as well as for fast polynomial
multiplication, convolution and modular
operations.