×

Newton’s method and FFT trading. (English) Zbl 1192.13017

Summary: Let \(\mathcal C[[z]]\) be the ring of power series over an effective ring \(\mathcal C\). R. P. Brent and H. T. Kung [J. Assoc. Comput. Mach. 25, 581–595 (1978; Zbl 0388.68052)] first showed that differential equations over \(\mathcal C[[z]]\) may be solved in an asymptotically efficient way using Newton’s method. More precisely, if \(M(n)\) denotes the complexity for multiplying two polynomials of degree \(< n\) over \(\mathcal C\), then the first \(n\) coefficients of the solution can be computed in time \(O(M(n))\). However, this complexity does not take into account the dependency on the order \(r\) of the equation, which is exponential for the original method [J. van der Hoeven, J. Symb. Comput. 34, No. 6, 479–542 (2002; Zbl 1011.68189)] and quadratic for a recent improvement [A. Bostan et al., in: Proc. ACM-SIAM Symp., New Orleans, LA, 1012–1021 (2007)]. In this paper, we present a technique for further improving the dependency on \(r\), by applying Newton’s method up to a lower order, such as \(n/r\), and trading the remaining Newton steps against a lazy or relaxed algorithm in a suitable FFT model. The technique leads to improved asymptotic complexities for several basic operations on formal power series, such as division, exponentiation and the resolution of more general linear and non-linear systems of equations.

MSC:

13F25 Formal power series rings
68W30 Symbolic computation and algebraic computation
13P99 Computational aspects and applications of commutative rings

Software:

Mathemagix
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baur, W.; Strassen, V., The complexity of partial derivatives, Theoretical Computer Science, 22, 317-330 (1983) · Zbl 0498.68028
[2] Bernstein, D., The transposition principle. http://cr.yp.to/transposition.html.; Bernstein, D., The transposition principle. http://cr.yp.to/transposition.html.
[3] Bernstein, D., 2000. Removing redundancy in high precision Newton iteration. Available from http://cr.yp.to/fastnewton.html.; Bernstein, D., 2000. Removing redundancy in high precision Newton iteration. Available from http://cr.yp.to/fastnewton.html.
[4] Bordewijk, J. L., Inter-reciprocity applied to electrical networks, Applied Scientific Research B: Electrophysics, Acoustics, Optics, Mathematical Methods, 6, 1-74 (1956) · Zbl 0072.43203
[5] Borodin, A.; Moenck, R., Fast modular transforms, Journal of Computer and System Sciences, 8, 366-386 (1974) · Zbl 0302.68064
[6] Bostan, A., Chyzak, F., Ollivier, F., Salvy, B., Schost, E., Sedoglavic, A., 2007. Fast computation of power series solutions of systems of differential equations. In: Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms. New Orleans, Louisiana, USA, pp. 1012-1021.; Bostan, A., Chyzak, F., Ollivier, F., Salvy, B., Schost, E., Sedoglavic, A., 2007. Fast computation of power series solutions of systems of differential equations. In: Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms. New Orleans, Louisiana, USA, pp. 1012-1021. · Zbl 1302.65180
[7] Bostan, A.; Schost, É., Polynomial evaluation and interpolation on special sets of points, Journal of Complexity, 21, 4, 420-446 (2005), festschrift for the 70th Birthday of Arnold Schönhage · Zbl 1101.68039
[8] Brent, R.; Kung, H., Fast algorithms for manipulating formal power series, Journal of the ACM, 25, 581-595 (1978) · Zbl 0388.68052
[9] Cantor, D.; Kaltofen, E., On fast multiplication of polynomials over arbitrary algebras, Acta Informatica, 28, 693-701 (1991) · Zbl 0766.68055
[10] Cook, S., 1966. On the minimum computation time of functions. Ph.D. Thesis, Harvard University.; Cook, S., 1966. On the minimum computation time of functions. Ph.D. Thesis, Harvard University.
[11] Cooley, J.; Tukey, J., An algorithm for the machine calculation of complex Fourier series, Mathematics of Computation, 19, 297-301 (1965) · Zbl 0127.09002
[12] Coppersmith, D., Winograd, S., 1987. Matrix multiplication via arithmetic progressions. In: Proc. of the 19th Annual Symposium on Theory of Computing. New York City, pp. 1-6.; Coppersmith, D., Winograd, S., 1987. Matrix multiplication via arithmetic progressions. In: Proc. of the 19th Annual Symposium on Theory of Computing. New York City, pp. 1-6. · Zbl 0702.65046
[13] 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
[14] Hanrot, G., Zimmermann, P., 2002. A long note on Mulders’ short product. Research Report 4654, INRIA. Available from http://www.loria.fr/ hanrot/Papers/mulders.ps.; Hanrot, G., Zimmermann, P., 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
[15] Hanrot, G., Zimmermann, P., 2004. Newton iteration revisited. http://www.loria.fr/ zimmerma/papers/fastnewton.ps.gz.; Hanrot, G., Zimmermann, P., 2004. Newton iteration revisited. http://www.loria.fr/ zimmerma/papers/fastnewton.ps.gz.
[16] Harvey, D., 2009a. Faster algorithms for the square root and reciprocal of power series. http://arxiv.org/abs/0910.1926.; Harvey, D., 2009a. Faster algorithms for the square root and reciprocal of power series. http://arxiv.org/abs/0910.1926.
[17] Harvey, D., 2009b. Faster exponentials of power series. http://arxiv.org/abs/0911.3110.; Harvey, D., 2009b. Faster exponentials of power series. http://arxiv.org/abs/0911.3110.
[18] Karatsuba, A.; Ofman, J., Multiplication of multidigit numbers on automata, Soviet Physics Doklady, 7, 595-596 (1963)
[19] Lecerf, G.; Schost, E., Fast multivariate power series multiplication in characteristic zero, SADIO Electronic Journal on Informatics and Operations Research, 5, 1, 1-10 (2003) · Zbl 1209.68618
[20] Lohner, R., 1988. Einschließung der Lösung gewöhnlicher Anfangs- und randwertaufgaben und anwendugen. Ph.D. Thesis, Universität Karlsruhe.; Lohner, R., 1988. Einschließung der Lösung gewöhnlicher Anfangs- und randwertaufgaben und anwendugen. Ph.D. Thesis, Universität Karlsruhe.
[21] Lohner, R., On the ubiquity of the wrapping effect in the computation of error bounds, (Kulisch, U.; Lohner, R.; Facius, A., Perspectives on enclosure methods (2001), Springer: Springer Vienna, New York), 201-217 · Zbl 0990.65073
[22] Makino, K.; Berz, M., Remainder differential algebras and their applications, (Berz, M.; Bischof, C.; Corliss, G.; Griewank, A., Computational Differentiation: Techniques, Applications and Tools (1996), SIAM: SIAM Philadelphia), 63-74 · Zbl 0867.68062
[23] Makino, K., Berz, M., 2004. Suppression of the wrapping effect by Taylor model-based validated integrators. Tech. Rep. MSU Report MSUHEP 40910, Michigan State University.; Makino, K., Berz, M., 2004. Suppression of the wrapping effect by Taylor model-based validated integrators. Tech. Rep. MSU Report MSUHEP 40910, Michigan State University. · Zbl 1133.65045
[24] Moenck, R., Borodin, A., 1972. Fast modular transforms via division. In: Thirteenth Annual IEEE Symposium on Switching and Automata Theory. Univ. Maryland, College Park, MD, pp. 90-96.; Moenck, R., Borodin, A., 1972. Fast modular transforms via division. In: Thirteenth Annual IEEE Symposium on Switching and Automata Theory. Univ. Maryland, College Park, MD, pp. 90-96.
[25] Moenck, R.; Carter, J., Approximate algorithms to derive exact solutions to systems of linear equations, (Symbolic and Algebraic Computation (EUROSAM’79, Marseille). Symbolic and Algebraic Computation (EUROSAM’79, Marseille), LNCS, vol. 72 (1979), Springer: Springer Berlin), 65-73
[26] Moore, R., Interval Analysis (1966), Prentice Hall: Prentice Hall Englewood Cliffs, NJ · Zbl 0176.13301
[27] Pan, V., How to multiply matrices faster, (Lect. Notes in Math., vol. 179 (1984), Springer) · Zbl 0548.65022
[28] Schönhage, A., Variations on computing reciprocals of power series, Information Processing Letters, 74, 41-46 (2000) · Zbl 1014.68065
[29] Schönhage, A.; Strassen, V., Schnelle Multiplikation grosser Zahlen, Computing, 7, 281-292 (1971) · Zbl 0223.68007
[30] Schulz, G., Iterative Berechnung der reziproken Matrix, Zeitschrift für Angewandte Mathematik und Mechanik, 13, 57-59 (1933) · JFM 59.0535.04
[31] Strassen, V., Gaussian elimination is not optimal, Numerische Mathematik, 13, 352-356 (1969) · Zbl 0185.40101
[32] Strassen, V., Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten, Numerische Mathematik, 20, 238-251 (1973) · Zbl 0251.65036
[33] 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
[34] van der Hoeven, J., 1997. Lazy multiplication of formal power series. In: Küchlin, W.W. (Ed.), Proc. ISSAC’97. Maui, Hawaii, pp. 17-20.; van der Hoeven, J., 1997. Lazy multiplication of formal power series. In: Küchlin, W.W. (Ed.), Proc. ISSAC’97. Maui, Hawaii, pp. 17-20. · Zbl 0932.68135
[35] van der Hoeven, J., Relax, but don’t be too lazy, Journal of Symbolic Computation, 34, 479-542 (2002) · Zbl 1011.68189
[36] van der Hoeven, J., 2004. The truncated Fourier transform and applications. In: Gutierrez, J. (Ed.), Proc. ISSAC 2004, July 4-7. Univ. of Cantabria, Santander, Spain, pp. 290-296.; van der Hoeven, J., 2004. The truncated Fourier transform and applications. In: Gutierrez, J. (Ed.), Proc. ISSAC 2004, July 4-7. Univ. of Cantabria, Santander, Spain, pp. 290-296. · Zbl 1064.65158
[37] van der Hoeven, J., 2005. Notes on the Truncated Fourier Transform. Tech. Rep. 2005-5. Université Paris-Sud, Orsay, France.; van der Hoeven, J., 2005. Notes on the Truncated Fourier Transform. Tech. Rep. 2005-5. Université Paris-Sud, Orsay, France. · Zbl 1074.62015
[38] van der Hoeven, J., 2006. Newton’s method and FFT trading. Tech. Rep. 2006-17. Univ. Paris-Sud,http://www.texmacs.org/joris/fnewton/fnewton-abs.html.; van der Hoeven, J., 2006. Newton’s method and FFT trading. Tech. Rep. 2006-17. Univ. Paris-Sud,http://www.texmacs.org/joris/fnewton/fnewton-abs.html. · Zbl 1192.13017
[39] van der Hoeven, J., New algorithms for relaxed multiplication, Journal of Symbolic Computation, 42, 8, 792-802 (2007) · Zbl 1130.68103
[40] van der Hoeven, J., On effective analytic continuation, Mathematics in Computer Science, 1, 1, 111-175 (2007) · Zbl 1154.68574
[41] van der Hoeven, J., et al. 2002. Mathemagix. http://www.mathemagix.org.; van der Hoeven, J., et al. 2002. Mathemagix. http://www.mathemagix.org.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.