search

dme65 / pySOT

Surrogate Optimization Toolbox for Python
Other
205 stars 53 forks source link

What's the algorithm complexity of DYCORS with CubicRBF? #13

Closed ili3p closed 8 years ago

ili3p commented 8 years ago

Thanks

ili3p commented 8 years ago

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

dme65 commented 8 years ago

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 commented 8 years ago

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 commented 8 years ago

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.