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 >
