# zbMATH — the first resource for mathematics

New algorithms for relaxed multiplication. (English) Zbl 1130.68103
Summary: In previous work, we have introduced the technique of relaxed power series computations. With this technique, it is possible to solve implicit equations almost as quickly as doing the operations which occur in the implicit equation. Here “almost as quickly” means that we need to pay a logarithmic overhead. In this paper, we show how to reduce this logarithmic factor in the case when the constant ring has sufficiently many $$2^p$$th roots of unity.

##### MSC:
 68W30 Symbolic computation and algebraic computation 13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
##### Keywords:
power series; multiplication; algorithm; FFT; computer algebra
##### Software:
Mmxlib; Mathemagix
Full Text:
##### References:
 [1] Bostan, A., Chyzak, F., Ollivier, F., Salvy, B., Schost, E., Sedoglavic, A., April 2006. Fast computation of power series solutions of systems of differential equation. 13 pages, preprint (submitted for publicaton) · Zbl 1302.65180 [2] Brent, R.; Kung, H., Fast algorithms for manipulating formal power series, Journal of the ACM, 25, 581-595, (1978) · Zbl 0388.68052 [3] Cantor, D.; Kaltofen, E., On fast multiplication of polynomials over arbitrary algebras, Acta informatica, 28, 693-701, (1991) · Zbl 0766.68055 [4] Cook, S., 1966. On the minimum computation time of functions. Ph.D. Thesis, Harvard University [5] Cooley, J.; Tukey, J., An algorithm for the machine calculation of complex Fourier series, Mathematics of computation, 19, 297-301, (1965) · Zbl 0127.09002 [6] Hanrot, G.; Quercia, M.; Zimmermann, P., The middle product algorithm I. speeding up the division and square root of power series, Applicable algebra in engineering, communication and computing, 14, 6, 415-438, (2004) · Zbl 1064.68094 [7] Hanrot, G., Zimmermann, P., December 2002. A long note on Mulders’ short product. Research Report 4654. INRIA. Available from http://www.loria.fr/ hanrot/Papers/mulders.ps · Zbl 1161.65301 [8] Karatsuba, A.; Ofman, J., Multiplication of multidigit numbers on automata, Soviet physics doklady, 7, 595-596, (1963) [9] Knuth, D., () [10] Schönhage, A.; Strassen, V., Schnelle multiplikation grosser zahlen, Computing, 7, 281-292, (1971) · Zbl 0223.68007 [11] Sedoglavic, A., 2001. Méthodes seminumériques en algèbre différentielle; applications à l’étude des propriétés structurelles de systèmes différentiels algébriques en automatique. Ph.D. Thesis, École Polytechnique [12] Toom, A., The complexity of a scheme of functional elements realizing the multiplication of integers, Soviet mathematics, 4, 2, 714-716, (1963) · Zbl 0203.15604 [13] van der Hoeven, J., July 1997. Lazy multiplication of formal power series. In: Küchlin, W.W. (Ed.), Proc. ISSAC’97, Maui, Hawaii, pp. 17-20 · Zbl 0932.68135 [14] van der Hoeven, J., Relax, but don’t be too lazy, Journal of symbolic computation, 34, 479-542, (2002) · Zbl 1011.68189 [15] van der Hoeven, J., 2003a. New algorithms for relaxed multiplication. Tech. Rep. 2003-44, Université Paris-Sud, Orsay, France · Zbl 1130.68103 [16] van der Hoeven, J., August 2003b. Relaxed multiplication using the middle product. In: Bronstein, M. (Ed.), Proc. ISSAC’03. Philadelphia, USA, pp. 143-147 · Zbl 1072.68706 [17] van der Hoeven, J., 2006a. Newton’s method and FFT trading. Tech. Rep. 2006-17, Univ. Paris-Sud, Journal of Symbolic Computation (submitted for publication) · Zbl 1192.13017 [18] van der Hoeven, J., 2006b. On effective analytic continuation. Tech. Rep. 2006-15, Univ. Paris-Sud · Zbl 1154.68574 [19] van der Hoeven, J., et al. 2002. Mmxlib: The standard library for Mathemagix. http://www.mathemagix.org/mml.html
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.