Multivariate Normal Hermite-Birkhoff Interpolating Splines in Julia
This announces the v0.4.0 release of NormalHermiteSplines.jl package that implements the normal splines method for solving the following interpolation problem:
14 Likes
Sounds great! What are the complexities of constructing and evaluating the splines, respectively, as a function of n_1,n_2,n?
3 Likes
It is necessary to factorize a dense symmetric positive definite matrix of size n_1 (n_1 + n_2) in order to construct an interpolating (Hermite) normal spline. In the package it is done by means of Cholesky decomposition which complexity is about 1/3 n_1^3 (1/3 (n_1 + n_2)^3).
2 Likes
as for evaluating the spline in a node that complexity is O(n(n_1 + n_2)).
2 Likes
Is it possible to use something like a fast Gauss transform to accelerate this?
2 Likes
I’m curious about something similar to @stevengj: do you need a Cholesky factor, or would some more exotic symmetric factorization that also admitted nice solves be feasible? Several H-matrix formats don’t easily admit a triangular symmetric factor, but they have other ways of getting nice fast solves. And for kernels that are smooth away from the origin there probably is some nice structure.
Very cool stuff, by the way! Thanks for writing such nice examples/docs, too.
1 Like
Thank you, @stevengj and @ cgeoga for your ideas, it could work. There are a few approaches of improving performance of the RBF-based interpolation methods, e.g. partition of unity, multilevel and fast multi-poles ones. However, my next goal is implementing code of the Multivariate Normal Smoothing Splines project. Constructing the spline is based on solving a simplest finite-dimensional quadratic programming problem. There are simple and pretty fast quadratic programming algorithms
Quadratic Programming in Hilbert space
and
Adaptive Quadratic Programming in Hilbert space
These algorithms are based on solving multiple systems of linear equations with positive definite matrices and use relatively fast recalculation of a matrix Cholesky factors.
Algorithms for updating Cholesky factorization
That is why I stick to Cholesky decomposition here.
Regards,
Igor
2 Likes
That sounds like a very interesting next goal! All cool stuff. Thanks for sharing and again for writing up the nice docs and references.
Yesterday I found a paper that fully described the interpolating normal splines method. Here we are:
DIX, JULIO G., and ROBERT D. OGDEN. “AN INTERPOLATION SCHEME WITH RADIAL BASIS IN SOBOLEV SPACES H s. The Rocky Mountain Journal of Mathematics, vol. 24, no. 4, 1994, pp. 1319–1337. JSTOR, AN INTERPOLATION SCHEME WITH RADIAL BASIS IN SOBOLEV SPACES H s (R n ) on JSTOR. Accessed 22 Mar. 2021.
Links:
https://rmmc.asu.edu/rmj/rmjVOLS2/vol24/vol24-4/DIX.pdf
or
1 Like