steps to convert spline from B-form to pp-form (fn2fm)

x = [3.0,4.5,6.0,7.5,9.0,12.0,15.0];
y = [0 0.0343653 0.0694232 0.105143 0.141178 0.246013 0.630537];
f_bm = spapi(5, x, y);
f_pp = fn2fm(f_bm, 'pp');

Based on f_bm.knots, it is easy to compute f_pp.breaks. But how is f_pp.coefs calculated? Is there a linear system solved or is there an analytical equation for computing the coefficients based on the control points + knots + degree?

Thank you!

[SA-W]

Given a spline in B-form with control Points and a knot vector , how can we get the coefficients contained in the pp-form on . Is there an analytical equation ? Or are the 's determined via re-fitting? I just want to understand/reprodce what happends under the hood when I call fn2fm and convert from B-form to pp-form.

[Torsten]

Why not simply evaluating s, s',..., s^(j) at x = x_i ? This will give c_j*j! in your pp-form expansion around x_i.

[SA-W]

Torsten's solution seems to be the easisest one to implement.

Why not simply evaluating s, s',..., s^(j) at x = x_i ? This will give c_j*j! in your pp-form expansion around x_i.

Say we have order = 4 (cubic spline), hence we need four equations to setup defined on . By evaluating the value, first, second, third derivative of the spline in B-form at we have determined the coefficients . Like Torsten said.

But interestingly, and the derivatives up to third order also match the values at (and everywhere in the interval) although we only used values from for calculating the coefficients. Why is that? I mean pp-form is just a different expression of the same spline, so it should indeed match. However, we only used the information from the left point to determine the coefficients but it predicts the values on the entire interval correct.

[Torsten]

A polynomial p of order n is determined by p(x0),p'(x0),...,p^(n)(x0) on all of IR for any point x0.

This follows from its Taylor expansion

p(x) = sum_{i=0}^{i=n} p^(i)(x0)/i! * (x-x0)^i

[Torsten]

@SA-W By evaluating the value, first, second, third derivative of the spline in B-form at we have determined the coefficients . Like Torsten said.

Better use the value of the function at x_(i+1) as 4th condition instead of something with third derivatives.

[SA-W]

@Torsten

In my previous comment, I wanted to refer to the following:

If we have defined on and determine by evaluting (i) , its (ii) first + (iii) second + (iv) third derivative at the point , the value and derivatives of and are the same for . Do you have an explanation why? We have not used any boundary condtion from the right point to determine the coefficients but the derivatives up to second order (as Bruno said) coincide.

[Bruno Luong]

Still wonder: if you allow to use stock functions such as fnval fnder why not using fn2fm to convert B-spline to pp form?

Why bother when MATLAB provide a ready-to-go solution?

[Torsten]

Why bother when MATLAB provide a ready-to-go solution?

Maybe for the theory-part of his/her paper on the subject.

[SA-W]

Maybe for the theory-part of his/her paper on the subject.

Exactly. And, of course, I want to have a basis understanding of what happens when I call fn2fm or friends.

[SA-W]

@Bruno Luong

Why did you delete your answers?

[Bruno Luong]

@SA-W Because my answers do not address how fn2fm specifically works

[SA-W]

You answered my question. If you want to repost it, I will accept.

Answer 1

[Bruno Luong]

The pp-form stores the polynomial of each each subiterval, the variable is x := (t-ti) where ti is the left knot of interval #i. https://www.mathworks.com/help/curvefit/the-ppform.html

In my BSFK FEX https://www.mathworks.com/matlabcentral/fileexchange/25872-free-knot-spline-approximation

there is a function private/Bspline2pp.m that just does the conversion to pp

It evalutes the spline in k points inside each subitervals then invert the Vandermond matrix to compute a row of pp.coefs. The last stage can be done with polyfit for coding convenience.

You can also compute from Taylor expansion of the polynomial wrt th the left knot as Torsen has suggested.

It requires to compute 0 to (k-1) order derivatives

Code to avoid using fn2fm (why?!) if this idea

WARNING this only works for non-duplicated knot vectors

x = [3.0,4.5,6.0,7.5,9.0,12.0,15.0];
y = [0 0.0343653 0.0694232 0.105143 0.141178 0.246013 0.630537];
f_bm = spapi(5, x, y);
f_pp = fn2fm(f_bm, 'pp'); % just used for checking correctness

k = f_bm.order;
breaks = f_bm.knots(k:end-k+1);
pieces = length(breaks)-1;
coefs = zeros(pieces,k);
Sd = f_bm;
xi = breaks(1:pieces);
for j=0:k-1
    coefs(:,k-j) = fnval(Sd, xi)./factorial(j);
    Sd = fnder(Sd);
end
pp = struct('form', 'pp', ...
    'breaks', breaks, ...
    'coefs', coefs,...
    'piecs', pieces, ...
    'order', k, ...
    'dim', 1);
% Check the result
format long
f_pp.coefs

ans = 3×5

-0.000010839458734 0.000095398958747 -0.000104662728187 0.022889129608328 -0.000000000000000 0.000030128251860 -0.000067192922266 0.000053996227019 0.023842354392321 0.087249675574952 0.000176086472898 0.000158768966683 0.000311553851941 0.024130562157454 0.132073372169513

pp.coefs

ans = 3×5

-0.000010839458734 0.000095398958747 -0.000104662728187 0.022889129608328 -0.000000000000000 0.000030128251860 -0.000067192922266 0.000053996227019 0.023842354392321 0.087249675574952 0.000176086472898 0.000158768966683 0.000311553851941 0.024130562157453 0.132073372169513

% Note different last digit in coefs(3,4)

[Bruno Luong]

Direct method without the need of using any MATLAB stock function: Outline (I'm too lazy to implement and test):

I find this article : https://arxiv.org/pdf/2204.05002.pdf

It allows to express the B-spline basis (given a knots array) in term of linear combination of Bernstein polynomials by algorithm 4.1 page 15 of this paper. The authors claim the algorihm is optimal.

Once the Berntein-Bezier coefficients B(j,i,k) are found we just make a tensor product of B(.,.,.) with the B-spline form coefficients {a_j}, then applying the derivative formulae at 0 of Bernstein polynomials https://en.wikipedia.org/wiki/Bernstein_polynomial. Need to take care of the strinkage between unnormalized and normalized variables u and t in this paper, used resp by N_mi and B^k_n basis) and the factorial from Taylor expansion formula. That should give pp-form coefs

[SA-W]

Thanks a lot.

Actually, my motivtion to switch to pp-form is that the evaluation of the spline and its derivatives is faster than in B-form because the B-spline basis functions are defined recursively. This is of course not very efficient in a computer program.

But I found De Boor's algorithm, see e.g wiki, which only needs a for loop to evaluate the spline; no recursion anymore. The algorithm showed at the bottom can be easily adjusted to also compute derivatives up to nth order.

[Bruno Luong]

I'm not sure, the De Boor algorithm and B-spline basis function evaluation are usually both based on Cox–de Boor recursion formula. It is just implement with different workfow. We never need to compute the explitly the basis functions if spline values are required to be calculated.

I suppose (not sure) when you call fnval with B-spline form input, it would use De Boor algorithm.

In my BSFK toolbox it is implement in function private/Berntein.m with vectorasation, if you want to dig in and see how it is implemented in MATLAB.

To me the most efficient evaluation is with pp-form. This is the whole point why this form is invented.