Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Numerical Algorithms
Published in: Numerical Algorithms 4/2020

29-05-2019 | Original Paper

Symbolic-numeric integration of rational functions

Authors: Robert H. C. Moir, Robert M. Corless, Marc Moreno Maza, Ning Xie

Published in: Numerical Algorithms | Issue 4/2020

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We consider the problem of symbolic-numeric integration of symbolic functions, focusing on rational functions. Using a hybrid method allows the reliable yet efficient computation of symbolic antiderivatives while avoiding issues of ill-conditioning to which numerical methods are susceptible. We propose two alternative methods for exact input that compute the rational part of the integral using Hermite reduction and then compute the transcendental part two different ways using a combination of exact integration and efficient numerical computation of roots. The symbolic computation is done within bpas, or Basic Polynomial Algebra Subprograms, which is a highly optimized environment for polynomial computation on parallel architectures, while the numerical computation is done using the highly optimized multiprecision rootfinding package MPSolve. We provide for both algorithms computable expressions for the first-order term of a structured forward and backward error and show how, away from singularities, tolerance proportionality is achieved by adjusting the precision of the rootfinding tasks.
previous article A derivative-free conjugate residual method using secant condition for general large-scale nonlinear equations
next article Iterative method with inertial terms for nonexpansive mappings: applications to compressed sensing

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now
Footnotes
1
Note that strict preservation of the form of the integrand is not quite achieved for the PFD method described below, since the derivative cannot be simplified into this form without using approximate gcd. Thus, with exact computation, the degree of the numerator and denominator of the nearby integrand is larger in general than the exact integrand.
 
2
The following review is based in part on the ISSAC 1998 tutorial [3] and the landmark text book [2] of M. Bronstein.
 
3
Note that throughout this section we assume that the error for the numerical rootfinding for a polynomial P(x) satisfies the relation |Δr|≤ ε|r|, where r is the value of the computed root and Δr is the distance in the complex plane to the exact root. This can be accomplished using MPSolve by specifying an error tolerance of ε. Given the way that MPSolve isolates and then approximates roots, the bound is generally satisfied by several orders of magnitude.
 
4
Note that we assume that ε is sufficiently small to avoid spurious identification of residues in this analysis. Even with spurious identification, however, the backward error analysis would only change slightly, viz., to use the maximum error among the nearby residues, rather than the error of the selected representative residue. A different but related issue occurs when several distinct residues are clustered within an interval of width of some small multiple of ε. This presents a more challenging situation that we reserve for future work, but discuss briefly in Section 7 below.
 
5
This means that when several computed residues are coalesced, the chosen representative root \(\hat {\gamma }_{\tilde {k}}\) must be used to evaluate \(\hat {a}_{k}\) and \(\hat {b}_{k}\), and \(c^{\prime }(\hat {\gamma }_{k})\) must be used to evaluate all of the error terms corresponding to the roots \(\hat {\gamma }_{k}\) that have the same residue.
 
6
Note that this may account for the differences in stability between the LRT-based and PFD-based methods observed in Section 6 below. Because roots are isolated using multiprecision arithmetic, however, both methods nonetheless produce stable results.
 
7
The data for this section was collected using an internal December 2017 version of the BPAS library.
 
Literature
1.
Bini, D.A., Robol, L.: Solving secular and polynomial equations: a multiprecision algorithm. J. Comput. Appl. Math. 272, 276–292 (2014)MathSciNetCrossRef
2.
3.
4.
Buchberger, B., Rüdiger, G.K.L.: Algebraic Simplification, pp 11–43. Springer, Wien–New York (1982)
5.
6.
Kahan, W.M.: Conserving confluence curbs ill-condition. Technical report, DTIC Document (1972)
7.
Kahan, W.M.: Handheld calculator evaluates integrals. Hewlett-Packard Journal 31(8), 23–32 (1980)MathSciNet
8.
Noda, M.-T., Miyahiro, E.: On the symbolic/numeric hybrid integration. In: Proceedings of the International Symposium on Symbolic and Algebraic Computation, p 304. ACM (1990)
9.
Noda, M.-T., Miyahiro, E.: A hybrid approach for the integration of a rational function. J. Comput. Appl. Math. 40(3), 259–268 (1992)MathSciNetCrossRef
10.
Rioboo, R.: Proceedings of the 1992 International Symposium on Symbolic and Algebraic Computation, ISSAC ’92, Berkeley, CA, USA, July 27–29, 1992. In: Wang, P.S. (ed.) , pp 206–215. ACM (1992)
11.
12.
Zeng, Z.: Apatools: a software toolbox for approximate polynomial algebra. In: Software for Algebraic Geometry, pp 149–167. Springer (2008)
Metadata
Title
Symbolic-numeric integration of rational functions
Authors
Robert H. C. Moir
Robert M. Corless
Marc Moreno Maza
Ning Xie
Publication date
29-05-2019
Publisher
Springer US
Published in
Numerical Algorithms / Issue 4/2020
Print ISSN: 1017-1398
Electronic ISSN: 1572-9265
DOI
https://doi.org/10.1007/s11075-019-00726-6

Other articles of this Issue 4/2020

Numerical Algorithms 4/2020 Go to the issue

Original Paper

A coercive heterogeneous media Helmholtz model: formulation, wavenumber-explicit analysis, and preconditioned high-order FEM

Original Paper

A derivative-free conjugate residual method using secant condition for general large-scale nonlinear equations

Original Paper

Efficient high-order compact exponential time differencing method for space-fractional reaction-diffusion systems with nonhomogeneous boundary conditions

Original Paper

Stationary distribution of the stochastic theta method for nonlinear stochastic differential equations

Original Paper

Computing the roots of sparse high–degree polynomials that arise from the study of random simplicial complexes

Original Paper

Strong convergence of an extragradient-like algorithm involving pseudo-monotone mappings

Premium Partner

    Image Credits