Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Fast and stable contour integration for high order divided differences via elliptic functions

Authors: M. Lopez-Fernandez and S. Sauter
Journal: Math. Comp. 84 (2015), 1291-1315
MSC (2010): Primary 65D30, 30E20, 33B99, 39A70, 65R20
Published electronically: August 28, 2014
MathSciNet review: 3315509
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper, we will present a new method for evaluating high order divided differences for certain classes of analytic, possibly, operator-valued functions. This is a classical problem in numerical mathematics but also arises in new applications such as the use of generalized convolution quadrature to solve retarded potential integral equations. The functions which we will consider are allowed to grow exponentially to the left complex half-plane, polynomially to the right half-plane and have an oscillatory behaviour with increasing imaginary part. The interpolation points are scattered in a large real interval. Our approach is based on the representation of divided differences as contour integral and we will employ a subtle parameterization of the contour in combination with a quadrature approximation by the trapezoidal rule.

References [Enhancements On Off] (What's this?)

  • [1] Milton Abramowitz and Irene A. Stegun, Handbook of Mathematical Functions, Applied Mathematics Series 55, National Bureau of Standards, U.S. Department of Commerce, 1972.
  • [2] A. Bamberger and T. Ha Duong, Formulation variationnelle espace-temps pour le calcul par potentiel retardé de la diffraction d'une onde acoustique. I, Math. Methods Appl. Sci. 8 (1986), no. 3, 405-435 (French, with English summary). MR 859833 (87m:76048)
  • [3] L. Banjai and S. Sauter, Rapid solution of the wave equation in unbounded domains, SIAM J. Numer. Anal. 47 (2008/09), no. 1, 227-249. MR 2452859 (2009j:65370),
  • [4] L. Banjai and M. Schanz, Wave propagation problems treated with convolution quadrature and BEM, In Fast Boundary Element Methods in Engineering and Industrial Applications, Edited by U. Langer, M. Schanz, O. Steinbach, W.L. Wendland. Vol. 63, Lecture Notes in Applied and Computational Mechanics, Springer, Heidelberg, 2012, pp. 145-187, Chap. 5.
  • [5] Folkmar Bornemann, Accuracy and stability of computing high-order derivatives of analytic functions by Cauchy integrals, Found. Comput. Math. 11 (2011), no. 1, 1-63. MR 2754188 (2012a:65061),
  • [6] M. Caliari, Accurate evaluation of divided differences for polynomial interpolation of exponential propagators, Computing 80 (2007), no. 2, 189-201. MR 2318505 (2008c:65019),
  • [7] Philip J. Davis, On the numerical integration of periodic analytic functions, On Numerical Approximation, Proceedings of a Symposium, Madison, April 21-23, 1958, Edited by R. E. Langer, Publication no. 1 of the Mathematics Research Center, U.S. Army, the University of Wisconsin, The University of Wisconsin Press, Madison, 1959, pp. 45-59. MR 0100354 (20 #6787)
  • [8] Carl de Boor, Divided differences, Surv. Approx. Theory 1 (2005), 46-69 (electronic). MR 2221566 (2006k:41001)
  • [9] T. A. Driscoll, The Schwarz-Christoffel toolbox, available online at http://www.math.
  • [10] Tobin A. Driscoll, Algorithm 843: improvements to the Schwarz-Christoffel toolbox for MATLAB, ACM Trans. Math. Software 31 (2005), no. 2, 239-251. MR 2266791 (2007f:30001),
  • [11] Ömer Eğecioğlu, E. Gallopoulos, and Çetin K. Koç, Fast computation of divided differences and parallel Hermite interpolation, J. Complexity 5 (1989), no. 4, 417-437. MR 1028905 (91g:65018),
  • [12] M. B. Friedman and R. Shaw, Diffraction of pulses by cylindrical obstacles of arbitrary cross section, Trans. ASME Ser. E. J. Appl. Mech. 29 (1962), 40-46. MR 0136238 (24 #B2276)
  • [13] G. Frobenius, Über die Entwicklung analytischer Functionen in Reihen, die nach gegebenen Functionen fortschreiten, J. Reine Angew. Math. 73 (1871), 1-30.
  • [14] I. S. Gradshteyn and I. M. Ryzhik, Table of Integrals, Series, and Products, Fourth edition prepared by Ju. V. Geronimus and M. Ju. Ceĭtlin. Translated from the Russian by Scripta Technica, Inc. Translation edited by Alan Jeffrey, Academic Press, New York, 1965. MR 0197789 (33 #5952)
  • [15] Wolfgang Hackbusch, Wendy Kress, and Stefan A. Sauter, Sparse convolution quadrature for time domain boundary integral formulations of the wave equation by cutoff and panel-clustering, Boundary element analysis, Lect. Notes Appl. Comput. Mech., vol. 29, Springer, Berlin, 2007, pp. 113-134. MR 2298801 (2007m:65086),
  • [16] Nicholas Hale, Nicholas J. Higham, and Lloyd N. Trefethen, Computing $ {\bf A}^\alpha ,\ \log ({\bf A})$, and related matrix functions by contour integrals, SIAM J. Numer. Anal. 46 (2008), no. 5, 2505-2523. MR 2421045 (2009e:65071),
  • [17] Ch. Hermite, Formule d'interpolation de Lagrange, J. Reine Angew. Math. 84 (1878), 70-79.
  • [18] Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996. MR 1368629 (97a:65047)
  • [19] Nicholas J. Higham, The numerical stability of barycentric Lagrange interpolation, IMA J. Numer. Anal. 24 (2004), no. 4, 547-556. MR 2094569 (2005e:65007),
  • [20] Rainer Kreß, Zur numerischen Integration periodischer Funktionen nach der Rechteckregel, Numer. Math. 20 (1972/73), 87-92 (German, with English summary). MR 0317524 (47 #6071)
  • [21] Maria Lopez-Fernandez and Stefan A. Sauter, Generalized convolution quadrature with variable time stepping. part II: algorithms and numerical results, Tech. Report 09-2012, Institut für Mathematik, Univ. Zürich, 2012.
  • [22] -, Generalized convolution quadrature with variable time stepping, IMA J. Numer. Anal. (2013), DOI:10.1093/imanum/drs034.
  • [23] C. Lubich, Convolution quadrature and discretized operational calculus. I, Numer. Math. 52 (1988), no. 2, 129-145. MR 923707 (89g:65018),
  • [24] C. Lubich, Convolution quadrature and discretized operational calculus. II, Numer. Math. 52 (1988), no. 4, 413-425. MR 932708 (89g:65019),
  • [25] A. McCurdy, K. C. Ng, and B. N. Parlett, Accurate computation of divided differences of the exponential function, Math. Comp. 43 (1984), no. 168, 501-528. MR 758198 (86e:65029),
  • [26] Lothar Reichel, Newton interpolation at Leja points, BIT 30 (1990), no. 2, 332-346. MR 1039671 (91e:65020),
  • [27] Klaus Schiefermayr, Inequalities for the Jacobian elliptic functions with complex modulus, J. Math. Inequal. 6 (2012), no. 1, 91-94. MR 2934569,
  • [28] A. Smoktunowicz, I. Wróbel, and P. Kosowski, A new efficient algorithm for polynomial interpolation, Computing 79 (2007), no. 1, 33-52. MR 2282335 (2008a:65020),
  • [29] J. L. Walsh, Interpolation and Approximation by Rational Functions in the Complex Domain, Fourth edition. American Mathematical Society Colloquium Publications, Vol. XX, American Mathematical Society, Providence, R.I., 1965. MR 0218588 (36 #1672b)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65D30, 30E20, 33B99, 39A70, 65R20

Retrieve articles in all journals with MSC (2010): 65D30, 30E20, 33B99, 39A70, 65R20

Additional Information

M. Lopez-Fernandez
Affiliation: Institut für Mathematik, Universität Zürich, Winterthurerstrasse 190, CH-8057 Zürich, Switzerland

S. Sauter
Affiliation: Institut für Mathematik, Universität Zürich, Winterthurerstrasse 190, CH-8057 Zürich, Switzerland

Keywords: Divided differences, numerical approximation of contour integrals, Jacobi elliptic functions, convolution quadrature
Received by editor(s): August 2, 2012
Received by editor(s) in revised form: August 7, 2013
Published electronically: August 28, 2014
Additional Notes: The first author was partially supported by the Spanish grant MTM 2010-19510 and the Swiss grant SNSF 200021_140685
Article copyright: © Copyright 2014 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society