Relaxed mltiplication using the middle product

ABSTRACT

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. In this paper, we present a new relaxed multiplication algorithm for the resolution of linear equations. The algorithm has the same asymptotic time complexity as our previous algorithms, but we improve the space overhead in the divide and conquer model and the constant factor in the F.F.T. model.

REFERENCES

• 1: David G. Cantor , Erich Kaltofen, On fast multiplication of polynomials over arbitrary algebras, Acta Informatica, v.28 n.7, p.693-701, Oct. 1991 [doi>10.1007/BF01178683]
• 2: Cooley, J., and Tukey, J. An algorithm for the machine calculation of complex Fourier series. Math. Computat. 19 (1965), 297--301.
• 3: Hanrot, G., Quercia, M., and Zimmermann, P. Speeding up the division and square root of power series. Research Report 3973, INRIA, July 2000. Available from http://www.inria.fr/RRRT/RR-3973.html.
• 4: Hanrot, G., Quercia, M., and Zimmermann, P. The middle product algorithm I. speeding up the division and square root of power series. Submitted, 2002.
• 5: Hanrot, G., and Zimmermann, P. A long note on mulders' short product. Research Report 4654, INRIA, Dec. 2002. Available from http://www.loria.fr/˜hanrot/Papers/mulders.ps.
• 6: Karatsuba, A., and Ofman, J. Multiplication of multidigit numbers on automata. Soviet Physics Doklady 7 (1963), 595--596.
• 7: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 8: Mulders, T. On short multiplication and division. AAECC 11, 1 (2000), 69--88.
• 9: Schönhage, A., and Strassen, V. Schnelle Multiplikation grosser Zahlen. Computing 7 7 (1971), 281--292.
• 10: Joris van der Hoeven, Lazy multiplication of formal power series, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.17-20, July 21-23, 1997, Kihei, Maui, Hawaii, United States [doi>10.1145/258726.258738]
• 11: Joris Van der Hoeven, Relax, but don't be too lazy, Journal of Symbolic Computation, v.34 n.6, p.479-542, December 2002 [doi>10.1006/jsco.2002.0562]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Multiple precision arithmetic

General Terms:
Algorithms

Keywords:
middle product, power series, relaxed multiplication