Polynomial Interpolation: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| (3 intermediate revisions by the same user not shown) | |||
| Line 8: | Line 8: | ||
== Parameters == | == Parameters == | ||
n: number of points | $n$: number of points | ||
d: dimension of space | $d$: dimension of space | ||
== Table of Algorithms == | == Table of Algorithms == | ||
{| class="wikitable sortable" style="text-align:center;" width="100%" | |||
! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference | |||
|- | |||
== Space | | [[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.ezproxy.canberra.edu.au/stable/2004623?origin=crossref&seq=5#metadata_info_tab_contents Time] & [https://academic-oup-com.ezproxy.canberra.edu.au/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.ezproxy.canberra.edu.au/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.ezproxy.canberra.edu.au/article/10.1007/BF01990529 Time] | |||
|- | |||
|} | |||
== Time Complexity Graph == | |||
[[File:Polynomial Interpolation - Time.png|1000px]] | |||
[[File:Polynomial Interpolation - | |||
Latest revision as of 09:12, 28 April 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
Error creating thumbnail: Unable to save thumbnail to destination