Let S be a multivariate power series ring over a field of characteristic zero. The article [5] presents an asymptotically fast algorithm for multiplying two elements of S truncated according to total degree. Up to logarithmic factors, the complexity of the algorithm is optimal, in the sense that it is linear in the size of the output.
D = deg  (  m^{d+1}  )  = 

. 

: 

R_{t} : 

E_{P} : 

I : 

(1)  F ¬ R_{t}(f); G ¬ R_{t}(g);  // new representation  
(2)  for i in (P_{1},...,P_{C}) do  // evaluation  
F_{Pi} ¬ E_{Pi}(F); G_{Pi} ¬ E_{Pi}(G);  
(3)  for i to C do  // univariate multiplication  
H_{Pi} ¬ F_{Pi}G_{Pi};  
(4)  R_{t}(h) ¬ I(H_{P1},...,H_{PC});  // interpolation  
(5)  h ¬ homogenization in degree with respect to x_{1}  // reconstruction  
in R_{t}(h);  
return h; 
O  (  D log^{3}D loglogD  )  . 
V_{t} : 

K_{t} : 

http://www.medicis.polytechnique.fr/~schost/
,
2001.This document was translated from L^{A}T_{E}X by H^{E}V^{E}A.