https://github.com/stevengj/cubature
Tip revision: d1955d864f53ecb2b95a802c4b9cceeeccae7b71 authored by Steven G. Johnson on 31 May 2023, 14:27:06 UTC
added citation info
added citation info
Tip revision: d1955d8
clencurt_gen.c
/*
* Copyright (c) 2005-2013 Steven G. Johnson
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*
*/
/* This stand-alone program, which should be compiled and linked against
FFTW (www.fftw.org) version 3 or later, is used to generate the clencurt.h
file for pcubature.c. You only need to run it if you want to do
p-adaptive cubature with more than 8193 points per dimension. See
the README file for more information. */
#include <stdlib.h>
#include <stdio.h>
#include <fftw3.h>
extern long double cosl(long double x);
/* Program to generate tables of precomputed points and weights
for Clenshaw-Curtis quadrature on an interval [-1, 1] with
3, 5, 9, ..., 2^(m+1)+1, ..., 2^(M+1)+1
points up to some given M. Because the quadrature rules are
mirror-symmetric, we only need to store 2^m+1 weights for each rule.
Furthermore, the rules are nested, so we only need to store the
points for the M rule and the points for the other rules are a subset.
We store the points and weights in a permuted order P corresponding to a
usage where we first evaluate m=0, then m=1, etc. until it is converged.
In particular, for the m rule (2^m+1 weights w[j], j=0,1,...,2^m),
the corresponding points are
x[j] = +/- cos(pi * j / 2^(m+1))
(Note that for x[2^m] = 0; this point must be specially handled
so that it is not counted twice.)
So, we precompute an array clencurt_x of length 2^M storing
clencurt_x[j] = cos(pi * P_M(j) / 2^(M+1))
for j = 0,1,...,2^M-1. Then, for a given rule m, we use
x[P_m(j)] = clencurt_x[j]
for j = 0,1,...,2^m-1 and x=0 for j = 2^m. P_m is the permutation
P_0(j) = j
P_m(j) = 2 * P_{m-1}(j) if j < 2^(m-1)
2 * (j - 2^(m-1)) + 1 otherwise
The 2^m+1 weights w are stored for m=0,1,..,M in the same order in an array
clencurt_w of length M+2^(M+1), in order of m. So, the weights for
a given m start at clencurt_w + (m + 2^m - 1), in the same order as
clencurt_x except that it starts with the weight for x=0.
*/
static int P(int m, int j)
{
if (m == 0) return j;
else if (j < (1<<(m-1))) return 2 * P(m-1,j);
else return 2 * (j - (1<<(m-1))) + 1;
}
/***************************************************************************/
/* The general principle is this: in Fejer and Clenshaw-Curtis quadrature,
we take our function f(x) evaluated at f(cos(theta)), discretize
it in theta to a vector f of points, compute the DCT, then multiply
by some coefficients c (the integrals of cos(theta) * sin(theta)).
In matrix form, given the DCT matrix D, this is:
c' * D * f = (D' * c)' * f = w' * f
where w is the vector of weights for each function value. It
is obviously much nicer to precompute w if we are going to be
integrating many functions. Since w = D' * c, and the transpose
D' of a DCT is another DCT (e.g. the transpose of DCT-I is a DCT-I,
modulo some rescaling in FFTW's normalization), to compute w is just
another DCT.
There is an additional wrinkle, because the odd-frequency DCT components
of f integrate to zero, so every other entry in c is zero. We can
take advantage of this in computing w, because we can essentially do
a radix-2 step in the DCT where one of the two subtransforms is zero.
Therefore, for 2n+1 inputs, we only need to do a DCT of size n+1, and
the weights w are a nice symmetric function.
The weights are for integration of functions on (-1,1).
*/
void clencurt_weights(int n, long double *w)
{
fftwl_plan p;
int j;
long double scale = 1.0 / n;
p = fftwl_plan_r2r_1d(n+1, w, w, FFTW_REDFT00, FFTW_ESTIMATE);
for (j = 0; j <= n; ++j) w[j] = scale / (1 - 4*j*j);
fftwl_execute(p);
w[0] *= 0.5;
fftwl_destroy_plan(p);
}
/***************************************************************************/
#define KPI 3.1415926535897932384626433832795028841971L
int main(int argc, char **argv)
{
int M = argc > 1 ? atoi(argv[1]) : 11;
long double *w;
int j, m;
long double k;
if (argc > 2 || M < 0) {
fprintf(stderr, "clencurt_gen usage: clencurt_gen [M]\n");
return EXIT_FAILURE;
}
w = (long double *) fftwl_malloc(sizeof(long double) * ((1<<(M+2)) - 2));
if (!w) {
fprintf(stderr, "clencurt_gen: out of memory\n");
return EXIT_FAILURE;
}
printf("/* AUTOMATICALLY GENERATED -- DO NOT EDIT */\n\n");
printf("static const int clencurt_M = %d;\n\n", M);
printf("static const double clencurt_x[%d] = { /* length 2^M */\n", 1<<M);
k = KPI / ((long double) (1<<(M+1)));
for (j = 0; j < (1<<M); ++j)
printf("%0.18Lg%s\n", cosl(k*P(M,j)), j == (1<<M)-1 ? "" : ",");
printf("};\n\n");
printf("static const double clencurt_w[%d] = { /* length M+2^(M+1) */\n",
M + (1<<(M+1)));
for (m = 0; m <= M; ++m) {
clencurt_weights(1 << m, w);
printf("/* m = %d: */ %0.18Lg,\n", m, w[1 << m]);
for (j = 0; j < (1 << m); ++j)
printf("%0.18Lg%s\n", w[P(m,j)],
j == (1<<m)-1 && m == M ? "" : ",");
}
printf("};\n");
printf("\n/* P_M =");
for (j = 0; j < (1<<M); ++j)
printf(" %d", P(M,j));
printf(" */\n");
return EXIT_SUCCESS;
}