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.
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