Lower complexity bounds for interpolation algorithms
We introduce and discuss a new computational model for the HermiteLagrange interpolation with nonlinear classes of polynomial interpolants. We distinguish between an interpolation problem and an algorithm that solves it. Our model includes also coalescence phenomena and captures a large variety of k...
Guardado en:
| Publicado: |
2011
|
|---|---|
| Materias: | |
| Acceso en línea: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0885064X_v27_n2_p151_Gimnez http://hdl.handle.net/20.500.12110/paper_0885064X_v27_n2_p151_Gimnez |
| Aporte de: |
| id |
paper:paper_0885064X_v27_n2_p151_Gimnez |
|---|---|
| record_format |
dspace |
| spelling |
paper:paper_0885064X_v27_n2_p151_Gimnez2023-06-08T15:46:37Z Lower complexity bounds for interpolation algorithms Constructible map Geometrically robust map HermiteLagrange interpolation Interpolation algorithm Interpolation problem Lower complexity bound Geometry Lagrange multipliers Rational functions Software engineering Architecture tradeoff analysis methods Arithmetic operations Asymptotically optimal Interpolation algorithms Interpolation problems Lagrange interpolations Lower complexity Nonlinear techniques Interpolation We introduce and discuss a new computational model for the HermiteLagrange interpolation with nonlinear classes of polynomial interpolants. We distinguish between an interpolation problem and an algorithm that solves it. Our model includes also coalescence phenomena and captures a large variety of known HermiteLagrange interpolation problems and algorithms. Like in traditional HermiteLagrange interpolation, our model is based on the execution of arithmetic operations (including divisions) in the field where the data (nodes and values) are interpreted and arithmetic operations are counted at unit cost. This leads us to a new view of rational functions and maps defined on arbitrary constructible subsets of complex affine spaces. For this purpose we have to develop new tools in algebraic geometry which themselves are mainly based on Zariski's Main Theorem and the theory of places (or equivalently: valuations). We finish this paper by exhibiting two examples of Lagrange interpolation problems with nonlinear classes of interpolants, which do not admit efficient interpolation algorithms (one of these interpolation problems requires even an exponential quantity of arithmetic operations in terms of the number of the given nodes in order to represent some of the interpolants). In other words, classic Lagrange interpolation algorithms are asymptotically optimal for the solution of these selected interpolation problems and nothing is gained by allowing interpolation algorithms and classes of interpolants to be nonlinear. We show also that classic Lagrange interpolation algorithms are almost optimal for generic nodes and values. This generic data cannot be substantially compressed by using nonlinear techniques. We finish this paper highlighting the close connection of our complexity results in HermiteLagrange interpolation with a modern trend in software engineering: architecture tradeoff analysis methods (ATAM). © 2010 Elsevier Inc. All rights reserved. 2011 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0885064X_v27_n2_p151_Gimnez http://hdl.handle.net/20.500.12110/paper_0885064X_v27_n2_p151_Gimnez |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-134 |
| collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
| topic |
Constructible map Geometrically robust map HermiteLagrange interpolation Interpolation algorithm Interpolation problem Lower complexity bound Geometry Lagrange multipliers Rational functions Software engineering Architecture tradeoff analysis methods Arithmetic operations Asymptotically optimal Interpolation algorithms Interpolation problems Lagrange interpolations Lower complexity Nonlinear techniques Interpolation |
| spellingShingle |
Constructible map Geometrically robust map HermiteLagrange interpolation Interpolation algorithm Interpolation problem Lower complexity bound Geometry Lagrange multipliers Rational functions Software engineering Architecture tradeoff analysis methods Arithmetic operations Asymptotically optimal Interpolation algorithms Interpolation problems Lagrange interpolations Lower complexity Nonlinear techniques Interpolation Lower complexity bounds for interpolation algorithms |
| topic_facet |
Constructible map Geometrically robust map HermiteLagrange interpolation Interpolation algorithm Interpolation problem Lower complexity bound Geometry Lagrange multipliers Rational functions Software engineering Architecture tradeoff analysis methods Arithmetic operations Asymptotically optimal Interpolation algorithms Interpolation problems Lagrange interpolations Lower complexity Nonlinear techniques Interpolation |
| description |
We introduce and discuss a new computational model for the HermiteLagrange interpolation with nonlinear classes of polynomial interpolants. We distinguish between an interpolation problem and an algorithm that solves it. Our model includes also coalescence phenomena and captures a large variety of known HermiteLagrange interpolation problems and algorithms. Like in traditional HermiteLagrange interpolation, our model is based on the execution of arithmetic operations (including divisions) in the field where the data (nodes and values) are interpreted and arithmetic operations are counted at unit cost. This leads us to a new view of rational functions and maps defined on arbitrary constructible subsets of complex affine spaces. For this purpose we have to develop new tools in algebraic geometry which themselves are mainly based on Zariski's Main Theorem and the theory of places (or equivalently: valuations). We finish this paper by exhibiting two examples of Lagrange interpolation problems with nonlinear classes of interpolants, which do not admit efficient interpolation algorithms (one of these interpolation problems requires even an exponential quantity of arithmetic operations in terms of the number of the given nodes in order to represent some of the interpolants). In other words, classic Lagrange interpolation algorithms are asymptotically optimal for the solution of these selected interpolation problems and nothing is gained by allowing interpolation algorithms and classes of interpolants to be nonlinear. We show also that classic Lagrange interpolation algorithms are almost optimal for generic nodes and values. This generic data cannot be substantially compressed by using nonlinear techniques. We finish this paper highlighting the close connection of our complexity results in HermiteLagrange interpolation with a modern trend in software engineering: architecture tradeoff analysis methods (ATAM). © 2010 Elsevier Inc. All rights reserved. |
| title |
Lower complexity bounds for interpolation algorithms |
| title_short |
Lower complexity bounds for interpolation algorithms |
| title_full |
Lower complexity bounds for interpolation algorithms |
| title_fullStr |
Lower complexity bounds for interpolation algorithms |
| title_full_unstemmed |
Lower complexity bounds for interpolation algorithms |
| title_sort |
lower complexity bounds for interpolation algorithms |
| publishDate |
2011 |
| url |
https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0885064X_v27_n2_p151_Gimnez http://hdl.handle.net/20.500.12110/paper_0885064X_v27_n2_p151_Gimnez |
| _version_ |
1768543807400312832 |