Artículo
Abstract:
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.
Registro:
| Documento: | Artículo |
| Título: | Lower complexity bounds for interpolation algorithms |
| Autor: | Gimnez, N.; Heintz, J.; Matera, G.; Solernó, P. |
| Filiación: | Instituto Del Desarrollo Humano, Universidad Nacional de General Sarmiento, J.M. Gutirrez 1150 (B1613GSX) Los Polvorines, Buenos Aires, Argentina Departamento de Computacin, Universidad de Buenos Aires and CONICET, Ciudad Universitaria, Pab.I, 1428 Ciudad Autnoma de Buenos Aires, Argentina Departamento de Matemticas, Estadstica y Computacin, Facultad de Ciencias, Universidad de Cantabria, 39071 Santander, Spain Instituto Del Desarrollo Humano, Universidad Nacional de General Sarmiento and CONICET, J.M. Gutirrez 1150 (B1613GSX) Los Polvorines, Buenos Aires, Argentina Departamento de Matemtica, Universidad de Buenos Aires and CONICET, Ciudad Universitaria, Pab.I, 1428 Ciudad Autnoma de Buenos Aires, Argentina |
| Palabras clave: | 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 |
| Año: | 2011 |
| Volumen: | 27 |
| Número: | 2 |
| Página de inicio: | 151 |
| Página de fin: | 187 |
| DOI: | http://dx.doi.org/10.1016/j.jco.2010.10.003 |
| Título revista: | Journal of Complexity |
| Título revista abreviado: | J. Complexity |
| ISSN: | 0885064X |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0885064X_v27_n2_p151_Gimnez |
Referencias:
- Alder, A., (1984) Grenzrang und Grenzkomplexitaμt Aus Algebraischer und Topologischer Sicht, , Ph.D. Thesis, Universitaμt Zürich, Philosophische Fakultaμt II
- Barbacci, M., Klein, M., Longstaff, T., Weinstock, C., Quality attributes (1995) Technical Report CMU/SEI-95-TR-021, ESC-TR-95-021, , Software Engineering Institute, Carnegie Mellon University
- Bass, L., Clements, P., Kazman, R., (2003) Software Architecture in Practice, , second ed. Addison-Wesley Boston, MA
- Bloom, T., Calvi, J.-P., A continuity property of multivariate Lagrange interpolation (1997) Mathematics of Computation, 66 (220), pp. 1561-1577
- Blum, L., Cucker, F., Shub, M., Smale, S., Algebraic settings for the problem "p≠NP"? (1996) Lectures in Applied Mathematics, 32, pp. 125-144. , J. Renegar, M. Shub, S. Smale The Mathematics of Numerical Analysis: 1995 AMS-SIAM Summer Seminar in Applied Mathematics July 17August 11, 1995, Park City, Utah
- Blum, L., Cucker, F., Shub, M., Smale, S., (1998) Complexity and Real Computation, , Springer New York, Berlin, Heidelberg
- Blum, L., Shub, M., Smale, S., On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines (1989) Bull. Amer. Math. Soc., 21 (1), pp. 1-46
- Bürgisser, P., Clausen, M., Shokrollahi, M., Algebraic Complexity Theory (1997) Grundlehren Math. Wiss., 315. , Springer Berlin
- Castro, D., Giusti, M., Heintz, J., Matera, G., Pardo, L.M., The hardness of polynomial equation solving (2003) Foundations of Computational Mathematics, 3 (4), pp. 347-420. , DOI 10.1007/s10208-002-0065-7
- De Boor, C., Ron, A., The least solution for the polynomial interpolation problem (1992) Math. Z., 210 (3), pp. 347-378
- De Boor, C., Ron, A., On multivariate polynomial interpolation (1990) Constr. Approx., 6 (3), pp. 287-302
- Giusti, M., Heintz, J., Kronecker's smart, little black-boxes (2001) London Math. Soc. Lecture Note Ser., 284, pp. 69-104. , Proceedings of Foundations of Computational Mathematics FoCM'99, Oxford 1999
- Grauert, H., Fritzsche, K., Several Complex Variables (1976) Grad. Texts in Math., 38. , Springer New York, Heidelberg, Berlin
- Heintz, J., Kuijpers, B., Constraint databases, data structures and efficient query evaluation (2004) Lecture Notes in Comput. Sci., 3074, pp. 1-24. , Proceedings of Foundations of Computational Mathematics FoCM'99, Oxford 1999
- Heintz, J., Morgenstern, J., On the intrinsic complexity of elimination theory (1983) J. Complexity, 9, pp. 471-498
- Heintz, J., Schnorr, C.-P., Testing polynomials which are easy to compute (1982) Monogr. Enseig. Math., 30, pp. 237-254
- Iversen, B., Generic Local Structure of the Morphisms in Commutative Algebra (1973) Lecture Notes in Math., 310. , Springer New York
- Kazman, R., Klein, M., Barbacci, M., Longstaff, T., Lipson, H., Jeromy Carrire, S., The architecture tradeoff analysis method (1998) Proceedings 4th International Conference on Engineering of Complex Computer Systems, pp. 68-78. , ICECCS'98, 1014 August, 1998 IEEE Computer Society Monterrey, CA, USA
- Kunz, E., (1985) Introduction to Commutative Algebra and Algebraic Geometry, , Birkhuser Boston
- Lang, S., (1993) Algebra, , third ed. Addison-Wesley Reading, Massachusetts
- Marker, O., Model Theory: An Introduction (2002) Grad. Texts in Math., 217. , Springer New York
- Meyer, B., (2000) Object-Oriented Software Construction, , second ed. Prentice-Hall Upper Saddle River, NJ
- Mumford, D., The Red Book of Varieties and Schemes (1988) Lecture Notes in Math., 1358. , Springer New York
- Olver, P.J., On multivariate interpolation (2006) Studies in Applied Mathematics, 116 (2), pp. 201-240. , DOI 10.1111/j.1467-9590.2006.00335.x
- Rojas Paredes, A., (2010) Complexity As Quality Attribute in Software Design, , Master Thesis, Universidad de Buenos Aires, Facultad de Ciencias Exactas y Naturales
- Shafarevich, I.R., (1994) Basic Algebraic Geometry: Varieties in Projective Space, , Springer Berlin, Heidelberg, New York
- Stoer, J., Bulirsch, R., (1993) Introduction to Numerical Analysis, , second ed. Springer Berlin, Heidelberg, New York
- Teissier, B., Varits polaires. II: Multiplicits polaires, sections planes et conditions de Whitney (1982) Lect. Notes Math., 961, pp. 314-491
- Zariski, O., Samuel, P., Commutative Algebra II (1960) Grad. Texts in Math., 39. , Springer New York
Citas:
---------- APA ----------
Gimnez, N., Heintz, J., Matera, G. & Solernó, P. (2011) . Lower complexity bounds for interpolation algorithms. Journal of Complexity, 27(2), 151-187.http://dx.doi.org/10.1016/j.jco.2010.10.003
---------- CHICAGO ----------
Gimnez, N., Heintz, J., Matera, G., Solernó, P. "Lower complexity bounds for interpolation algorithms" . Journal of Complexity 27, no. 2 (2011) : 151-187.http://dx.doi.org/10.1016/j.jco.2010.10.003
---------- MLA ----------
Gimnez, N., Heintz, J., Matera, G., Solernó, P. "Lower complexity bounds for interpolation algorithms" . Journal of Complexity, vol. 27, no. 2, 2011, pp. 151-187.http://dx.doi.org/10.1016/j.jco.2010.10.003
---------- VANCOUVER ----------
Gimnez, N., Heintz, J., Matera, G., Solernó, P. Lower complexity bounds for interpolation algorithms. J. Complexity. 2011;27(2):151-187.http://dx.doi.org/10.1016/j.jco.2010.10.003
