[SciPy-Dev] GSoC 2017: BSpline support

Sun Mar 19 18:08:13 EDT 2017

For future I suggest to put your proposal in markdown format somewhere on github (scipy wiki is a good place).

I don't know what is the correct and productive way to review such proposal, so these are some thoughts on some of your points.

> Rework the tutorial for scipy.interpolate: The 1D interpolation section prominently recommends interp1d. We likely want              to tone it down and recommend instead CubicSpline, Akima1DInterpolator, BSpline etc.

   This can be done after reading some basics about these algorithms and making the changes as required.

Honestly I don't think it is that easy, you definitely need to have a certain taste and interest to rewrite this tutorial. My guess is that you will be able to do it better after you finished the main algorithmic and coding work.

> Come up with better names for make_interp_spline/make_lsq_spline routines.

   This too can be handled after some discussion.

I don't think it is necessary to put things like that in the proposal, you'll figure it out (with Evgeni) as the work progresses.

> Add string aliases to the bc_type keyword of make_interp_spline to match what CubicSpline allows. I.e.                                   bc_type="natural" should be equivalent to bc_type=((2, 0), (2, 0))

 This requires mainly imitating whats there in CubicSpline so wont be very difficult.

This can be indeed your first small objective. The documentation for bc_type in make_interp_spline reads 

"Each of these must be an iterable of pairs (order, value) which gives the values of derivatives of specified orders at the given edge of the interpolation interval."  

So BSpline is quite general and allows specifying conditions for several derivatives at one end (as opposed to CubicSpline). Maybe it will need some special considerations, just something I noticed.

        > Convert a CubicSpline object to a BSpline

 This could be done by assigning the __class__ attribute to the instance. However, since this is not preferred, we may                       construct a new method which will create a new BSpline object using a CubicSpline object by assigning the corresponding               attribute values. (I need your suggestion, which approach to follow?)

 I believe ideally there should be a factory method like `BSpline.from_ppoly(...)`, as a compromise something like `BSpline.from_cubic_spline`, but I'm not sure whether it will be that valuable in that form. The problem might be not that simple, do some research on now to make conversion between polynomial and B-spline basis.

> Knot insertion: BSpline class should grow a method insert_knot (or insert_knots). This can either wrap fitpack.insert                        directly, or reuse parts of it (e.g. retain the buffer swapping plumbing from _fitpack and reimplement the Fortran routine                    fitpack/fpinst.f in C or Cython).

   Since fitpack.insert is already implemented for BSplines, wrapping around it would be the simplest solution as I perceive.

As I see there is already a public function insert (implemented in fitpack.py). So just moving it in as a method pretty much does the job. However is the final aim is to move away from FITPACK, then reimplementing insertion algorithm in Cython is useful. Additionally it can be an entry into more serious problems to follow and doing things in Cython. (Btw, I'm not sure what Evgeni meant by "e.g. retain the buffer swapping plumbing".)

> Root-finding: At a minimum, sproot should be wrapped into a method of BSpline class. Better still, it should be generalized            to allow non-cubic splines. The interface should mirror PPoly.solve and PPoly.roots.

   This too can be done by imitating PPoly.roots and PPoly.solve.

Writing a new implementation for arbitrary spline orders looks like an interesting and challenging problem. Consider doing it instead of just minimal wrapper.

All in all the two previous problems, if done in full capacity, don't seem easy and can occupy you for the good part of the GSoC.

BSpline Variations:-

> Cardinal BSplines (BSplines with equidistant knots). We need representation, evaluation and construction. scipy.signal              has some. The task here is to have an interface which is both compatible with regular b-splines and piecewise polynomials              and is useful for the signal processing folks.

   For implementing this feature I will have to read some material to get a good understanding of Cardinal BSplines and its                    implementation

   These are two of the places (for now) I would start my study from. The implementation in scipy.signal can be of help.

           https://en.wikipedia.org/wiki/B-spline#Cardinal_B-spline

   http://dx.doi.org/10.1016/j.aml.2010.06.029

   This task could take a long time, maybe 3 weeks or more.

> Spline fitting to data. ATM there's only FITPACK, and we want a more controllable alternative. A first exploratory shot could            be to implement de Boors's newknot routine and see how it behaves in real life.

   This too requires reading of some literature to understand the math and also looking at the FITPACK code for guidance.

   The following literature can be helpful.

   https://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/B-spline/de-Boor.html

   https://en.wikipedia.org/wiki/De_Boor%27s_algorithm

 Both these tasks would take over a month for complete implementation.

Generally I suggest to pick (at least for now) one subject most interesting to you and think it through in more details. Now it's unclear what exactly you want to program (which classes, functions, etc.) and time estimates don't look reliable. For "Spline fitting to data" I'm somewhat confused, because make_lsq_spline and make_interp_spline seem to already solve fitting problems without relying on FITPACK. Evgeni, what is the situation here?

For now that's all from me. To sum up: focus on fewer things with more details, you don't necessary need to go into the most advanced things. If I'm not mistaken, the whole project can be organized as "get rid of some things from fitpack" and it can be good.

I think Evgeni will clarify/comment on things.

Nikolay.

After looking at the issue tracker #6730 I have made my first proposal for the GSoC project "Improve support for B-splines". This is in continuation with my first mail regarding the same matter.

This is a long list of what I think could be done as part of the project. I don't have much knowledge of Splines or B-Splines hence the work plan is not very detailed. Please have a look.

Minor changes:-

::: Documentation:

> Rework the tutorial for scipy.interpolate: The 1D interpolation section prominently recommends interp1d. We likely want              to tone it down and recommend instead CubicSpline, Akima1DInterpolator, BSpline etc.

   This can be done after reading some basics about these algorithms and making the changes as required.

> Come up with better names for make_interp_spline/make_lsq_spline routines.

   This too can be handled after some discussion.

Both these documentation changes can be done within a few days time, 3 to 4 days should be enough.

::: Enhancements:

> Add string aliases to the bc_type keyword of make_interp_spline to match what CubicSpline allows. I.e.                                   bc_type="natural" should be equivalent to bc_type=((2, 0), (2, 0))

 This requires mainly imitating whats there in CubicSpline so wont be very difficult.

        > Convert a CubicSpline object to a BSpline

 This could be done by assigning the __class__ attribute to the instance. However, since this is not preferred, we may                       construct a new method which will create a new BSpline object using a CubicSpline object by assigning the corresponding               attribute values. (I need your suggestion, which approach to follow?)

 Both these tasks should not take more than 6 to 7 days, including all the documentation and unit tests.

Major Enhancements:-

> Knot insertion: BSpline class should grow a method insert_knot (or insert_knots). This can either wrap fitpack.insert                        directly, or reuse parts of it (e.g. retain the buffer swapping plumbing from _fitpack and reimplement the Fortran routine                    fitpack/fpinst.f in C or Cython).

   Since fitpack.insert is already implemented for BSplines, wrapping around it would be the simplest solution as I perceive.

> Root-finding: At a minimum, sproot should be wrapped into a method of BSpline class. Better still, it should be generalized            to allow non-cubic splines. The interface should mirror PPoly.solve and PPoly.roots.

   This too can be done by imitating PPoly.roots and PPoly.solve.

 Both these tasks can be completed within 10 days time including all the documentation and tests.

BSpline Variations:-

> Cardinal BSplines (BSplines with equidistant knots). We need representation, evaluation and construction. scipy.signal              has some. The task here is to have an interface which is both compatible with regular b-splines and piecewise polynomials              and is useful for the signal processing folks.

   For implementing this feature I will have to read some material to get a good understanding of Cardinal BSplines and its                    implementation

   These are two of the places (for now) I would start my study from. The implementation in scipy.signal can be of help.

           https://en.wikipedia.org/wiki/B-spline#Cardinal_B-spline

   http://dx.doi.org/10.1016/j.aml.2010.06.029

   This task could take a long time, maybe 3 weeks or more.

> Spline fitting to data. ATM there's only FITPACK, and we want a more controllable alternative. A first exploratory shot could            be to implement de Boors's newknot routine and see how it behaves in real life.

   This too requires reading of some literature to understand the math and also looking at the FITPACK code for guidance.

   The following literature can be helpful.

   https://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/B-spline/de-Boor.html

   https://en.wikipedia.org/wiki/De_Boor%27s_algorithm

 Both these tasks would take over a month for complete implementation.

optional:

I am not sure about the scope of these additions. Also, if we decide to implement these, I am not quite sure they can be                   completed within the span of GSoC. Probably, we can just take up one of these tasks.

> PSpline: The term P-spline stands for "penalized B-spline". It refers to using the B-spline representation where the                            coefficients are determined partly by the data to be fitted, and partly by an additional penalty function that aims to impose                  smoothness to avoid overfitting.

   Adequate literature can be found here,

 https://projecteuclid.org/download/pdf_1/euclid.ss/1038425655

 SAS have already implemented it,

 https://support.sas.com/documentation/cdl/en/statug/63033/HTML/default/viewer.htm#statug_transreg_sect020.htm

 This feature could take up a lot of time, including documentation,tests,examples etc.

> Non-Uniform Rational B-splines (NURBS):  Unlike simple B-splines, the control points each have a weight.

 The following literature can be helpful,

 https://en.wikipedia.org/wiki/Non-uniform_rational_B-spline

 https://www.rhino3d.com/nurbs

 The following articles can help with the implementation.

 https://www.codeproject.com/Articles/996281/NURBS-curve-made-easy

 http://www.nar-associates.com/nurbs/c_code.html#chapter4

 This feature too can take up lots of time for full completion.

> Constructing periodic splines. Fitpack does it. With full matrices it's straightforward, a naive implementation with banded              matrices has issues with numerical stability.

   We can definitely look into the banded matrix issue if time permits. I am not sure what we may find so cant say anything                    about the time required.

Final Assessment:-

After these tasks have been completed. All the new features,methods would undergo rigorous tests and doctests. Benchmark tests could also be added wherever necessary. Features having scope for work could be reported on GitHub.

I plan on reading as much as I can related to Cardinal BSplines,De Boor's newknot routine,Penalized BSplines,NURBS etc. before the start of GSoC. This will help me in saving time finding literature related to all these new additions.

Looking forward to feedback and corrections.

On 16 March 2017 at 20:03, Evgeni Burovski <evgeny.burovskiy at gmail.com> wrote:

_______________________________________________

SciPy-Dev mailing list 

SciPy-Dev at scipy.org 

https://mail.scipy.org/mailman/listinfo/scipy-dev 

On Thu, Mar 16, 2017 at 11:06 AM, Aman Pratik <amanpratik10 at gmail.com> wrote:

Hello Developers,

This is Aman Pratik. I am currently pursuing my B.Tech from Indian Institute of Technology, Varanasi. I am a keen software developer and not very new to the open source community. I am interested in your project "Improve support for B-splines" for GSoC 2017.

I have been working in Python for the past 2 years and have good idea about Mathematical Methods and Techniques. I am quite familiar with scipy mainly as a user and also as a developer. I also have some experience with Cython.

These are the PRs I have worked/working on for the past month.

ENH: Add evaluation of periodic splines #6730

DOC: Bad documentation of k in sparse.linalg.eigs See #6990 (Merged)

ENH: scipy.linalg.eigsh cannot get all eigenvalues #7004

My GitHub Profile: https://www.github.com/amanp10

I am interested in Mathematical models and functions and therefore willing to work on splines. Also, I am familiar with Benchmark tests, Unit tests and other technical knowledge I would require for this project. I have started my study for the subject and am looking forward to guidance from the potential mentors or other developers.

Thank You

Hi Aman, and welcome!

I see that you already started with https://github.com/scipy/scipy/pull/7185, great!

We'll also need a proposal. Since writing a good proposal typically takes several iterations, I encourage you to start working on it, too. When you have a draft, please send it to the list.

All the best,

Evgeni

_______________________________________________

SciPy-Dev mailing list

SciPy-Dev at scipy.org

https://mail.scipy.org/mailman/listinfo/scipy-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20170320/29f1df10/attachment.html>