Polynomial Interpolation: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 14: | Line 14: | ||
== Table of Algorithms == | == Table of Algorithms == | ||
{| class="wikitable sortable" style="text-align:center;" width="100%" | |||
== Time Complexity | ! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference | ||
|- | |||
| [[Gaussian elimination (2-D Polynomial Interpolation Polynomial Interpolation)|Gaussian elimination]] || -150 || $O(n^{3})$ || $O(n^{2})$ || Exact || Deterministic || | |||
|- | |||
| [[Bjorck (2-D Polynomial Interpolation Polynomial Interpolation)|Bjorck]] || 1970 || $O(n^{2})$ || $O(n)$ || Exact || Deterministic || [https://www.jstor.org/stable/2004623?origin=crossref&seq=5#metadata_info_tab_contents Time] & [https://academic.oup.com/imajna/article/8/4/473/758789?login=true Space] | |||
|- | |||
| [[Higham (2-D Polynomial Interpolation Polynomial Interpolation)|Higham]] || 1988 || $O(n^{2})$ || $O(n)$ || Exact || Deterministic || [https://academic.oup.com/imajna/article/8/4/473/758789?login=true Time & Space] | |||
|- | |||
| [[Calvetti, Reichel (2-D Polynomial Interpolation Polynomial Interpolation)|Calvetti, Reichel]] || 1993 || $O(n^{2})$ || $O(n)$? || Exact || Deterministic || [https://link.springer.com/article/10.1007/BF01990529 Time] | |||
|- | |||
|} | |||
== Time Complexity Graph == | |||
[[File:Polynomial Interpolation - Time.png|1000px]] | [[File:Polynomial Interpolation - Time.png|1000px]] | ||
== Space Complexity | == Space Complexity Graph == | ||
[[File:Polynomial Interpolation - Space.png|1000px]] | [[File:Polynomial Interpolation - Space.png|1000px]] | ||
== Pareto | == Pareto Frontier Improvements Graph == | ||
[[File:Polynomial Interpolation - Pareto Frontier.png|1000px]] | [[File:Polynomial Interpolation - Pareto Frontier.png|1000px]] | ||
Revision as of 13:05, 15 February 2023
Description
Given a finite number of points $x_1, \ldots , x_n$, some real constants $y_1, \ldots , y_n$ and a subspace $V$ of $\Pi^d$, find a polynomial $p \in V$, such that
$p(x_j) = y_j$, $j = 1, ... , n$
Parameters
n: number of points
d: dimension of space
Table of Algorithms
| Name | Year | Time | Space | Approximation Factor | Model | Reference |
|---|---|---|---|---|---|---|
| Gaussian elimination | -150 | $O(n^{3})$ | $O(n^{2})$ | Exact | Deterministic | |
| Bjorck | 1970 | $O(n^{2})$ | $O(n)$ | Exact | Deterministic | Time & Space |
| Higham | 1988 | $O(n^{2})$ | $O(n)$ | Exact | Deterministic | Time & Space |
| Calvetti, Reichel | 1993 | $O(n^{2})$ | $O(n)$? | Exact | Deterministic | Time |
Time Complexity Graph
Space Complexity Graph
Pareto Frontier Improvements Graph
