Calcul analytique

Joris van der Hoeven[1]

  • [1] CNRS, LIX École polytechnique 91128 Palaiseau Cedex France

Les cours du CIRM (2011)

  • Volume: 2, Issue: 1, page 1-85
  • ISSN: 2108-7164

How to cite


Hoeven, Joris van der. "Calcul analytique." Les cours du CIRM 2.1 (2011): 1-85. <>.

affiliation = {CNRS, LIX École polytechnique 91128 Palaiseau Cedex France},
author = {Hoeven, Joris van der},
journal = {Les cours du CIRM},
language = {fre},
number = {1},
pages = {1-85},
publisher = {CIRM},
title = {Calcul analytique},
url = {},
volume = {2},
year = {2011},

AU - Hoeven, Joris van der
TI - Calcul analytique
JO - Les cours du CIRM
PY - 2011
VL - 2
IS - 1
SP - 1
EP - 85
LA - fre
UR -
ER -


  1. O. Aberth. Computable analysis. McGraw-Hill, New York, 1980. Zbl0461.03015
  2. G. Alefeld and J. Herzberger. Introduction to interval analysis. Academic Press, New York, 1983. Zbl0552.65041MR733988
  3. ANSI/IEEE. IEEE standard for binary floating-point arithmetic. Technical report, ANSI/IEEE, New York, 2008. ANSI-IEEE Standard 754-2008. Revision of IEEE 754-1985, approved on June 12, 2008 by IEEE Standards Board. 
  4. D. Bates, J. Hauenstein, A. Sommese, and C. Wampler. Bertini : Software for numerical algebraic geometry., 2006. 
  5. C. Beltrán and L.M. Pardo. Smale’s 17th problem : Average polynomial time to compute affine and projective solutions. Journal of the AMS, 2008. To appear. Zbl1206.90173
  6. D. Bini and V.Y. Pan. Polynomial and matrix computations. Vol. 1. Birkhäuser Boston Inc., Boston, MA, 1994. Fundamental algorithms. Zbl0809.65012MR1289412
  7. D. A. Bini and G. Fiorentino. Design, analysis, and implementation of a multiprecision polynomial rootfinder. Numerical Algorithms, 23 :127–173, 2000. Zbl1018.65061MR1772050
  8. E. Bishop and D. Bridges. Foundations of constructive analysis. Die Grundlehren der mathematische Wissenschaften. Springer, Berlin, 1985. Zbl0656.03042MR804042
  9. J. Blanck, V. Brattka, and P. Hertling, editors. Computability and complexity in analysis, volume 2064 of Lect. Notes in Comp. Sc., Berlin, Heidelberg, 2001. Springer. Zbl0967.00056MR1893067
  10. A. Bostan, F. Chyzak, F. Ollivier, B. Salvy, É. Schost, and A. Sedoglavic. Fast computation of power series solutions of systems of differential equations. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms, pages 1012–1021, New Orleans, Louisiana, U.S.A., January 2007. Zbl1302.65180MR2485252
  11. A. Bostan, G. Lecerf, and É. Schost. Tellegen’s principle into practice. In Proceedings of ISSAC 2003, pages 37–44. ACM, 2003. Zbl1072.68649
  12. B.L.J. Braaksma. Multisummability and Stokes multipliers of linear meromorphic differential equations. J. Diff. Eq, 92 :45–75, 1991. Zbl0729.34005MR1113588
  13. R.P. Brent and H.T. Kung. O ( ( n log n ) 3 / 2 ) algorithms for composition and reversion of power series. In J.F. Traub, editor, Analytic Computational Complexity, Pittsburg, 1975. Proc. of a symposium on analytic computational complexity held by Carnegie-Mellon University. Zbl0342.65010
  14. R.P. Brent and H.T. Kung. Fast algorithms for composition and reversion of multivariate power series. In Proc. Conf. Th. Comp. Sc., pages 149–158, Waterloo, Ontario, Canada, August 1977. University of Waterloo. Zbl0411.68043
  15. R.P. Brent and H.T. Kung. Fast algorithms for manipulating formal power series. Journal of the ACM, 25 :581–595, 1978. Zbl0388.68052MR520733
  16. B. Buchberger. Ein Algorithmus zum auffinden der Basiselemente des Restklassenringes nach einem null-dimensionalen Polynomideal. PhD thesis, University of Innsbruck, 1965. 
  17. D.G. Cantor and E. Kaltofen. On fast multiplication of polynomials over arbitrary algebras. Acta Informatica, 28 :693–701, 1991. Zbl0766.68055MR1129288
  18. D.V. Chudnovsky and G.V. Chudnovsky. Computer algebra in the service of mathematical physics and number theory (computers in mathematics, stanford, ca, 1986). In Lect. Notes in Pure and Applied Math., volume 125, pages 109–232, New-York, 1990. Dekker. Zbl0712.11078MR1068536
  19. J.W. Cooley and J.W. Tukey. An algorithm for the machine calculation of complex Fourier series. Math. Computat., 19 :297–301, 1965. Zbl0127.09002MR178586
  20. D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. In Proc. of the 19 t h Annual Symposium on Theory of Computing, pages 1–6, New York City, may 25–27 1987. Zbl0702.65046
  21. Jean-Pierre Dedieu. Points fixes, zéros et la méthode de Newton. Number 54 in Mathématiques et Applications. SMAI-Springer Verlag. Zbl1095.65047MR2510891
  22. J. Denef and L. Lipshitz. Decision problems for differential equations. The Journ. of Symb. Logic, 54(3) :941–950, 1989. Zbl0683.03039MR1011182
  23. F.J. Drexler. Eine Methode zur Berechnung sämtlicher Lösungen von Polynomgleichungssystemen. Numer. Math., 29(1) :45–58, 1977. Zbl0352.65023MR483386
  24. C. Durvye. Algorithmes pour la décomposition primaire des idéaux polynomiaux de dimension nulle donnés en évaluation. PhD thesis, Univ. de Versailles (France), 2008. 
  25. J. Écalle. L’accélération des fonctions résurgentes (survol). Unpublished manuscript, 1987. 
  26. J. Écalle. Introduction aux fonctions analysables et preuve constructive de la conjecture de Dulac. Hermann, collection : Actualités mathématiques, 1992. MR1399559
  27. J. Écalle. Six lectures on transseries, analysable functions and the constructive proof of Dulac’s conjecture. In D. Schlomiuk, editor, Bifurcations and periodic orbits of vector fields, pages 75–184. Kluwer, 1993. Zbl0814.32008MR1258519
  28. J.-C. Faugère. A new efficient algorithm for computing Gröbner bases (F4). Journal of Pure and Applied Algebra, 139(1–3) :61–88, 1999. Zbl0930.68174MR1700538
  29. J.C. Faugère, P. Gianni, D. Lazard, and T. Mora. Efficient computation of zero-dimensional Gröbner bases by change of ordering. Journal of Symbolic Computation, 16(4) :329–344, 1993. Zbl0805.13007MR1263871
  30. M. Fürer. Faster integer multiplication. In Proceedings of the Thirty-Ninth ACM Symposium on Theory of Computing (STOC 2007), pages 57–66, San Diego, California, 2007. Zbl1179.68198MR2402428
  31. J. von zur Gathen and J. Gerhard. Modern Computer Algebra. Cambridge University Press, 2-nd edition, 2002. Zbl1055.68168MR1689167
  32. A. Giovini, T. Mora, G. Niesi, L. Robbiano, and C. Traverso. “one sugar cube, please” or selection strategies in the buchberger algorithm. In S. Watt, editor, Proc. ISSACâĂŹ91, pages 49–54, New York, 1991. ACM Press. Zbl0933.68161
  33. M. Giusti, K. Hägele, J. Heintz, J.E. Morais, J.L Monta na, and L.M. Pardo. Lower bounds for diophantine approximation. Journal of Pure and Applied Algebra, 117–118 :277–317, 1997. Zbl0871.68101MR1457843
  34. M. Giusti, J. Heintz, J.E. Morais, and L.M. Pardo. When polynomial equation systems can be solved fast ? In G. Cohen, M. Giusti, and T. Mora, editors, Proc. AAECC’11, volume 948 of Lecture Notes in Computer Science. Springer Verlag, 1995. Zbl0902.12005MR1448166
  35. X. Gourdon. Combinatoire, algorithmique et géométrie des polynômes. PhD thesis, École polytechnique, 1996. 
  36. A. Grzegorczyk. Computable functionals. Fund. Math., 42 :168–202, 1955. Zbl0066.26001MR86756
  37. A. Grzegorczyk. On the definition of computable functionals. Fund. Math., 42 :232–239, 1955. Zbl0067.00301MR86755
  38. A. Grzegorczyk. On the definitions of computable real continuous functions. Fund. Math., 44 :61–71, 1957. Zbl0079.24801MR89809
  39. G. Hanrot, V. Lefèvre, K. Ryde, and P. Zimmermann. MPFR, a C library for multiple-precision floating-point computations with exact rounding., 2000. 
  40. L. Jaulin, M. Kieffer, O. Didrit, and E. Walter. Applied interval analysis. Springer, London, 2001. Zbl1023.65037MR1989308
  41. A. Karatsuba and J. Ofman. Multiplication of multidigit numbers on automata. Soviet Physics Doklady, 7 :595–596, 1963. 
  42. R.B. Kearfott. An interval step control for continuation methods. SIAM J. Numer. Anal., 31(3) :892–914, 1994. Zbl0809.65050MR1275119
  43. R. Krawczyk. Newton-algorithmen zur bestimmung von nullstellen mit fehler-schranken. Computing, 4 :187–201, 1969. Zbl0187.10001MR255046
  44. V. Kreinovich, A.V. Lakeyev, J. Rohn, and P.T. Kahl. Computational Complexity and Feasibility of Data Processing and Interval Computations. Springer, 1997. Zbl0945.68077
  45. B. Lambov. Interval arithmetic using sse-2. In Peter Hertling, Christoph Hoffmann, Wolfram Luther, and Nathalie Revol, editors, Reliable Implementation of Real Number Algorithms : Theory and Practice, volume 5045 of Lecture Notes in Computer Science, pages 102–113. Springer Berlin/Heidelberg, 2008. Zbl1165.65339
  46. G. Lecerf. Une alternative aux méthodes de réécriture pour la résolution des syst m ` es algébriques. PhD thesis, École polytechnique, 2001. 
  47. A. Leykin. NAG., 2009. Macaulay 2 package for numerical algebraic geometry. 
  48. Anton Leykin, Jan Verschelde, and Ailing Zhao. Algorithms in algebraic geometry, chapter Higher-order deflation for polynomial systems with isolated singular solutions, pages 79–97. Springer, New York, 2008. Zbl1138.65038MR2397938
  49. K. Makino and M. Berz. Remainder differential algebras and their applications. In M. Berz, C. Bischof, G. Corliss, and A. Griewank, editors, Computational differentiation : techniques, applications and tools, pages 63–74, SIAM, Philadelphia, 1996. Zbl0867.68062MR1431042
  50. K. Makino and M. Berz. Suppression of the wrapping effect by Taylor model-based validated integrators. Technical Report MSU Report MSUHEP 40910, Michigan State University, 2004. Zbl1133.65045
  51. A. Mantzaflaris and B. Mourrain. Deflation and certified isolation of singular zeros of polynomial systems. In A. Leykin, editor, Proc. ISSAC’11, pages 249–256, San Jose, CA, US, Jun 2011. ACM New York. Zbl1323.65054
  52. J. Martinet and J.-P. Ramis. Elementary acceleration and multisummability. Ann. Inst. Henri Poincaré, 54(4) :331–401, 1991. Zbl0748.12005MR1128863
  53. R.E. Moore. Automatic local coordinate transformations to reduce the growth of error bounds in interval computation of solutions to ordinary differential equation. In L.B. Rall, editor, Error in Digital Computation, volume 2, pages 103–140. John Wiley, 1965. Zbl0202.45101MR185839
  54. R.E. Moore. Interval Analysis. Prentice Hall, Englewood Cliffs, N.J., 1966. Zbl0176.13301MR231516
  55. A.P. Morgan. Solving polynomial systems using continuation for] engineering and scientific problems. Prentice-Hall, Englewood Cliffs, N.J., 1987. Zbl0733.65031MR1049872
  56. Jean-Michel Muller. Elementary Functions, Algorithms and Implementation. Birkhauser Boston, Inc., 2006. Zbl1089.65016MR2175068
  57. A. Neumaier. Interval methods for systems of equations. Cambridge university press, Cambridge, 1990. Zbl1152.65054MR1100928
  58. V. Pan. How to multiply matrices faster, volume 179 of Lect. Notes in Math. Springer, 1984. Zbl0548.65022MR765701
  59. V. Y. Pan. Optimal and nearly optimal algorithms for approximating polynomial zeros. Comput. Math. Appl., 31(12) :97–138, 1996. Zbl0859.65045MR1418708
  60. V. Y. Pan. Univariate polynomials : nearly optimal algorithms for numerical factorization and root-finding. J. Symbolic Comput., 33(5) :701–733, 2002. Zbl1004.65061MR1919911
  61. S.M. Rump. Kleine Fehlerschranken bei Matrixproblemen. PhD thesis, Universität Karlsruhe, 1980. Zbl0437.65036
  62. S.M. Rump. Fast and parallel interval arithmetic. BIT, 39(3) :534–554, 1999. Zbl0942.65048MR1708669
  63. S.M. Rump. Verification methods : Rigorous results using floating-point arithmetic. Acta Numerica, 19 :287–449, 2010. Zbl1323.65046MR2652784
  64. L. Schlesinger. Handbuch der Theorie der linearen Differentialgleichungen, volume I. Teubner, Leipzig, 1895. Zbl26.0329.01
  65. L. Schlesinger. Handbuch der Theorie der linearen Differentialgleichungen, volume II. Teubner, Leipzig, 1897. Zbl28.0260.04
  66. A. Schönhage. The fundamental theorem of algebra in terms of computational complexity. Technical report, Math. Inst. Univ. of Tübingen, 1982. 
  67. A. Schönhage and V. Strassen. Schnelle Multiplikation grosser Zahlen. Computing, 7 :281–292, 1971. Zbl0223.68007MR292344
  68. Alexandre Sedoglavic. 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. PhD thesis, École polytechnique, 2001. 
  69. M. Shub and S. Smale. Computational complexity. On the geometry of polynomials and a theory of cost. I. Ann. Sci. École Norm. Sup. (4), 18(1) :107–142, 1985. Zbl0603.65027MR803197
  70. M. Shub and S. Smale. Computational complexity : on the geometry of polynomials and a theory of cost. II. SIAM J. Comput., 15(1) :145–161, 1986. Zbl0625.65036MR822199
  71. S. Smale. The fundamental theorem of algebra and complexity theory. Bull. Amer. Math. Soc. (N.S.), 4(1) :1–36, 1981. Zbl0456.12012MR590817
  72. S. Smale. Newton method estimates from data at one point. In R. E. Ewing, K. I. Gross, and C. F. Martin, editors, In the Merging of Disciplines : New Directions in Pure, Applied, and Computational Mathematics, pages 185–196. Springer-Verlag, 1986. Zbl0613.65058MR870648
  73. A.J. Sommese and C.W. Wampler. The Numerical Solution of Systems of Polynomials Arising in Engineering and Science. World Scientific, 2005. Zbl1091.65049MR2160078
  74. V. Strassen. Gaussian elimination is not optimal. Numer. Math., 13 :352–356, 1969. Zbl0185.40101MR248973
  75. A. Turing. On computable numbers, with an application to the Entscheidungsproblem. Proc. London Maths. Soc., 2(42) :230–265, 1936. Zbl0016.09701
  76. J. van der Hoeven. Lazy multiplication of formal power series. In W. W. Küchlin, editor, Proc. ISSAC ’97, pages 17–20, Maui, Hawaii, July 1997. Zbl0932.68135
  77. J. van der Hoeven. Fast evaluation of holonomic functions. TCS, 210 :199–215, 1999. Zbl0912.68081MR1650888
  78. J. van der Hoeven. Fast evaluation of holonomic functions near and in singularities. JSC, 31 :717–743, 2001. Zbl0982.65024MR1834006
  79. J. van der Hoeven. Relax, but don’t be too lazy. JSC, 34 :479–542, 2002. Zbl1011.68189MR1943041
  80. J. van der Hoeven. Computations with effective real numbers. TCS, 351 :52–60, 2006. Zbl1086.65045MR2201092
  81. J. van der Hoeven. Around the numeric-symbolic computation of differential Galois groups. JSC, 42 :236–264, 2007. Zbl05203522MR2284295
  82. J. van der Hoeven. Efficient accelero-summation of holonomic functions. JSC, 42(4) :389–428, 2007. Zbl1125.34072MR2317557
  83. J. van der Hoeven. New algorithms for relaxed multiplication. JSC, 42(8) :792–802, 2007. Zbl1130.68103MR2345837
  84. J. van der Hoeven. Fast composition of numeric power series. Technical Report 2008-09, Université Paris-Sud, Orsay, France, 2008. 
  85. J. van der Hoeven. Making fast multiplication of polynomials numerically stable. Technical Report 2008-02, Université Paris-Sud, Orsay, France, 2008. 
  86. J. van der Hoeven. Newton’s method and FFT trading. JSC, 45(8) :857–878, 2010. Zbl1192.13017MR2657669
  87. J. van der Hoeven. Efficient root counting for analytic functions on a disk. Technical report, HAL, 2011. 
  88. J. van der Hoeven. Reliable homotopy continuation. Technical report, HAL, 2011. 
  89. J. van der Hoeven, G. Lecerf, B. Mourain, et al. Mathemagix, 2002. 
  90. J. Verschelde. Homotopy continuation methods for solving polynomial systems. PhD thesis, Katholieke Universiteit Leuven, 1996. MR2714998
  91. J. Verschelde. PHCpack : A general-purpose solver for polynomial systems by homotopy continuation. ACM Transactions on Mathematical Software, 25(2) :251–276, 1999. Algorithm 795. Zbl0961.65047
  92. J.W. von Gudenberg. Interval arithmetic on multimedia architectures. Reliable Computing, 8(4), 2002. Zbl0999.65029
  93. K. Weihrauch. Computable analysis. Springer-Verlag, Berlin/Heidelberg, 2000. Zbl0956.68056MR1795407

NotesEmbed ?


You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.


Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.