Monotonic interpolating splines

[svillemot]

Thanks for this great package.

It would be nice to add monotonic splines. This is very useful in some situations, e.g. when optimizing over an interpolated function.

See for example splinefun from R for an implementation and some references.

[tomasaschan]

Monotonic splines would be a great addition! However, we can't look at R's implementation, since it's GPL licenced. The references listed are these:

Becker, R. A., Chambers, J. M. and Wilks, A. R. (1988) The New S Language. Wadsworth & Brooks/Cole.

Dougherty, R. L., Edelman, A. and Hyman, J. M. (1989) Positivity-, monotonicity-, or convexity-preserving cubic and quintic Hermite interpolation. Mathematics of Computation 52, 471--494.

Forsythe, G. E., Malcolm, M. A. and Moler, C. B. (1977) Computer Methods for Mathematical Computations. Wiley.

Fritsch, F. N. and Carlson, R. E. (1980) Monotone piecewise cubic interpolation, SIAM Journal on Numerical Analysis 17, 238--246.

Hyman, J. M. (1983) Accurate monotonicity preserving cubic interpolation. SIAM J. Sci. Stat. Comput. 4, 645--654.

I don't have any of those available, but someone else might :) Without having read more than the titles, it seems to me that this paper and this paper might also be good starting points.

My focus at the moment is on wrapping up B-splines (see e.g. #99, and in particular this comment) and I will unfortunately not have much time to spend on this library in a while, so I cannot promise a timeline for when this could be included.

Of course, if you'd like to give it a try yourself, a PR is certainly welcome!

[svillemot]

Thanks for your feedback. Currently I am also quite busy, but I may have a look later.

[nicknack23]

There is a nice Javascript implementation of monotonic cubic splines on Wikipedia, but licensing is not mentioned. The code was added by "Olathe" in 2013, perhaps he is still available and can release it under MIT?

[timholy]

Worth asking. Of course it will also take someone willing to write the Julia version, but just getting it clearly licensed is a nice start.

[niclasmattsson]

Some months ago I needed fast monotone cubic splines for a webapp and decided to look up the original papers that first published the algorithms and write my own implementation based on that. If you're interested I'm willing to release my code under MIT or any license you want. It's in Javascript of course, but you can easily port it to Julia. I have code for two different algorithms:

The Fritsch-Carlson algorithm (1980) is the one described on the Wikipedia page and implemented in the WIP by cc7768.

The Fritsch-Butland algorithm (1984) is faster because it only needs one pass over the data points instead of two. It produces very similar results but in practice looks a tiny bit more more linear than Fritsch-Carlson. Current spline literature appears to regard Fritsch-Butland as the "benchmark", but I am not a specialist.

Let me know if you want my implementation. If so, please tell me how I should release it. As you can tell from my profile I'm a complete Github newbie. I can also share PDFs of these papers if you want to have a look yourself.

[niclasmattsson]

One of the devs of plotly.js suggested I should post my code as a gist, and if I had anything interactive I could just link to it via bl.ocks.org. So I did. Please have a look at my spline playground or the gist, and grab anything you want for Interpolations.jl. To be clear @timholy and others, I coded this from scratch based only on the original papers, so the licensing (MIT) is legit.

[sglyon]

Thank you @niclasmattsson. This is great!

I will try to find time in the next day or two to take a look at this.

[mateuszbaran]

I'm working on monotonic interpolations based on code from @niclasmattsson : https://github.com/mateuszbaran/Interpolations.jl/commits/monotonic-interpolations Any suggestions are welcome.

[tomasaschan]

@mateuszbaran Great! It would be a very welcome addition to the library! :)