Artículo

Artículo de Acceso Abierto. Puede ser descargado en su versión final
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We prove upper bounds on the order and degree of the polynomials involved in a resolvent representation of the prime differential ideal associated with a polynomial differential system for a particular class of ordinary first order algebraic-differential equations arising in control theory. We also exhibit a probabilistic algorithm which computes this resolvent representation within time polynomial in the natural syntactic parameters and the degree of a certain algebraic variety related to the input system. In addition, we give a probabilistic polynomial-time algorithm for the computation of the differential Hilbert function of the ideal. © 2005 Elsevier Inc. All rights reserved.

Registro:

Documento: Artículo
Título:On the complexity of the resolvent representation of some prime differential ideals
Autor:D'Alfonso, L.; Jeronimo, G.; Solernó, P.
Filiación:Departamento de Matemática, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Ciudad Universitaria, 1428 Buenos Aires, Argentina
Palabras clave:Differential algebra; Differential Hilbert function; Elimination theory; Probabilistic algorithms; Resolvent representation; Straight-line programs; Algorithms; Computation theory; Differential equations; Functions; Polynomials; Probabilistic logics; Differential algebra; Differential Hilbert function; Elimination theory; Resolvent representation; Straight-line programs; Computational complexity
Año:2006
Volumen:22
Número:3
Página de inicio:396
Página de fin:430
DOI: http://dx.doi.org/10.1016/j.jco.2005.10.002
Handle:http://hdl.handle.net/20.500.12110/paper_0885064X_v22_n3_p396_DAlfonso
Título revista:Journal of Complexity
Título revista abreviado:J. Complexity
ISSN:0885064X
PDF:https://bibliotecadigital.exactas.uba.ar/download/paper/paper_0885064X_v22_n3_p396_DAlfonso.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0885064X_v22_n3_p396_DAlfonso

Referencias:

  • Bini, D., Pan, V.Y., (1994) Polynomial and Matrix Computations, Fundamental Algorithms, Progress in Theoretical Computer Science, , Birkhäuser, Boston, MA
  • Cluzeau, T., Hubert, E., Resolvent representation for regular differential ideals (2003) AAECC, 13, pp. 395-425
  • Diop, S., Fliess, M., On nonlinear observability (1991) Proceedings of the European Control Conference, pp. 152-157. , Commault C., Normand-Cyrot D., Dion J.M., Dugard L., Fliess M., Titli A., Cohen G., Benveniste A., and Landau I.D. (Eds). vol. 1, Hermès, Paris
  • von zur Gathen, J., Gerhard, J., (1999) Modern Computer Algebra, , Cambridge University Press, New York
  • Giusti, M., Hägele, K., Heintz, J., Montaña, J.L., Morais, J.E., Pardo, L.M., Lower bounds for diophantine approximation (1997) J. Pure Appl. Algebra, 117-118, pp. 277-317
  • Giusti, M., Lecerf, G., Salvy, B., A Gröbner free alternative for polynomial system solving (2001) J. Complexity, 17 (1), pp. 154-211
  • Heintz, J., Definability and fast quantifier elimination in algebraically closed fields (1983) Theoret. Comput. Sci., 24 (3), pp. 239-277
  • Heintz, J., Krick, T., Puddu, S., Sabia, J., Waissbein, A., Deformation techniques for efficient polynomial equation solving (2000) J. Complexity, 16 (1), pp. 70-109
  • Heintz, J., Matera, G., Waissbein, A., On the time-space complexity of geometric elimination procedures (2001) Appl. Algebra Eng. Comm. Comput., 11 (4), pp. 239-296
  • Hubert, E., Notes on triangular sets and triangulation decomposition algorithms II: differential systems (2003) Lecture Notes in Computer Science, 2630, pp. 40-87. , Langer U., and Winkler F. (Eds), Springer, Berlin
  • Kolchin, E.R., (1973) Differential Algebra and Algebraic Groups, , Academic Press, New York
  • Krick, T., Pardo, L.M., A computational method for Diophantine approximation (1996) Progr. Math., 143, pp. 193-254
  • Krick, T., Pardo, L.M., Sombra, M., Sharp estimates for the arithmetic Nullstellensatz (2001) Duke Math. J., 109 (3), pp. 521-598
  • Kronecker, L., Grundzüge einer arithmetischen Theorie der algebraischen Grössen (1882) J. Reine Angew. Math., 92, pp. 1-122
  • Kunz, E., (1985) Introduction to Commutative Algebra and Algebraic Geometry, , Birkhäuser, Boston, MA
  • Matera, G., Sedoglavic, A., Fast computation of discrete invariants associated to a differential rational mapping (2003) J. Symbolic Comput., 36 (3-4), pp. 473-499
  • Ritt, J.F., Differential equations from the algebraic standpoint (1932) Amer. Math. Soc. Colloq. Publ., 14
  • Ritt, J.F., Differential algebra (1950) Amer. Math. Soc. Colloq. Publ., 33
  • Sadik, B., A bound for the order of characteristic set elements of an ordinary prime differential ideal and some applications (2000) Appl. Algebra Eng. Comm. Comput., 10 (3), pp. 251-268
  • Schost, E., Computing parametric geometric resolutions (2003) Appl. Algebra Eng. Comm. Comput., 13 (5), pp. 349-393
  • Schwartz, J.T., Fast probabilistic algorithms for verification of polynomial identities (1980) J. ACM, 27, pp. 701-717
  • Sedoglavic, A., A probabilistic algorithm to test local algebraic observability in polynomial time, Computer algebra (London, ON, 2001) (2002) J. Symbolic Comput., 33 (5), pp. 735-755
  • Seidenberg, A., Some basic theorems in differential algebra (characteristic p arbitrary) (1952) Trans. Amer. Math. Soc., 73, pp. 174-190;

Citas:

---------- APA ----------
D'Alfonso, L., Jeronimo, G. & Solernó, P. (2006) . On the complexity of the resolvent representation of some prime differential ideals. Journal of Complexity, 22(3), 396-430.
http://dx.doi.org/10.1016/j.jco.2005.10.002
---------- CHICAGO ----------
D'Alfonso, L., Jeronimo, G., Solernó, P. "On the complexity of the resolvent representation of some prime differential ideals" . Journal of Complexity 22, no. 3 (2006) : 396-430.
http://dx.doi.org/10.1016/j.jco.2005.10.002
---------- MLA ----------
D'Alfonso, L., Jeronimo, G., Solernó, P. "On the complexity of the resolvent representation of some prime differential ideals" . Journal of Complexity, vol. 22, no. 3, 2006, pp. 396-430.
http://dx.doi.org/10.1016/j.jco.2005.10.002
---------- VANCOUVER ----------
D'Alfonso, L., Jeronimo, G., Solernó, P. On the complexity of the resolvent representation of some prime differential ideals. J. Complexity. 2006;22(3):396-430.
http://dx.doi.org/10.1016/j.jco.2005.10.002