What's the algorithm complexity of DYCORS with CubicRBF? about pysot

[ili3p]

Is it O(N^3) where N is the number of points the RBF interpolant uses to build the surface?

[dme65]

pySOT is currently solving the entire RBF system from scratch each time, so each iteration is O(n^3). This adds up to O(n^4). It's possible to do each iteration in O(n^2) by updating the LU-factorization of the RBF system incrementally and that's something that I can easily add to the code. This gives you the desired O(n^3) complexity.

[ili3p]

Then why is Kriging slower?
From the documentation

By default we recommend the CubicRBFSurface (with capping if necessary). We recommend not using Kriging since it is very slow.

Gaussian processes are generally considered slow since the inference time grows cubically in the number of observations, as it necessitates the inversion of a dense covariance matrix. But if RBF is also cubic, I don't see where is the difference. Can you please explain to me?

Thanks

[dme65]

Good question. I'm not that familiar with Kriging and I'm not sure if I can be very helpful without looking at the Kriging implementation that we rely on: https://github.com/capaulson/pyKriging. From numerical tests it looks like Kriging is at least an order of magnitude slower than RBFs.