[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Bug-gsl] [bug #34361] gsl_bspline_knots_greville needs inequality const
From: |
Rhys Ulerich |
Subject: |
[Bug-gsl] [bug #34361] gsl_bspline_knots_greville needs inequality constrained linear least squares |
Date: |
Thu, 22 Sep 2011 20:12:01 +0000 |
User-agent: |
Mozilla/5.0 (X11; U; Linux x86_64; en-US) AppleWebKit/534.16 (KHTML, like Gecko) Ubuntu/10.04 Chromium/10.0.648.151 Chrome/10.0.648.151 Safari/534.16 |
URL:
<http://savannah.gnu.org/bugs/?34361>
Summary: gsl_bspline_knots_greville needs inequality
constrained linear least squares
Project: GNU Scientific Library
Submitted by: rhysu
Submitted on: Thu 22 Sep 2011 08:12:00 PM GMT
Category: Runtime error
Severity: 3 - Normal
Operating System: All
Status: Need Info
Assigned to: rhysu
Open/Closed: Open
Release:
Discussion Lock: Any
_______________________________________________________
Details:
A working note...
The new B-spline routine gsl_bspline_knots_greville was added in
r4750, r4751, r4752, r4753, r4754, and r4755. It aims to provide the best
B-spline basis to best approximate a given target set of Greville abscissae.
The crux of the implementation is minimizing ||Ax-b||_2 for A describing the
mapping from breakpoints to the Greville abscissae. It's just least squares.
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.
Once this bug is fixed, the NEWS entry should again be
** Added gsl_bspline_knots_greville to allow initializing a B-spline
workspace so that it best approximates a target set of Greville
abscissae. The function facilitates projecting data from fixed
collocation points onto a B-spline basis.
I apologize for the partial-but-incomplete feature,
Rhys
_______________________________________________________
Reply to this item at:
<http://savannah.gnu.org/bugs/?34361>
_______________________________________________
Message sent via/by Savannah
http://savannah.gnu.org/
- [Bug-gsl] [bug #34361] gsl_bspline_knots_greville needs inequality constrained linear least squares,
Rhys Ulerich <=