Research and Advances

More on algorithms that reveal properties of floating point arithmetic units

In the interests of producing portable mathematical software, it is highly desirable for a program to be able directly to obtain fundamental properties of the environment in which it is to run. The installer would then not be obliged to change appropriate magic constants in the source code, and the user would not have to provide information he may very well not understand. Until the standard definitions of programming languages are changed to require builtin functions that provide this information [1, 3], we will have to resort to writing routines that discover it.


Author Archives

Research and Advances

Implementing Clenshaw-Curtis quadrature, I methodology and experience

Clenshaw-Curtis quadrature is a particularly important automatic quadrature scheme for a variety of reasons, especially the high accuracy obtained from relatively few integrand values. However, it has received little use because it requires the computation of a cosine transformation, and the arithmetic cost of this has been prohibitive. This paper is in two parts; a companion paper, “II Computing the Cosine Transformation,” shows that this objection can be overcome by computing the cosine transformation by a modification of the fast Fourier transform algorithm. This first part discusses the strategy and various error estimates, and summarizes experience with a particular implementation of the scheme.
Research and Advances

Algorithm 424: Clenshaw-Curtis quadrature [D1]

Clenshaw-Curtis quadrature is one of the most effective automatic quadrature schemes available, particularly for integrands with some continuous derivatives. It can also be used for any piecewise continuous integrand, although it is not recommended for integrands with discontinuities.
Research and Advances

Implementing Clenshaw-Curtis quadrature, II computing the cosine transformation

In a companion paper to this, “I Methodology and Experiences,” the automatic Clenshaw-Curtis quadrature scheme was described and how each quadrature formula used in the scheme requires a cosine transformation of the integrand values was shown. The high cost of these cosine transformations has been a serious drawback in using Clenshaw-Curtis quadrature. Two other problems related to the cosine transformation have also been troublesome. First, the conventional computation of the cosine transformation by recurrence relation is numerically unstable, particularly at the low frequencies which have the largest effect upon the integral. Second, in case the automatic scheme should require refinement of the sampling, storage is required to save the integrand values after the cosine transformation is computed. This second part of the paper shows how the cosine transformation can be computed by a modification of the fast Fourier transform and all three problems overcome. The modification is also applicable in other circumstances requiring cosine or sine transformations, such as polynomial interpolation through the Chebyshev points.

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved