Polynomial Interpolation: Difference between revisions
Jump to navigation
Jump to search
(Created page with "{{DISPLAYTITLE:Polynomial Interpolation (Polynomial Interpolation)}} == 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 == <pre>n: number of points d: dimension of space</pre> == Table of Algorithms == Currently no algorithms in our database for the given problem. == Time Complexity grap...") |
No edit summary |
||
| (4 intermediate revisions by the same user not shown) | |||
| Line 8: | Line 8: | ||
== Parameters == | == Parameters == | ||
$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 | |||
|- | |||
[[ | | [[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 - | [[File:Polynomial Interpolation - Time.png|1000px]] | ||
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
