3 ms·
The most efficient implementation of Lagrange Interpolators is O(N). Calculate the left Product(0..i-1) of each term in left-to-right order, and the Product(i+
by rerdavies 4y ago
The most efficient implementation of Lagrange Interpolators is O(N).
Calculate the left Product(0..i-1) of each term in left-to-right order, and the Product(i+1..N-1) of each term in right-to-left order. Your mileage may vary on a GPU.
- steppi 4y agoI think you're talking about evaluating the interpolating polynomial at a single value, but others are talking about getting all of the coefficients of the interpolating polynomial.
- pkhuong 4y agoGP is referring to https://en.wikipedia.org/wiki/Lagrange_polynomial https://en.wikipedia.org/wiki/Lagrange_polynomial Build a table left[j] of product-of-ratios for i < j, and another right[k] for i > k, each in linear-time, and combine the two to find the product-of-ratio for i != m in linear time as well.
- steppi 4y agoRight, and if we are trying to get all coefficients and are thus performing the polynomial multiplications symbolically, then performing the multiplications naively will take O(n^2) time but using FFT allows it to be done in O(n log n) time.
- credit_guy 4y agoI'm not aware of any algorithm for Lagrange interpolation that is O(N), and wikipedia does not know one either. What do you mean by left product and right product?
- rerdavies 4y ago:-( Walking it back a bit. For common cases, O[N], but O[N^2] for initialization. https://news.ycombinator.com/edit?id=34720462 https://news.ycombinator.com/edit?id=34720462