Calcul analytique

Hoeven, Joris van der

Journées Nationales de Calcul Formel. 14 – 18 Novembre 2011, Les cours du CIRM, no. 1 (2011), Exposé no. 4, 85 p.

[1] O. Aberth. Computable analysis. McGraw-Hill, New York, 1980.

[2] G. Alefeld and J. Herzberger. Introduction to interval analysis. Academic Press, New York, 1983.

[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. http://www.nd.edu/~sommese/bertini/, 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.

[6] D. Bini and V.Y. Pan. Polynomial and matrix computations. Vol. 1. Birkhäuser Boston Inc., Boston, MA, 1994. Fundamental algorithms.

[7] D. A. Bini and G. Fiorentino. Design, analysis, and implementation of a multiprecision polynomial rootfinder. Numerical Algorithms, 23 :127–173, 2000.

[8] E. Bishop and D. Bridges. Foundations of constructive analysis. Die Grundlehren der mathematische Wissenschaften. Springer, Berlin, 1985.

[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.

[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.

[11] A. Bostan, G. Lecerf, and É. Schost. Tellegen’s principle into practice. In Proceedings of ISSAC 2003, pages 37–44. ACM, 2003.

[12] B.L.J. Braaksma. Multisummability and Stokes multipliers of linear meromorphic differential equations. J. Diff. Eq, 92 :45–75, 1991.

[13] R.P. Brent and H.T. Kung. $O\left({(nlogn)}^{3/2}\right)$ 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.

[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.

[15] R.P. Brent and H.T. Kung. Fast algorithms for manipulating formal power series. Journal of the ACM, 25 :581–595, 1978.

[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.

[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.

[19] J.W. Cooley and J.W. Tukey. An algorithm for the machine calculation of complex Fourier series. Math. Computat., 19 :297–301, 1965.

[20] D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. In Proc. of the ${19}^{th}$ Annual Symposium on Theory of Computing, pages 1–6, New York City, may 25–27 1987.

[21] Jean-Pierre Dedieu. Points fixes, zéros et la méthode de Newton. Number 54 in Mathématiques et Applications. SMAI-Springer Verlag.

[22] J. Denef and L. Lipshitz. Decision problems for differential equations. The Journ. of Symb. Logic, 54(3) :941–950, 1989.

[23] F.J. Drexler. Eine Methode zur Berechnung sämtlicher Lösungen von Polynomgleichungssystemen. Numer. Math., 29(1) :45–58, 1977.

[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.

[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.

[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.

[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.

[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.

[31] J. von zur Gathen and J. Gerhard. Modern Computer Algebra. Cambridge University Press, 2-nd edition, 2002.

[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.

[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.

[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.

[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.

[37] A. Grzegorczyk. On the definition of computable functionals. Fund. Math., 42 :232–239, 1955.

[38] A. Grzegorczyk. On the definitions of computable real continuous functions. Fund. Math., 44 :61–71, 1957.

[39] G. Hanrot, V. Lefèvre, K. Ryde, and P. Zimmermann. MPFR, a C library for multiple-precision floating-point computations with exact rounding. http://www.mpfr.org, 2000.

[40] L. Jaulin, M. Kieffer, O. Didrit, and E. Walter. Applied interval analysis. Springer, London, 2001.

[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.

[43] R. Krawczyk. Newton-algorithmen zur bestimmung von nullstellen mit fehler-schranken. Computing, 4 :187–201, 1969.

[44] V. Kreinovich, A.V. Lakeyev, J. Rohn, and P.T. Kahl. Computational Complexity and Feasibility of Data Processing and Interval Computations. Springer, 1997.

[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.

[46] G. Lecerf. Une alternative aux méthodes de réécriture pour la résolution des syst$\stackrel{`}{\text{m}}$es algébriques. PhD thesis, École polytechnique, 2001.

[47] A. Leykin. NAG. http://www.math.uic.edu/~leykin/NAG4M2, 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.

[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.

[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.

[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.

[52] J. Martinet and J.-P. Ramis. Elementary acceleration and multisummability. Ann. Inst. Henri Poincaré, 54(4) :331–401, 1991.

[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.

[54] R.E. Moore. Interval Analysis. Prentice Hall, Englewood Cliffs, N.J., 1966.

[55] A.P. Morgan. Solving polynomial systems using continuation for] engineering and scientific problems. Prentice-Hall, Englewood Cliffs, N.J., 1987.

[56] Jean-Michel Muller. Elementary Functions, Algorithms and Implementation. Birkhauser Boston, Inc., 2006.

[57] A. Neumaier. Interval methods for systems of equations. Cambridge university press, Cambridge, 1990.

[58] V. Pan. How to multiply matrices faster, volume 179 of Lect. Notes in Math. Springer, 1984.

[59] V. Y. Pan. Optimal and nearly optimal algorithms for approximating polynomial zeros. Comput. Math. Appl., 31(12) :97–138, 1996.

[60] V. Y. Pan. Univariate polynomials : nearly optimal algorithms for numerical factorization and root-finding. J. Symbolic Comput., 33(5) :701–733, 2002.

[61] S.M. Rump. Kleine Fehlerschranken bei Matrixproblemen. PhD thesis, Universität Karlsruhe, 1980.

[62] S.M. Rump. Fast and parallel interval arithmetic. BIT, 39(3) :534–554, 1999.

[63] S.M. Rump. Verification methods : Rigorous results using floating-point arithmetic. Acta Numerica, 19 :287–449, 2010.

[64] L. Schlesinger. Handbuch der Theorie der linearen Differentialgleichungen, volume I. Teubner, Leipzig, 1895.

[65] L. Schlesinger. Handbuch der Theorie der linearen Differentialgleichungen, volume II. Teubner, Leipzig, 1897.

[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.

[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.

[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.

[71] S. Smale. The fundamental theorem of algebra and complexity theory. Bull. Amer. Math. Soc. (N.S.), 4(1) :1–36, 1981.

[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.

[73] A.J. Sommese and C.W. Wampler. The Numerical Solution of Systems of Polynomials Arising in Engineering and Science. World Scientific, 2005.

[74] V. Strassen. Gaussian elimination is not optimal. Numer. Math., 13 :352–356, 1969.

[75] A. Turing. On computable numbers, with an application to the Entscheidungsproblem. Proc. London Maths. Soc., 2(42) :230–265, 1936.

[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.

[77] J. van der Hoeven. Fast evaluation of holonomic functions. TCS, 210 :199–215, 1999.

[78] J. van der Hoeven. Fast evaluation of holonomic functions near and in singularities. JSC, 31 :717–743, 2001.

[79] J. van der Hoeven. Relax, but don’t be too lazy. JSC, 34 :479–542, 2002.

[80] J. van der Hoeven. Computations with effective real numbers. TCS, 351 :52–60, 2006.

[81] J. van der Hoeven. Around the numeric-symbolic computation of differential Galois groups. JSC, 42 :236–264, 2007.

[82] J. van der Hoeven. Efficient accelero-summation of holonomic functions. JSC, 42(4) :389–428, 2007.

[83] J. van der Hoeven. New algorithms for relaxed multiplication. JSC, 42(8) :792–802, 2007.

[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.

[87] J. van der Hoeven. Efficient root counting for analytic functions on a disk. Technical report, HAL, 2011. | HAL

[88] J. van der Hoeven. Reliable homotopy continuation. Technical report, HAL, 2011. | HAL

[89] J. van der Hoeven, G. Lecerf, B. Mourain, et al. Mathemagix, 2002. http://www.mathemagix.org.

[90] J. Verschelde. Homotopy continuation methods for solving polynomial systems. PhD thesis, Katholieke Universiteit Leuven, 1996.

[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.

[92] J.W. von Gudenberg. Interval arithmetic on multimedia architectures. Reliable Computing, 8(4), 2002.

[93] K. Weihrauch. Computable analysis. Springer-Verlag, Berlin/Heidelberg, 2000.