New Algorithm to Make Short Work of Challenging Problems
October 1, 2010 — Jon McLoone, International Business & Strategic Development
Buried deep in the list of new technology in the Mathematica development pipeline was the item “integration of oscillatory functions (univariate, multivariate)—new algorithm”. I expect most people will overlook it, as I did, in favor of the new functions, new directions, big infrastructure, and the eye candy. Even worse, most people who will use it won’t even know—it will be selected automatically when needed, like many of Mathematica‘s algorithms. So I think it’s my duty to share my discovery that this algorithm is actually really cool.
Why is it so cool?
The first clue I had was when I read in the notes that this was the first time anyone had fully automated the algorithm into a very wide class of problems. Second, that it was a hybrid numeric-symbolic method (putting it beyond the reach of most numerical systems). And finally, that it was developed by the talented Wolfram Research developer Andrew Moylan.
I decided to look for an example to test it on and remembered the SIAM hundred-dollar, hundred-digit challenge. This was a set of “tricky” numerical problems posed by Nick Trefethen of Oxford University, and prize money was awarded for correct solutions. Ninety-four teams from around the world entered, but only 20 of them managed to solve all the tasks.
The first task could be easily stated in Mathematica notation:
But Mathematica 7, like other systems that do numerical integration, fails on this tricky problem due to the strong oscillations near the origin.
People who solved this challenge had to be much more ingenious and transform the problem through a change of variables into a numerically more stable form, or into a contour integral, and then work on computing with those. It was, after all, meant to be a challenge.
But with this new algorithm, it just works:
A world-class problem that stumped many top minds that you can solve just by typing the question—now that’s cool.