Fast algorithms for composition and reversion of
multivariate power series
39. R. P. Brent and
H. T. Kung,
Fast algorithms for composition
and reversion of multivariate power series
(preliminary version),
in Proceedings of a Conference on Theoretical Computer Science
Department of Computer Science,
University of Waterloo, Waterloo, Ontario (August 1977), 149-158.
Abstract:
dvi (3K),
pdf (78K).
Extended abstract:
pdf (112K).
Paper:
pdf (631K).
Abstract
In our earlier papers
[29,
45],
we gave fast algorithms for
manipulating dense univariate power series.
In this paper, fast algorithms
for composition and reversion of dense multivariate
power series are presented.
The new algorithms require substantially less operations
than the best previously known algorithms. The relative advantage
of the new algorithms increases with the number of variables in the
multivariate power series.
Comments
Although called a "preliminary version" this was in fact the final version.
The univariate case is considered in Brent and Kung
[45],
and generalized composition is considered in
Brent and Traub
[50].
It should be noted that most multivariate power series occurring in
practice are sparse,
i.e. many of the coefficients are zero, but our
algorithms do not take advantage of this.
Go to next publication
Return to Richard Brent's index page