Brief
Quadrature means estimating an integral as a weighted sum of function values at chosen points (nodes). Implement these methods. Composite trapezoid/Simpson. Romberg (refine the trapezoid rule repeatedly and extrapolate). Gauss-Legendre, with nodes and weights from Golub-Welsch: they come from the eigenpairs of the Jacobi matrix (a small symmetric tridiagonal matrix), computed with your own symmetric tridiagonal eigensolver. Clenshaw-Curtis (nodes at cosine-spaced points, weights computed with an FFT) via your B11 FFT. Adaptive Gauss-Kronrod (keeps splitting the interval wherever the error estimate is large). Score every method on the six Genz integrand families (standard test integrands that are oscillatory, peaked, discontinuous and so on).
VICTORY CONDITIONS
- Match or beat quad's evaluation count on >= 4/6 Genz families. Golub-Welsch nodes agree with numpy.polynomial.legendre.leggauss to 1e-14 for n <= 100. Reproduce Trefethen's Gauss ~ Clenshaw-Curtis observation (the two are about equally accurate in practice). (Function evaluations needed to reach 1e-10 relative error, per Genz family).
- A public repository with a README that shows your result and how to reproduce it.
Terms in plain words
- Quadrature
- Approximating an integral by a weighted sum of the function's values at a set of points.
- Golub-Welsch algorithm
- Computing Gauss quadrature nodes and weights as the eigenvalues and eigenvector entries of a tridiagonal Jacobi matrix.
- Gauss-Kronrod
- A pair of nested quadrature rules whose difference gives an error estimate, used to decide where to subdivide.
- Clenshaw-Curtis
- A quadrature rule using cosine-spaced points whose weights can be computed quickly with an FFT.
- Genz families
- Six standard families of test integrands, each designed to stress a different weakness of integration methods.
Why it rates ★★☆☆☆
Elegant numerics that link eigenvalues to integration. But quadrature is rarely the bottleneck in ML.