The complexity of bivariate power series arithmetic
Inspired by Schonhage's discussion in the Proc. 11th Applied Algebra and Error Correcting Codes Conference (AAECC), Lecture Notes in Comput. Sci., Springer, Berlin, Vol. 948, 1995 pp. 70, we study the multiplicative complexity of the multiplication, squaring, inversion, and division of bivariate power series modulo the "triangular" and "quadratic" ideals (Xd+1,(XY)-Y-d,Xd-1 Y-2,..., Yd+1) and (Xd+1, Yd+1), respectively. For multiplication, we obtain the lower bounds 5/4 d(2) -O(d) and 2 1/3 d(2) - O(d) for the triangular and quadratic case, respectively, opposed to the upper bounds 3/2 d(2) + O(d) and 3d(2) + O(d). For squaring, we prove the lower bounds 7/8 d(2) - O(d) and 1 3/5 d(2) - O(d). As upper bounds, we have d(2) + O(d) and 2 1/2 d(2) + O(d) for the triangular and quadratic case, respectively. Concerning inversion, the obtained lower bounds coincide with those of squaring. As upper bounds, we show 3 5/6 d(2) +O(d) and 8 1/3 d(2) + O(d), respectively. The lower bounds for division are those of multiplication. The upper bounds follow from combining the bounds for inversion and multiplication. All of the above lower bounds hold over arbitrary fields (in the case of multiplication and division) and over fields of characteristic distinct from two (in the case of squaring and inversion), respectively. All upper bounds are valid for fields that "support FFTs", that is, fields that have characteristic zero and contain all roots of unity. (C) 2002 Elsevier Science B.V. All rights reserved.
bivariate power series multiplicative complexity multiplication division