GNU Scientific Library - Bugs: bug #34361, gsl_bspline_knots_greville needs...
You are not allowed to post comments on this tracker with your current authentication level.
bug #34361: gsl_bspline_knots_greville needs inequality constrained linear least squares
Submitter: | Rhys Ulerich <rhysu> | ||
Submitted: | Thu 22 Sep 2011 08:12:00 PM UTC | ||
Category: | Runtime error | Severity: | 3 - Normal |
Operating System: | All | Status: | Need Info |
Assigned to: | rhysu | Open/Closed: | Open |
Release: |
Fri 23 Sep 2011 03:01:39 PM UTC, comment #1: |
Rhys Ulerich <rhysu>![]() ![]() |
Thu 22 Sep 2011 08:12:00 PM UTC, original submission:
A working note...
The new B-spline routine gsl_bspline_knots_greville was added in
Having worked with code a bit, I goofed and failed to include the constraint that breakpoints be strictly increasing. As of r4755 the implementation works for "benign" breakpoint requests but produces broken knot vectors for more challenging ones.
The correct implementation would minimize ||Ax-b||_2 subject to Cx>=d where C describes the difference between adjacent breakpoints and d is strictly positive (and likely double-precision epsilon). That falls into the classical "linear least squares with linear inequality constraints" camp and is covered by Lawson and Hanson in Chapter 23 of "Solving least squares problems" published by SIAM.
I need to spend some time investigating the right way to solve such a problem in the context of the GSL (either by implementing classical techniques or reformulating the problem for another constrained solve approach).
In the meantime, I do not wish to release a partially working implementation. I am removing gsl_bspline_knots_greville from the NEWS file and commenting out its mention in the documentation. I will add a link to this bug in the source code.
I apologize for the partial-but-incomplete feature,
|
Rhys Ulerich <rhysu>![]() ![]() |
No files currently attached
Depends on the following items: None found
Items that depend on this one: None found
Having done some more legwork...
It appears that the nonnegative least squares (NNLS), least distance programming (LDP), and linear least squares with inequality constraints (LSI in PROG6) source from Lawson and Hanson appears on Netlib at http://www.netlib.org/lawson-hanson/ and is public domain (see Appendix C's introduction in their text). Others have f2c-ed this code, removed the libf2c build-and-link prereqs by hand, and successfully employed it. For example, the LGPLed old APPSPACK 3.0.1 available at https://software.sandia.gov/appspack/version3/ did so.
I intend to perform the same f2c-then-cleanup task starting directly from the Netlib sources to ensure the license pedigree remains firmly public domain. According to http://www.gnu.org/licenses/gpl-faq.html#CombinePublicDomainWithGPL and http://www.gnu.org/s/gsl/design/gsl-design.html#SEC40, the resulting code can be distributed with the GSL provided that it remains separated from GPL code.
That should give me the LSI solver I need to correctly finish gsl_bspline_knots_greville.