CLENSHAW_CURTIS
Multidimensional Clenshaw Curtis Quadrature

CLENSHAW_CURTIS is a FORTRAN90 program, using double precision arithmetic, which can set up a Clenshaw Curtis quadrature rule in one or multiple dimensions.

Routines are available to look up or compute the weights and abscissas of the 1D rule.

The code includes a routine to set the abscissas of a multiple dimension product rule.

It is easy to generate a Clenshaw Curtis grid of any order N. Of special interest are nested grids, particularly those for which the nesting involves repeated divisions of the interval length by 2. In such a case, the data computed from the previous step can be reused, and the new data allows for an inexpensive estimate of the rate of error decrease. In the 1D case, we can keep track of such a nested sequence of rules by the "level", which, except for the zeroth level, has a simple relationship to the order N:

LEVEL	N	H
0	1	2
1	3=2+1	1
2	5=4+1	1/2
3	9=8+1	1/4
4	17=16+1	1/8
5	33=32+1	1/16

The code includes routines which pack into a single array all the abscissas associated with several Clenshaw Curtis grids of abscissas, with the grids selected in one of two ways.

Two selection rules are available.

For the first "MINMAX" selection rule, we define the quantity Q to be the sum of the 1D orders:

        Q = sum ( 1 <= I <= DIM_NUM ) ORDER(I)
      

        Q_MIN <= Q <= Q_MAX.
      

For the second "CONSTRAINED" selection rule, we define the quantity Q to be the weighted sum of the 1D orders:

        Q = sum ( 1 <= I <= DIM_NUM ) ALPHA(I) * ORDER(I)
      

        ORDER_MIN(I) <= ORDER(I) <= ORDER_MAX(I).
      

        Q <= Q_MAX.
      

Related Data and Programs:

CC_DISPLAY is a MATLAB program which can display various 2D Clenshaw Curtis grids.

CLENSHAW_CURTIS is also available in a C++ version and a MATLAB version.

FEKETE is a FORTRAN90 library which defines a Fekete rule for quadrature or interpolation over a triangle.

INTLIB is a FORTRAN90 library which contains routines for numerical estimation of integrals in 1D.

NESTED_SEQUENCE_DISPLAY is a MATLAB program which can display a set of nested 1D sequences.

NINT_EXACTNESS is a FORTRAN90 program which demonstrates how to measure the polynomial exactness of a multidimensional quadrature rule.

NINTLIB is a FORTRAN90 library which contains a variety of routines for numerical estimation of integrals in multiple dimensions.

PRODUCT_FACTOR is a FORTRAN90 program which constructs a product rule from distinct 1D factor rules.

PRODUCT_RULE is a FORTRAN90 program which constructs a product rule from identical 1D factor rules.

QUADPACK is a FORTRAN90 library which contains a variety of routines for numerical estimation of integrals in 1D.

QUADRATURE_RULES is a dataset directory which contains sets of files that define quadrature rules over various 1D intervals or multidimensional hypercubes.

QUADRULE is a FORTRAN90 library which contains quadrature rules.

SPARSE_GRID_CLOSED is a FORTRAN90 library which generates points on sparse grids associated with closed quadrature rules, including the Clenshaw-Curtis rule.

SPARSE_GRID_DISPLAY is a MATLAB library which can display a sparse grid in 2D or 3D.

STROUD is a FORTRAN90 library which contains quadrature rules for a variety of unusual areas, surfaces and volumes in 2D, 3D and N-dimensions.

TEST_INT is a FORTRAN90 library which contains functions that may be used as test integrands for quadrature rules in 1D.

TEST_NINT is a FORTRAN90 library which containsn functions that may be used as test integrands for quadrature rules in multiple dimensions.

TOMS351 is a FORTRAN77 library which estimates an integral using Romberg integration.

TOMS379 is a FORTRAN77 library which estimates an integral.

TOMS418 is a FORTRAN77 library which estimates the integral of a function with a sine or cosine factor.

TOMS424 is a FORTRAN77 library which estimates the integral of a function using Clenshaw-Curtis quadrature.

TOMS468 is a FORTRAN77 library which "automatically" integrates a function.

Reference:

1. Philip Davis, Philip Rabinowitz,
   Methods of Numerical Integration,
   Second Edition,
   Dover, 2007,
   ISBN: 0486453391,
   LC: QA299.3.D28.
2. Charles Clenshaw, Alan Curtis,
   A Method for Numerical Integration on an Automatic Computer,
   Numerische Mathematik,
   Volume 2, Number 1, December 1960, pages 197-205.
3. W Morven Gentleman,
   Algorithm 424: Clenshaw-Curtis Quadrature,
   Communications of the ACM,
   Volume 15, Number 5, May 1972, pages 353-355.
4. Lloyd Trefethen,
   Is Gauss Quadrature Better than Clenshaw-Curtis?,
   SIAM Review,
   Volume 50, Number 1, 2008, pages 67-87.
5. Joerg Waldvogel,
   Fast Construction of the Fejer and Clenshaw-Curtis Quadrature Rules,
   BIT Numerical Mathematics,
   Volume 43, Number 1, 2003, pages 1-18.

Source Code:

• clenshaw_curtis.f90, the source code.
• clenshaw_curtis.csh, commands to compile the source code.

Examples and Tests:

• clenshaw_curtis_prb.f90, a sample calling program.
• clenshaw_curtis_prb.csh, commands to compile and run the sample program.
• clenshaw_curtis_prb_output.txt, the output file.

CC_1D is an image of the abscissas of a nested sequence of Clenshaw Curtis rules.

• cc_1d.png, a PNG image of the abscissas of the order 1, 3, 5, 9, 17, 33 and 65 order rules, created by NESTED_SEQUENCE_DISPLAY.

CC_D1_O9 is a Clenshaw Curtis rule for 1D, using an order 9 rule.

• cc_d1_o9_r.txt, range for dimension 1, and order 9.
• cc_d1_o9_w.txt, weights for dimension 1, and order 9.
• cc_d1_o9_x.txt, abscissas for dimension 1, and order 9.

CC_D4_O3X3X3X3 is a Clenshaw Curtis rule for 4D, using a product of order 3 rules.

• cc_d4_o3x3x3x3_r.txt, range for dimension 4, and (total) order 81.
• cc_d4_o3x3x3x3_w.txt, weights for dimension 4, and (total) order 81.
• cc_d4_o3x3x3x3_x.txt, abscissas for dimension 4, and (total) order 81.

List of Routines:

• CC_ABSCISSA returns the I-th Clenshaw Curtis abscissa.
• CC_ABSCISSA_LEVEL_1D: first level at which given abscissa is generated.
• CC_GRID returns a multidimensional Clenshaw-Curtis grid.
• CC_GRIDS_CONSTRAINED computes CC orders and grids satisfying a constraint.
• CC_GRIDS_CONSTRAINED_SIZE counts grids for CC_GRIDS_CONSTRAINED.
• CC_GRIDS_MINMAX computes CC orders and grids with Q_MIN <= Q <= Q_MAX.
• CC_GRIDS_MINMAX_SIZE counts grids for CC_GRIDS_MINMAX.
• CC_LEVEL_TO_ORDER converts a CC nesting level to a CC order.
• CC_LEVELS_CONSTRAINED: CC grids with constrained levels.
• CC_LEVELS_CONSTRAINED_SIZE counts grids for CC_LEVELS_CONSTRAINED.
• CC_LEVELS_MINMAX computes CC grids with LEVEL_MIN <= LEVEL <= LEVEL_MAX.
• CC_LEVELS_MINMAX_SIZE counts grids for CC_LEVELS_MINMAX.
• CC_WEIGHT returns the I-th Clenshaw Curtis weight.
• CLENSHAW_CURTIS_COMPUTE computes a Clenshaw Curtis quadrature rule.
• CLENSHAW_CURTIS_COMPUTE_ND returns a multidimensional Clenshaw-Curtis rule.
• CLENSHAW_CURTIS_SET sets a Clenshaw-Curtis quadrature rule.
• COMP_NEXT computes the compositions of the integer N into K parts.
• COMPNZ_NEXT computes the compositions of the integer N into K nonzero parts.
• DTABLE_CLOSE_WRITE closes a file used to write a DTABLE.
• DTABLE_DATA_WRITE writes DTABLE data to a file.
• DTABLE_HEADER_WRITE writes the header to a DTABLE file.
• DTABLE_OPEN_WRITE opens a file to write a DTABLE.
• DTABLE_WRITE writes a DTABLE to a file.
• GET_UNIT returns a free FORTRAN unit number.
• I4_MODP returns the nonnegative remainder of I4 division.
• I4VEC_UNIFORM returns a scaled pseudorandom I4VEC.
• S_BLANK_DELETE removes blanks from a string, left justifying the remainder.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• TIMESTRING writes the current YMDHMS date into a string.
• VEC_NEXT_GRAY computes the elements of a product space.
• VECTOR_CONSTRAINED_NEXT4 returns the "next" constrained vector.

You can go up one level to the FORTRAN90 source codes.