[ANN] NormalHermiteSplines.jl v.0.4.0

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:

Documentation

Hermite-Birkhoff Interpolation of Scattered Data

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, www.jstor.org/stable/44237842. Accessed 22 Mar. 2021.

Links:

or
https://projecteuclid.org/journals/rocky-mountain-journal-of-mathematics/volume-24/issue-4/An-Interpolation-Scheme-with-Radial-Basis-in-Sobolev-Spaces-HsRn/10.1216/rmjm/1181072340.full

1 Like