Cool, do you have a general idea of when these changes will make it into an official release?
I’m interested in adding code to the C++ library ROOT that interfaces with GSL, so I’d like to know the time frame (weeks, months, next year?) Jean-François On Apr 3, 2014, at 15:01 , Patrick Alken <[email protected]> wrote: > I merged the steffen code into the master branch and updated the NEWS file > > Patrick > > On 04/03/2014 03:53 PM, Jean-François Caron wrote: >> Looks good to me. >> >> Jean-François >> >> On Apr 3, 2014, at 14:51 , Patrick Alken <[email protected]> wrote: >> >>> Ok I used your new text and modified it slightly to say that the method >>> uses piecewise cubic polynomials in each interval: >>> >>> ---- >>> Steffen's method guarantees the monotonicity of the interpolating function >>> between the given data points. Therefore, minima and maxima can only occur >>> exactly at the data points, and there can never be spurious oscillations >>> between data points. The interpolated function is piecewise cubic >>> in each interval. The resulting curve and its first derivative >>> are guaranteed to be continuous, but the second derivative may be >>> discontinuous. >>> ---- >>> >>> Does this look ok? >>> >>> I added your name to test.c >>> >>> Patrick >>> >>> On 04/03/2014 01:58 PM, Jean-François Caron wrote: >>>> Hi Patrick, yes feel free to change the example dataset. I used it >>>> because it’s the same as I put into the test.c code, and other >>>> interpolation methods used randomly-generated data. >>>> >>>> For the description in the docs, I might recommend a different wording: >>>> >>>> @deffn {Interpolation Type} gsl_interp_steffen >>>> Steffen’s method guarantees the monoticity of the interpolating function >>>> between the given data points. Thus minima and maxima can only occur >>>> exactly at the data points, and there can never be spurious oscillations >>>> between data points. >>>> The interpolated function and its first derivative are guaranteed to be >>>> continuous, >>>> but the second derivative may be discontinuous. >>>> @end deffn >>>> >>>> Thanks for supporting my work! I’m very excited to be officially >>>> contributing to an open-source project. Could you check the copyright & >>>> attribution parts of the code files that I modified? I’m not sure what is >>>> correct, but I see author’s names and dates. I added mine to the >>>> steffen.c, but should I add it also to test.c and the others? >>>> >>>> Jean-François >>>> >>>> On Mar 31, 2014, at 15:24 , Patrick Alken <[email protected]> >>>> wrote: >>>> >>>>> I couldn't reproduce the figure in Steffen's paper, so I found another >>>>> dataset which nicely illustrates oscillation issues with Akima: >>>>> >>>>> J. M. Hyman, Accurate Monotonicity preserving cubic interpolation, >>>>> SIAM J. Sci. Stat. Comput. 4, 4, 1983. >>>>> >>>>> The dataset is simpler than your randomly generated plot and I think its >>>>> a little easier to compare the different methods. >>>>> >>>>> I added an example program and a figure to the manual (in the steffen >>>>> branch). >>>>> >>>>> I am hoping to finish everything up and merge into master by the end of >>>>> the week. >>>>> >>>>> Thanks again, >>>>> Patrick >>>>> >>>>> >>>>> On 03/31/2014 02:37 PM, Patrick Alken wrote: >>>>>> Ok I made a new branch 'steffen' in the GSL repository with your latest >>>>>> changes, thanks for all your work on this. I still want to update the >>>>>> docs a little and do some more testing on my own before merging it into >>>>>> master. I made a blurb about gsl_interp_steffen in the docs: >>>>>> >>>>>> ---- >>>>>> @deffn {Interpolation Type} gsl_interp_steffen >>>>>> Steffen's method for monotonic interpolation (not allowing minima or >>>>>> maxima >>>>>> to occur between adjacent data points). The resulting curve is >>>>>> piecewise cubic on each interval with the slope at each grid point >>>>>> chosen to ensure monotonicity and prevent undesired oscillations. The >>>>>> first-order derivative is everywhere continuous. >>>>>> @end deffn >>>>>> ---- >>>>>> >>>>>> Can you read this and make sure I haven't said anything inaccurate? Or >>>>>> let me know any suggestions you think its important to add for the users >>>>>> benefit to understand what this method does. >>>>>> >>>>>> Thanks, >>>>>> Patrick >>>>>> >>>>>> On 03/27/2014 11:17 AM, Jean-François Caron wrote: >>>>>>> By the way, my the second test function in interpolation/test.c uses >>>>>>> randomly-generated data points, but actually serves to nicely >>>>>>> illustrate the difference between major non-linear interpolation >>>>>>> methods. See the linked graph for a comparison of the interpolation >>>>>>> for those data using my implementation of steffen, and the existing GSL >>>>>>> akima and cubic spline methods. >>>>>>> >>>>>>> https://github.com/jfcaron3/gsl-steffen-devel/blob/steffen/interpolation/compare.pdf >>>>>>> (I couldn’t send a pdf to the mailing list, and I don’t know how to >>>>>>> view a pdf on github’s website, but I guess you can just get the image >>>>>>> when you clone the repo.) >>>>>>> >>>>>>> While the cubic spline and akima methods preserve continuity of the >>>>>>> second derivatives, they are not monotonic and can have oscillations >>>>>>> that are often undesireable. The steffen method sacrifices continuity >>>>>>> of the second derivative (but maintains it for the first) in order to >>>>>>> maintain monoticity, which also eliminates weird oscillations. In >>>>>>> Steffen’s paper, there is also an example graph where the akima method >>>>>>> is unstable (a very small change in one data point makes a large change >>>>>>> in the interpolated function), while the steffen method is stable by >>>>>>> construction. >>>>>>> >>>>>>> Jean-François >>>>>>> >>>>>>>> On Mar 27, 2014, at 01:10 , Patrick Alken <[email protected]> >>>>>>>> wrote: >>>>>>>> >>>>>>>>> The code is looking very good - I will try to find time in the next >>>>>>>>> few days to do some tests and import it into GSL >>>>>>>>> >>>>>>>>> Thanks >>>>>>>>> Patrick >>>>>>>>> ________________________________________ >>>>>>>>> From: [email protected] >>>>>>>>> [[email protected]] On Behalf Of Jean-François Caron >>>>>>>>> [[email protected]] >>>>>>>>> Sent: Wednesday, March 26, 2014 7:10 PM >>>>>>>>> To: [email protected] >>>>>>>>> Subject: Re: Compiling & Testing New Interpolation Type >>>>>>>>> >>>>>>>>> I have now fixed the problems with the tests and added a more robust >>>>>>>>> test with lots of data points. I am effectively ready to give a pull >>>>>>>>> request from my github repo. Let me know what I need to do to >>>>>>>>> facilitate this. >>>>>>>>> >>>>>>>>> Jean-François >>>>>>>>> >>>>>>>>> On Mar 25, 2014, at 15:51 , Jean-François Caron <[email protected]> >>>>>>>>> wrote: >>>>>>>>> >>>>>>>>>> Git and Github weren’t as intimidating as I expected. I have a repo >>>>>>>>>> here with the “steffen” branch including my changes: >>>>>>>>>> >>>>>>>>>> https://github.com/jfcaron3/gsl-steffen-devel >>>>>>>>>> >>>>>>>>>> The Savannah git repo didn’t include a configure script, and I got >>>>>>>>>> my modified GSL+Steffen code to compile by directly modifying >>>>>>>>>> interpolation/Makefile AFTER running ./configure, so I’m not sure >>>>>>>>>> how to compile the files cloned from my github repo. At least it’s >>>>>>>>>> easier to see the changes now. >>>>>>>>>> >>>>>>>>>> Jean-François >>>>>>>>>> >>>>>>>>>> On Mar 25, 2014, at 14:56 , Jean-François Caron >>>>>>>>>> <[email protected]> wrote: >>>>>>>>>> >>>>>>>>>>> I’ve improved my initial code greatly. You can find it here: >>>>>>>>>>> >>>>>>>>>>> http://bazaar.launchpad.net/~jfcaron/+junk/my_steffen/files >>>>>>>>>>> >>>>>>>>>>> You can compile it into GSL by adding in the interpolation/Makefile >>>>>>>>>>> references to “steffen.c”, “steffen.lo”, and “steffen.Plo” exactly >>>>>>>>>>> where there are currently references to “akima.*”. >>>>>>>>>>> >>>>>>>>>>> I’ve tried adding an “integ” method, but I’m afraid I don’t even >>>>>>>>>>> understand the workings of the integ methods for the existing >>>>>>>>>>> interpolation types. I couldn’t just copy from the akima.c integ >>>>>>>>>>> method because they use a build-in spline calculation function >>>>>>>>>>> (which I also don’t understand). Reading uncommented C code is >>>>>>>>>>> pretty hard. My test program shows that the integration method >>>>>>>>>>> isn’t obviously broken, but it fails the tests I wrote in >>>>>>>>>>> interpolation/test.c The actual interpolation and derivatives seem >>>>>>>>>>> to work and pass the tests. >>>>>>>>>>> >>>>>>>>>>> I’ve not used github before, so I guess my next move should be to >>>>>>>>>>> learn the basics and start using that, since otherwise describing >>>>>>>>>>> my additions & changes are hard to follow. In the meantime, is >>>>>>>>>>> anyone able to explain how the heck the “integ” methods work? >>>>>>>>>>> >>>>>>>>>>> Jean-François >>>>>>>>>>> >>>>>>>>>>> On Mar 20, 2014, at 11:30 , Patrick Alken >>>>>>>>>>> <[email protected]> wrote: >>>>>>>>>>> >>>>>>>>>>>> Yes that green curve is rather strange and doesn't seem much >>>>>>>>>>>> better than the cubic spline. I like simplicity too so lets >>>>>>>>>>>> proceed with importing the steffen code. >>>>>>>>>>>> >>>>>>>>>>>> On 03/20/2014 12:18 PM, Jean-François Caron wrote: >>>>>>>>>>>>> Definitely an advantage of a) is that it is conceptually simple. >>>>>>>>>>>>> b) is 44 pages while a) is only 7. Even if b) is somehow >>>>>>>>>>>>> mathematically superior, I like the idea of understanding the >>>>>>>>>>>>> tools that I am using (and being able to explain it to my >>>>>>>>>>>>> academic supervisor/conference attendees). >>>>>>>>>>>>> >>>>>>>>>>>>> The MESA astrophysics library (C++ unfortunately) actually >>>>>>>>>>>>> includes both types, and has a little graph to show differences: >>>>>>>>>>>>> http://mesa.sourceforge.net/interp_1D.html >>>>>>>>>>>>> >>>>>>>>>>>>> Actually their graph is confusing, blue is supposed to be a), >>>>>>>>>>>>> green b), but the green curve isn’t piece-wise monotonic between >>>>>>>>>>>>> the data points. I’m starting to think maybe Stetten and Huynh >>>>>>>>>>>>> mean different things when they say “monotonic”. I’ll try to >>>>>>>>>>>>> read Huynh’s paper to see if they define what they are trying to >>>>>>>>>>>>> do. Steffen is pretty clear about his technique being a for an >>>>>>>>>>>>> interpolating function that is monotonic between data points - >>>>>>>>>>>>> i.e. the interpolating function doesn’t change sign between data >>>>>>>>>>>>> points, and extrema can only occur at said data points. >>>>>>>>>>>>> >>>>>>>>>>>>> Jean-François >>>>>>>>>>>>> >>>>>>>>>>>>> On Mar 20, 2014, at 11:03 , Patrick Alken >>>>>>>>>>>>> <[email protected]> wrote: >>>>>>>>>>>>> >>>>>>>>>>>>>> I see question 1) is answered by section 4 of Steffen's paper - >>>>>>>>>>>>>> the method works on all data sets, and preserves monotonicity in >>>>>>>>>>>>>> each interval, which is nice. They also state that method (c) >>>>>>>>>>>>>> has some serious drawbacks. >>>>>>>>>>>>>> >>>>>>>>>>>>>> Unfortunately paper (b) doesn't reference (a) and so its >>>>>>>>>>>>>> difficult to tell whether (b) offers any advantage over (a) >>>>>>>>>>>>>> >>>>>>>>>>>>>> On 03/20/2014 11:52 AM, Patrick Alken wrote: >>>>>>>>>>>>>>> Hi, I'm moving this discussion over to gsl-discuss which is >>>>>>>>>>>>>>> more suited >>>>>>>>>>>>>>> for development issues. >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> I have 2 naive questions which you may be able to answer since >>>>>>>>>>>>>>> you've >>>>>>>>>>>>>>> been working on this code. >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> 1) If the Steffen algorithm is applied to non-monotonic data, >>>>>>>>>>>>>>> will it >>>>>>>>>>>>>>> still provide a solution or does the method encounter an error? >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> 2) Earlier on the GSL list it was mentioned that there are 3 >>>>>>>>>>>>>>> different >>>>>>>>>>>>>>> methods for interpolating monotonic data: >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> (a) M.Steffen, "A simple method for monotonic interpolation in >>>>>>>>>>>>>>> one >>>>>>>>>>>>>>> dimension", Astron. Astrophys. 239, 443-450 (1990). >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> (b) H.T.Huynh, "Accurate Monotone Cubic Interpolation", SIAM J. >>>>>>>>>>>>>>> Numer. >>>>>>>>>>>>>>> Anal. 30, 57-100 (1993). >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> (c) Fritsch, F. N.; Carlson, R. E., "Monotone Piecewise Cubic >>>>>>>>>>>>>>> Interpolation", SIAM J. Numer. Anal. 17 (2), 238–246 (1980). >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> I haven't looked at (c) but it seems that (a) and (b) both use >>>>>>>>>>>>>>> piecewise >>>>>>>>>>>>>>> cubic polynomials and preserve monotonicity. Do you happen to >>>>>>>>>>>>>>> know if >>>>>>>>>>>>>>> one method is superior to the other? If one method is >>>>>>>>>>>>>>> significantly >>>>>>>>>>>>>>> better than the other two it would make more sense to include >>>>>>>>>>>>>>> that one >>>>>>>>>>>>>>> in GSL. >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> Patrick >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> On 03/20/2014 11:37 AM, Jean-François Caron wrote: >>>>>>>>>>>>>>>> Yes, I didn’t bother doing the integration function at the >>>>>>>>>>>>>>>> time because I was having trouble just compiling. I will add >>>>>>>>>>>>>>>> the integration function, and re-write the eval and >>>>>>>>>>>>>>>> deriv/deriv2 functions to use Horner’s scheme for the >>>>>>>>>>>>>>>> polynomials. I can generate some comparison graphs using fake >>>>>>>>>>>>>>>> data like in Steffen’s paper, that sounds easy enough. >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> I’ll look at the interpolation/test.c file and see if I can >>>>>>>>>>>>>>>> come up with similar tests. >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> Thanks for offering to help with the integration into GSL >>>>>>>>>>>>>>>> itself. I don’t know a lot of the procedures (or even >>>>>>>>>>>>>>>> politics sometimes!) involved. >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> Jean-François >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> On Mar 20, 2014, at 10:22 , Patrick Alken >>>>>>>>>>>>>>>> <[email protected]> wrote: >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>> I did notice you talking about 1.6 in your earlier messages, >>>>>>>>>>>>>>>>> but assumed it was a typo and you meant 1.16, oops. >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>> On 03/20/2014 11:11 AM, Jean-François Caron wrote: >>>>>>>>>>>>>>>>>> My original problem was that I wanted to add an >>>>>>>>>>>>>>>>>> interpolation type to GSL. Specifically I want monotonic >>>>>>>>>>>>>>>>>> cubic-splines following the description in Steffen (1990): >>>>>>>>>>>>>>>>>> http://adsabs.harvard.edu/full/1990A%26A...239..443S >>>>>>>>>>>>>>>>> I took a quick look at your code earlier and it looks pretty >>>>>>>>>>>>>>>>> nice. I noticed you commented out the _integ function - is >>>>>>>>>>>>>>>>> this something you could add to make it feature complete with >>>>>>>>>>>>>>>>> the other interpolation types? >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>> It is important to add automated tests for this. Can you look >>>>>>>>>>>>>>>>> at interpolation/test.c and design similar tests for your new >>>>>>>>>>>>>>>>> method? Also I think it would be nice to add a figure to the >>>>>>>>>>>>>>>>> manual illustrating the differences between cubic, akima, and >>>>>>>>>>>>>>>>> your new steffen method (similar to the figures in the >>>>>>>>>>>>>>>>> Steffen paper). This would help users a lot when trying to >>>>>>>>>>>>>>>>> decide what method to use. Do you happen to have a dataset >>>>>>>>>>>>>>>>> which shows a nice contrast like Figs 1, 3 and 8 from that >>>>>>>>>>>>>>>>> paper? >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>> When everything is ready I would be happy to add it to GSL, >>>>>>>>>>>>>>>>> as we are already planning to update the interpolation module >>>>>>>>>>>>>>>>> for the next release. When I find some time I want to import >>>>>>>>>>>>>>>>> the 2D interpolation extension discussed previously, and also >>>>>>>>>>>>>>>>> add Hermite interpolation. >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>> It would be easiest for us if you could clone the GSL git >>>>>>>>>>>>>>>>> repository and make your changes there. You could make a new >>>>>>>>>>>>>>>>> branch called 'steffen' or something and publish it to >>>>>>>>>>>>>>>>> github, or just send a patch file to me, whichever is easiest. >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>> Patrick >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>> On Mar 19, 2014, at 18:40 , Dave Allured - NOAA Affiliate >>>>>>>>>>>>>>>>> <[email protected]> wrote: >>>>>>>>>>>>>>>>>>> More data. I tried the same plain build recipe, GSL 1.16 >>>>>>>>>>>>>>>>>>> on our test >>>>>>>>>>>>>>>>>>> machine which is at Mac OS 10.9.3. Got another perfect >>>>>>>>>>>>>>>>>>> build, no make >>>>>>>>>>>>>>>>>>> check errors, no PPC-related issues. Outputs on request, >>>>>>>>>>>>>>>>>>> please be >>>>>>>>>>>>>>>>>>> specific. >>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>> CC=clang >>>>>>>>>>>>>>>>>>> CFLAGS=-g >>>>>>>>>>>>>>>>>>> ./configure --prefix >>>>>>>>>>>>>>>>>>> /Users/dallured/Disk/3rd/gsl/1.16.os10.9 >>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>> mac27:~/Disk/3rd/gsl/1.16.os10.9 57> sw_vers >>>>>>>>>>>>>>>>>>> ProductName: Mac OS X >>>>>>>>>>>>>>>>>>> ProductVersion: 10.9.3 >>>>>>>>>>>>>>>>>>> BuildVersion: 13D17 >>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>> mac27:~/Disk/3rd/gsl/1.16.os10.9/src 36> \ >>>>>>>>>>>>>>>>>>> ? grep -i '# [a-z]' ../logfiles/make-check.0319a.log | sort >>>>>>>>>>>>>>>>>>> | uniq -c >>>>>>>>>>>>>>>>>>> 45 # ERROR: 0 >>>>>>>>>>>>>>>>>>> 45 # FAIL: 0 >>>>>>>>>>>>>>>>>>> 42 # PASS: 1 >>>>>>>>>>>>>>>>>>> 3 # PASS: 2 >>>>>>>>>>>>>>>>>>> 45 # SKIP: 0 >>>>>>>>>>>>>>>>>>> 42 # TOTAL: 1 >>>>>>>>>>>>>>>>>>> 3 # TOTAL: 2 >>>>>>>>>>>>>>>>>>> 45 # XFAIL: 0 >>>>>>>>>>>>>>>>>>> 45 # XPASS: 0 >>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>> mac27:~/Disk/3rd/gsl/1.16.os10.9 62> \ >>>>>>>>>>>>>>>>>>> ? grep -c -i ppc logfiles/*319a*log >>>>>>>>>>>>>>>>>>> logfiles/configure.0319a.os10.9.log:0 >>>>>>>>>>>>>>>>>>> logfiles/install.0319a.log:0 >>>>>>>>>>>>>>>>>>> logfiles/make-check.0319a.log:0 >>>>>>>>>>>>>>>>>>> logfiles/make.0319a.log:0 >>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>> mac27:~/Disk/3rd/gsl/1.16.os10.9 65> \ >>>>>>>>>>>>>>>>>>> ? grep -i ppc src/config.h src/config.log src/config.status >>>>>>>>>>>>>>>>>>> src/config.h:/* #undef HAVE_GNUPPC_IEEE_INTERFACE */ >>>>>>>>>>>>>>>>>>> src/config.log:HAVE_GNUPPC_IEEE_INTERFACE='' >>>>>>>>>>>>>>>>>>> src/config.status:S["HAVE_GNUPPC_IEEE_INTERFACE"]="" >>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>> --Dave >>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>> On Wed, Mar 19, 2014 at 5:27 PM, Jean-Francois Caron >>>>>>>>>>>>>>>>>>> <[email protected]> >>>>>>>>>>>>>>>>>>> wrote: >>>>>>>>>>>>>>>>>>>> Dave is correct, I am using an "i686" 64-bit x86 mac. For >>>>>>>>>>>>>>>>>>>> some reason >>>>>>>>>>>>>>>>>>>> it is still looking for the PPC mac header file. The >>>>>>>>>>>>>>>>>>>> ./configure >>>>>>>>>>>>>>>>>>>> stage correctly identifies my system, so it's a bit >>>>>>>>>>>>>>>>>>>> strange. Also GSL >>>>>>>>>>>>>>>>>>>> installs without errors when I do it from MacPorts, and >>>>>>>>>>>>>>>>>>>> MacPorts >>>>>>>>>>>>>>>>>>>> doesn't seem to do anything other than ./configure && >>>>>>>>>>>>>>>>>>>> make, from my >>>>>>>>>>>>>>>>>>>> reading of the portfile. >>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>> When I get back to my Mac, I will look at the NOTES file >>>>>>>>>>>>>>>>>>>> to see if >>>>>>>>>>>>>>>>>>>> anything needs to be done for 10.9. >>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>> Jean-François >
