public inbox for gsl-discuss@sourceware.org
 help / color / mirror / Atom feed
* Re: Compiling & Testing New Interpolation Type
       [not found]                         ` <AE615778-0196-446E-84C9-C2DB09934F01@phas.ubc.ca>
@ 2014-03-20 17:52                           ` Patrick Alken
  2014-03-20 18:04                             ` Patrick Alken
  0 siblings, 1 reply; 17+ messages in thread
From: Patrick Alken @ 2014-03-20 17:52 UTC (permalink / raw)
  To: Jean-François Caron; +Cc: gsl-discuss

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 <patrick.alken@Colorado.EDU> 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 <dave.allured@noaa.gov> 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 <jfcaron@phas.ubc.ca>
>>>> 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
>>

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: Compiling & Testing New Interpolation Type
  2014-03-20 17:52                           ` Compiling & Testing New Interpolation Type Patrick Alken
@ 2014-03-20 18:04                             ` Patrick Alken
  2014-03-20 18:18                               ` Jean-François Caron
  0 siblings, 1 reply; 17+ messages in thread
From: Patrick Alken @ 2014-03-20 18:04 UTC (permalink / raw)
  To: gsl-discuss, jfcaron

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 <patrick.alken@Colorado.EDU> 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 <dave.allured@noaa.gov> 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 <jfcaron@phas.ubc.ca>
>>>>> 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

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: Compiling & Testing New Interpolation Type
  2014-03-20 18:04                             ` Patrick Alken
@ 2014-03-20 18:18                               ` Jean-François Caron
  2014-03-20 18:30                                 ` Patrick Alken
  0 siblings, 1 reply; 17+ messages in thread
From: Jean-François Caron @ 2014-03-20 18:18 UTC (permalink / raw)
  To: gsl-discuss

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 <patrick.alken@colorado.edu> 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 <patrick.alken@Colorado.EDU> 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 <dave.allured@noaa.gov> 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 <jfcaron@phas.ubc.ca>
>>>>>> 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
> 

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: Compiling & Testing New Interpolation Type
  2014-03-20 18:18                               ` Jean-François Caron
@ 2014-03-20 18:30                                 ` Patrick Alken
  2014-03-25 21:56                                   ` Jean-François Caron
  0 siblings, 1 reply; 17+ messages in thread
From: Patrick Alken @ 2014-03-20 18:30 UTC (permalink / raw)
  To: gsl-discuss

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 <patrick.alken@colorado.edu> 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 <patrick.alken@Colorado.EDU> 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 <dave.allured@noaa.gov> 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 <jfcaron@phas.ubc.ca>
>>>>>>> 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

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: Compiling & Testing New Interpolation Type
  2014-03-20 18:30                                 ` Patrick Alken
@ 2014-03-25 21:56                                   ` Jean-François Caron
  2014-03-25 22:51                                     ` Jean-François Caron
  0 siblings, 1 reply; 17+ messages in thread
From: Jean-François Caron @ 2014-03-25 21:56 UTC (permalink / raw)
  To: gsl-discuss

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 <patrick.alken@Colorado.EDU> 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 <patrick.alken@colorado.edu> 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 <patrick.alken@Colorado.EDU> 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 <dave.allured@noaa.gov> 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 <jfcaron@phas.ubc.ca>
>>>>>>>> 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
> 

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: Compiling & Testing New Interpolation Type
  2014-03-25 21:56                                   ` Jean-François Caron
@ 2014-03-25 22:51                                     ` Jean-François Caron
  2014-03-27  1:10                                       ` Jean-François Caron
  0 siblings, 1 reply; 17+ messages in thread
From: Jean-François Caron @ 2014-03-25 22:51 UTC (permalink / raw)
  To: gsl-discuss

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 <jfcaron@phas.ubc.ca> 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 <patrick.alken@Colorado.EDU> 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 <patrick.alken@colorado.edu> 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 <patrick.alken@Colorado.EDU> 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 <dave.allured@noaa.gov> 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 <jfcaron@phas.ubc.ca>
>>>>>>>>> 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
>> 
> 

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: Compiling & Testing New Interpolation Type
  2014-03-25 22:51                                     ` Jean-François Caron
@ 2014-03-27  1:10                                       ` Jean-François Caron
  2014-03-27  8:13                                         ` Patrick Alken
  0 siblings, 1 reply; 17+ messages in thread
From: Jean-François Caron @ 2014-03-27  1:10 UTC (permalink / raw)
  To: gsl-discuss

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 <jfcaron@phas.ubc.ca> 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 <jfcaron@phas.ubc.ca> 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 <patrick.alken@Colorado.EDU> 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 <patrick.alken@colorado.edu> 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 <patrick.alken@Colorado.EDU> 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 <dave.allured@noaa.gov> 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 <jfcaron@phas.ubc.ca>
>>>>>>>>>> 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
>>> 
>> 
> 

^ permalink raw reply	[flat|nested] 17+ messages in thread

* RE: Compiling & Testing New Interpolation Type
  2014-03-27  1:10                                       ` Jean-François Caron
@ 2014-03-27  8:13                                         ` Patrick Alken
       [not found]                                           ` <ACADDE72-BE04-4B2E-8553-FA83C0DC227C@phas.ubc.ca>
  0 siblings, 1 reply; 17+ messages in thread
From: Patrick Alken @ 2014-03-27  8:13 UTC (permalink / raw)
  To: gsl-discuss

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: gsl-discuss-owner@sourceware.org [gsl-discuss-owner@sourceware.org] On Behalf Of Jean-François Caron [jfcaron@phas.ubc.ca]
Sent: Wednesday, March 26, 2014 7:10 PM
To: gsl-discuss@sourceware.org
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 <jfcaron@phas.ubc.ca> 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 <jfcaron@phas.ubc.ca> 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 <patrick.alken@Colorado.EDU> 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 <patrick.alken@colorado.edu> 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 <patrick.alken@Colorado.EDU> 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 <dave.allured@noaa.gov> 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 <jfcaron@phas.ubc.ca>
>>>>>>>>>> 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
>>>
>>
>

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: Compiling & Testing New Interpolation Type
       [not found]                                           ` <ACADDE72-BE04-4B2E-8553-FA83C0DC227C@phas.ubc.ca>
@ 2014-03-27 17:17                                             ` Jean-François Caron
  2014-03-31 20:37                                               ` Steffen interpolation Patrick Alken
  0 siblings, 1 reply; 17+ messages in thread
From: Jean-François Caron @ 2014-03-27 17:17 UTC (permalink / raw)
  To: gsl-discuss

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 <patrick.alken@Colorado.EDU> 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: gsl-discuss-owner@sourceware.org [gsl-discuss-owner@sourceware.org] On Behalf Of Jean-François Caron [jfcaron@phas.ubc.ca]
>> Sent: Wednesday, March 26, 2014 7:10 PM
>> To: gsl-discuss@sourceware.org
>> 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 <jfcaron@phas.ubc.ca> 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 <jfcaron@phas.ubc.ca> 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 <patrick.alken@Colorado.EDU> 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 <patrick.alken@colorado.edu> 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 <patrick.alken@Colorado.EDU> 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 <dave.allured@noaa.gov> 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 <jfcaron@phas.ubc.ca>
>>>>>>>>>>>> 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
>>>>> 
>>>> 
>>> 
>> 
> 

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Steffen interpolation
  2014-03-27 17:17                                             ` Jean-François Caron
@ 2014-03-31 20:37                                               ` Patrick Alken
  2014-03-31 22:24                                                 ` Patrick Alken
  0 siblings, 1 reply; 17+ messages in thread
From: Patrick Alken @ 2014-03-31 20:37 UTC (permalink / raw)
  To: gsl-discuss

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 <patrick.alken@Colorado.EDU> 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: gsl-discuss-owner@sourceware.org [gsl-discuss-owner@sourceware.org] On Behalf Of Jean-François Caron [jfcaron@phas.ubc.ca]
>>> Sent: Wednesday, March 26, 2014 7:10 PM
>>> To: gsl-discuss@sourceware.org
>>> 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 <jfcaron@phas.ubc.ca> 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 <jfcaron@phas.ubc.ca> 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 <patrick.alken@Colorado.EDU> 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 <patrick.alken@colorado.edu> 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 <patrick.alken@Colorado.EDU> 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 <dave.allured@noaa.gov> 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 <jfcaron@phas.ubc.ca>
>>>>>>>>>>>>> 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

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: Steffen interpolation
  2014-03-31 20:37                                               ` Steffen interpolation Patrick Alken
@ 2014-03-31 22:24                                                 ` Patrick Alken
       [not found]                                                   ` <958F2963-D3D1-4BC0-8081-EB56644E3AEE@phas.ubc.ca>
  0 siblings, 1 reply; 17+ messages in thread
From: Patrick Alken @ 2014-03-31 22:24 UTC (permalink / raw)
  To: gsl-discuss

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 <patrick.alken@Colorado.EDU> 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: gsl-discuss-owner@sourceware.org [gsl-discuss-owner@sourceware.org] On Behalf Of Jean-François Caron [jfcaron@phas.ubc.ca]
>>>> Sent: Wednesday, March 26, 2014 7:10 PM
>>>> To: gsl-discuss@sourceware.org
>>>> 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 <jfcaron@phas.ubc.ca> 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 <jfcaron@phas.ubc.ca> 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 <patrick.alken@Colorado.EDU> 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 <patrick.alken@colorado.edu> 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 <patrick.alken@Colorado.EDU> 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 <dave.allured@noaa.gov> 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 <jfcaron@phas.ubc.ca>
>>>>>>>>>>>>>> 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

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: Steffen interpolation
       [not found]                                                   ` <958F2963-D3D1-4BC0-8081-EB56644E3AEE@phas.ubc.ca>
@ 2014-04-03 21:51                                                     ` Patrick Alken
  2014-04-03 21:53                                                       ` Jean-François Caron
  0 siblings, 1 reply; 17+ messages in thread
From: Patrick Alken @ 2014-04-03 21:51 UTC (permalink / raw)
  To: gsl-discuss

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 <patrick.alken@Colorado.EDU> 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 <patrick.alken@Colorado.EDU> 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: gsl-discuss-owner@sourceware.org [gsl-discuss-owner@sourceware.org] On Behalf Of Jean-François Caron [jfcaron@phas.ubc.ca]
>>>>>> Sent: Wednesday, March 26, 2014 7:10 PM
>>>>>> To: gsl-discuss@sourceware.org
>>>>>> 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 <jfcaron@phas.ubc.ca> 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 <jfcaron@phas.ubc.ca> 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 <patrick.alken@Colorado.EDU> 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 <patrick.alken@colorado.edu> 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 <patrick.alken@Colorado.EDU> 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 <dave.allured@noaa.gov> 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 <jfcaron@phas.ubc.ca>
>>>>>>>>>>>>>>>> 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

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: Steffen interpolation
  2014-04-03 21:51                                                     ` Patrick Alken
@ 2014-04-03 21:53                                                       ` Jean-François Caron
  2014-04-03 22:01                                                         ` Patrick Alken
  0 siblings, 1 reply; 17+ messages in thread
From: Jean-François Caron @ 2014-04-03 21:53 UTC (permalink / raw)
  To: Patrick Alken; +Cc: gsl-discuss

Looks good to me.

Jean-François

On Apr 3, 2014, at 14:51 , Patrick Alken <patrick.alken@Colorado.EDU> 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 <patrick.alken@Colorado.EDU> 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 <patrick.alken@Colorado.EDU> 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: gsl-discuss-owner@sourceware.org [gsl-discuss-owner@sourceware.org] On Behalf Of Jean-François Caron [jfcaron@phas.ubc.ca]
>>>>>>> Sent: Wednesday, March 26, 2014 7:10 PM
>>>>>>> To: gsl-discuss@sourceware.org
>>>>>>> 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 <jfcaron@phas.ubc.ca> 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 <jfcaron@phas.ubc.ca> 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 <patrick.alken@Colorado.EDU> 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 <patrick.alken@colorado.edu> 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 <patrick.alken@Colorado.EDU> 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 <dave.allured@noaa.gov> 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 <jfcaron@phas.ubc.ca>
>>>>>>>>>>>>>>>>> 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
> 

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: Steffen interpolation
  2014-04-03 21:53                                                       ` Jean-François Caron
@ 2014-04-03 22:01                                                         ` Patrick Alken
  2014-04-03 22:07                                                           ` Jean-François Caron
  0 siblings, 1 reply; 17+ messages in thread
From: Patrick Alken @ 2014-04-03 22:01 UTC (permalink / raw)
  To: gsl-discuss

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 <patrick.alken@Colorado.EDU> 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 <patrick.alken@Colorado.EDU> 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 <patrick.alken@Colorado.EDU> 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: gsl-discuss-owner@sourceware.org [gsl-discuss-owner@sourceware.org] On Behalf Of Jean-François Caron [jfcaron@phas.ubc.ca]
>>>>>>>> Sent: Wednesday, March 26, 2014 7:10 PM
>>>>>>>> To: gsl-discuss@sourceware.org
>>>>>>>> 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 <jfcaron@phas.ubc.ca> 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 <jfcaron@phas.ubc.ca> 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 <patrick.alken@Colorado.EDU> 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 <patrick.alken@colorado.edu> 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 <patrick.alken@Colorado.EDU> 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 <dave.allured@noaa.gov> 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 <jfcaron@phas.ubc.ca>
>>>>>>>>>>>>>>>>>> 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

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: Steffen interpolation
  2014-04-03 22:01                                                         ` Patrick Alken
@ 2014-04-03 22:07                                                           ` Jean-François Caron
  2014-04-03 22:29                                                             ` Patrick Alken
  0 siblings, 1 reply; 17+ messages in thread
From: Jean-François Caron @ 2014-04-03 22:07 UTC (permalink / raw)
  To: Patrick Alken; +Cc: gsl-discuss

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 <patrick.alken@Colorado.EDU> 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 <patrick.alken@Colorado.EDU> 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 <patrick.alken@Colorado.EDU> 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 <patrick.alken@Colorado.EDU> 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: gsl-discuss-owner@sourceware.org [gsl-discuss-owner@sourceware.org] On Behalf Of Jean-François Caron [jfcaron@phas.ubc.ca]
>>>>>>>>> Sent: Wednesday, March 26, 2014 7:10 PM
>>>>>>>>> To: gsl-discuss@sourceware.org
>>>>>>>>> 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 <jfcaron@phas.ubc.ca> 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 <jfcaron@phas.ubc.ca> 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 <patrick.alken@Colorado.EDU> 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 <patrick.alken@colorado.edu> 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 <patrick.alken@Colorado.EDU> 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 <dave.allured@noaa.gov> 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 <jfcaron@phas.ubc.ca>
>>>>>>>>>>>>>>>>>>> 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
> 

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: Steffen interpolation
  2014-04-03 22:07                                                           ` Jean-François Caron
@ 2014-04-03 22:29                                                             ` Patrick Alken
  0 siblings, 0 replies; 17+ messages in thread
From: Patrick Alken @ 2014-04-03 22:29 UTC (permalink / raw)
  To: gsl-discuss

On 04/03/2014 04:07 PM, Jean-François Caron wrote:
> Cool, do you have a general idea of when these changes will make it into an official release?
Not sure but hopefully within a few months. There are a few things I 
want to ask the list about the 2.0 release so I'll start a separate 
thread on that soon.

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: Steffen interpolation
       [not found] <01cf4fdc$Blat.v3.1.2$46a9eb4f$255c3f79@tbeu.de>
@ 2014-04-04 15:57 ` Patrick Alken
  0 siblings, 0 replies; 17+ messages in thread
From: Patrick Alken @ 2014-04-04 15:57 UTC (permalink / raw)
  To: tbeu, gsl-discuss

Thanks for noticing this - I moved those parameters into the steffen 
state workspace and replaced the fmin() and copysign() functions which 
are not c89 compliant. Things should be working now under c89

Patrick

On 04/04/2014 02:02 AM, tbeu wrote:
> Hi,
>
> not sure if my comment at https://github.com/jfcaron3/gsl-steffen-devel/issues/1 is considered, but please make it C89 compliant. Thanks!
>
> Best regards,
> tbeu
>
>
> ---
> avast! Antivirus: Ausgehende Nachricht sauber.
> Virus-Datenbank (VPS): 140403-1, 03.04.2014
> Getestet am: 04.04.2014 10:02:51
> avast! - copyright (c) 1988-2014 AVAST Software.
> http://www.avast.com
>
>
>

^ permalink raw reply	[flat|nested] 17+ messages in thread

end of thread, other threads:[~2014-04-04 15:57 UTC | newest]

Thread overview: 17+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
     [not found] <57ABFACA-CA7C-439D-9695-F136F0142156@phas.ubc.ca>
     [not found] ` <5328EF5C.5010300@colorado.edu>
     [not found]   ` <0665FACA-1454-4C7C-80B5-30D08E71A1B7@phas.ubc.ca>
     [not found]     ` <A5FA6472-084A-4335-AC4A-4824AA14F1AF@phas.ubc.ca>
     [not found]       ` <5329F67E.7080203@colorado.edu>
     [not found]         ` <CAKZ7wvc+Pf7QR+cxcK9Lm3ad5bMpBqw1qn0HAhtnfr7sDfK3Fw@mail.gmail.com>
     [not found]           ` <532A124B.4090608@colorado.edu>
     [not found]             ` <532A13D0.2050609@colorado.edu>
     [not found]               ` <CALqwTFO7nJ_aDpYKq+RSLmJHTduK0SDgKFnJZLEx14G5ZfojHA@mail.gmail.com>
     [not found]                 ` <CAKZ7wve=fwdkH+0u3NSirH6-aK7u5TTfZe9kjPzGDVYznjfUxw@mail.gmail.com>
     [not found]                   ` <CALqwTFOMN-brCpnVzV2ebMn57sGbK_wE4v1Qs-apUQxz69kO6Q@mail.gmail.com>
     [not found]                     ` <8EA5CA7B-E4C4-48A0-A9EB-BA77F3F1AC11@phas.ubc.ca>
     [not found]                       ` <532B23E3.7050700@colorado.edu>
     [not found]                         ` <AE615778-0196-446E-84C9-C2DB09934F01@phas.ubc.ca>
2014-03-20 17:52                           ` Compiling & Testing New Interpolation Type Patrick Alken
2014-03-20 18:04                             ` Patrick Alken
2014-03-20 18:18                               ` Jean-François Caron
2014-03-20 18:30                                 ` Patrick Alken
2014-03-25 21:56                                   ` Jean-François Caron
2014-03-25 22:51                                     ` Jean-François Caron
2014-03-27  1:10                                       ` Jean-François Caron
2014-03-27  8:13                                         ` Patrick Alken
     [not found]                                           ` <ACADDE72-BE04-4B2E-8553-FA83C0DC227C@phas.ubc.ca>
2014-03-27 17:17                                             ` Jean-François Caron
2014-03-31 20:37                                               ` Steffen interpolation Patrick Alken
2014-03-31 22:24                                                 ` Patrick Alken
     [not found]                                                   ` <958F2963-D3D1-4BC0-8081-EB56644E3AEE@phas.ubc.ca>
2014-04-03 21:51                                                     ` Patrick Alken
2014-04-03 21:53                                                       ` Jean-François Caron
2014-04-03 22:01                                                         ` Patrick Alken
2014-04-03 22:07                                                           ` Jean-François Caron
2014-04-03 22:29                                                             ` Patrick Alken
     [not found] <01cf4fdc$Blat.v3.1.2$46a9eb4f$255c3f79@tbeu.de>
2014-04-04 15:57 ` Patrick Alken

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).