This looks pretty good from a quick skim (it's 2007 so I probably saw it 10+ years ago, but don't remember). I did my PhD on radial basis functions, and they seem surprisingly unknown for something so useful. RBFs provide a really easy way to interpolate through scattered data of any number of dimensions. I interpolated through point data, integral data, and derivative data (but didn't use them to solve DEs like this).
That fits a multiquadric RBF (p2) (with linear terms, because it's conditionally positive definite; p5-6) to some carefully chosen data, then evaluates it (at the same points again, because I was in a hurry...) and converts to characters.
Fitting an RBF naively involves inverting a matrix as big as the number of points, but the FMM techniques use approximation to make the task practical.
Yes, I'm familiar with that paper. It's very complicated to implement - back when I was researching I didn't encounter any papers by others who had replicated it, and citations often mentioned its complexity. There are simpler ways to scale RBFs. I did it piecewise, using overlapping subdomains (each with ~200 points, so a small linear system) blended with partition of unity, and it scaled to millions of points in an embarrassingly parallelisable way. Here's a result I've linked on HN before, filling a hole in a point cloud (a small one, ~24000 points): https://imgur.com/a/k6AQi
Those course notes have some interesting stuff in them, thanks!
4 comments
[ 1.2 ms ] story [ 23.8 ms ] threadThey also made a good well-obfuscated "peak hello world" attempt: https://news.ycombinator.com/item?id=23211972
That fits a multiquadric RBF (p2) (with linear terms, because it's conditionally positive definite; p5-6) to some carefully chosen data, then evaluates it (at the same points again, because I was in a hurry...) and converts to characters.
Fitting an RBF naively involves inverting a matrix as big as the number of points, but the FMM techniques use approximation to make the task practical.
JP Lewis has some course notes which explain the basics of RBF techniques well: http://scribblethink.org/Courses/ScatteredInterpolation/scat...
For a slightly more technical account, try Sage Shaw's excellent contribution to this Wikipedia page: https://en.wikipedia.org/wiki/Radial_basis_function_interpol...
Those course notes have some interesting stuff in them, thanks!