search

bgrimstad / splinter

Library for multivariate function approximation with splines (B-spline, P-spline, and more) with interfaces to C++, C, Python and MATLAB
Mozilla Public License 2.0
418 stars 115 forks source link

Is a bijection possible in a spline which is monotonous in one coordinate? #91

Closed ChrisS85 closed 6 years ago

ChrisS85 commented 7 years ago

Not sure if this is the correct place to ask.

I'm working on a simulation code which currently uses a linear interpolation class for 2D lookup tables. I would like to extend it to multidimensional lookup tables which use second order interpolation or possibly higher.

The code requires two tables which have one of the coordinates and y exchanged, i.e. first table: x_0 ... x_i ... x_n -> y second table: x_0 ... y ... x_n -> x_i The data in the tables is monotonous in x_i / y, so the mapping is bijective.

Will a second instance where coordinates are exchanged before creating the spline give such a bijective mapping? If not, is there a reasonably fast search function for a function value, given all but one coordinate? I didn't find anything appropriate while looking through the headers. I know that black-box solutions like Newton-Raphson are possible, but I would prefer a faster direct lookup because this is a performance-critical component in the code.

ChrisS85 commented 7 years ago

I realized this cannot work and also wrote a test to verify. Guess I will have to resort to a root finding algorithm then or stick to linear interpolation.

bgrimstad commented 7 years ago

Hi Chris,

Here are my initial thoughts.

If I understand you correctly, you want to use higher order interpolation with multidimensional lookup tables, and you want to find a x_i which gives y, given that all other variables are fixed? If you have verified that simply fitting a B-spline to the second table will not give you a bijective mapping (which confirms my expectations), then I suggest that you do attempt to perform a gradient search on f = y - f(x) using Newton's method along x_i. Gradients are supplied by SPLINTER and it may be fast enough for you application.

Let us know how it goes.

bgrimstad commented 6 years ago

Closing this issue since it will not lead to any code changes.