Why is it so fast to calculate one-dimensional cubic Spline interpolation through matlab?

I learned that the Time complexity of one-dimensional cubic Spline interpolation is at least n ^ 2. I implemented the algorithm through C++and solved System of linear equations through LU decomposition, but obviously the computation is too much!

But why does MATLAB quickly solve for data interpolation of 10 million?

Did you use any acceleration methods?

[澳旋]

The matlab code is：

X=linspace(-4,4,10001);
Y=sin(X);
Xq=linspace(-5,5,10000001);
Yq=interp1(X,Y,Xq,'spline');

Answer 1

[Bruno Luong]

"I learned that the Time complexity of one-dimensional cubic Spline interpolation is at least n ^ 2"

What is n?

There is two distinc steps in spline interpolation, (1) estimate the cubic coefficients from each subinterval of the pp form. (2) Find where the query points are in which intervals then evaluate the 3rd cubic polynomial.

The first step is O(N) with N is number of X-Y, as it requires mainy solving a tridiagonal matrix where the complexity is linear to the size.

The second step is O(M*log(N)) if searching using dichotomy method, where M is number of query points. MATLAB can detect also if the knot points are equidistance and use simply a division to find the interval (I don't know if such optimization is implemented in INTERP1), but that brings the complexity to O(M).

In any case O(n^2) you read is NOT optimal for spline.

[澳旋]

Sorry, the cubic Spline interpolation I learned is a kind of "global" interpolation, which requires solving System of linear equations and building the form of Ax=b, while A is about n * n matrix, and n is the number of points. If LU decomposition is used to solve x, then the Time complexity is about O (n ^ 3) (not the n ^ 2 I mentioned earlier), which means that the Time complexity of cubic Spline interpolation is at least O (n ^ 3)?

[Bruno Luong]

No A is tridiagonal matrix, which is known to be solved with O(N) complexity as I said.

I have implemented several spline tools (look at the file exchanges under my name) so I know what I speak.

Whatever the book/reference you read it is NOT the state of art of spline for sure.

[澳旋]

Thank you very much for your reply!

What's the name of the fastest way to solve Ax=b in cubic Spline interpolation, please?

[Bruno Luong]

Thomas algorithm

[Bruno Luong]

"If LU decomposition is used to solve x, then the Time complexity is about O (n ^ 3) (not the n ^ 2 I mentioned earlier"

BTW this figure of complexity must be your (wrong) conclusion, not the book-ref whatever you read. The LU on tridiagonal matrix is O(N), since the Thomas algorithm is actually based on LU.

The key difference is that if ones knows the shape of the input matrix to be decomposed one can stops the loop of LU during the decomposition much earlier. Essentially with this small but important observation the LU becomesThomas algorithm.

Lesson: don't draw a hasty conclusion.

[澳旋]

After a deeper understanding, it is indeed my fault!

LU can stop running as soon as possible to make it more efficient!

Thank you again for your enthusiastic reply!