A probabilistic algorithm to test local algebraic observability in polynomial time

ABSTRACT

The following questions are often encountered in system and control theory. Given an algebraic model of a physical process, which variables can be, in theory, deduced from the input-output behavior of an experiment? How many of the remaining variables should we assume to be known in order to determine all the others? These questions are parts of the local algebraic observability problem which is concerned with the existence of a non trivial Lie subalgebra of the symmetries of the model letting the inputs and the outputs invariant.

We present a probabilistic seminumerical algorithm that proposes a solution to this problem in polynomial time. A bound for the necessary number of arithmetic operations on the rational field is presented. This bound is polynomial in the complexity of evaluation of the model and in the number of variables. Furthermore, we show that the size of the integers involved in the computations is polynomial in the number of variables and in the degree of the system. Last, we estimate the probability of success of our algorithm.

REFERENCES

• 1: BAUR, W., AND STRASSEN, V. The complexity of partial derivatives. Theoretical Computer Science 22, 3 (1983), 317-330.
• 2: BOULIER, F. Efficient computation of regular differential systems by change of rankings using Kihler differentials. Preprint LIFL 1999-14, Dec. 1999.
• 3: F. Boulier , D. Lazard , F. Ollivier , M. Petitot, Representation for the radical of a finitely generated differential ideal, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.158-166, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220367]
• 4: R. P. Brent , H. T. Kung, Fast Algorithms for Manipulating Formal Power Series, Journal of the ACM (JACM), v.25 n.4, p.581-595, Oct. 1978 [doi>10.1145/322092.322099]
• 5: BORGISSER, P., CLAUSEN, M., AND SHOKROLLAHI, M. A. Algebraic Complexity Theory, vol. 315 of Grundlehren der Mathematischen Wissenschaften. Springer, 1997.
• 6: D. Castro , L. M. Pardo , K. Hägele , J. E. Morais, Kronecker's and Newton's approaches to solving: a first comparison, Journal of Complexity, v.17 n.1, p.212-303, March 1, 2001 [doi>10.1006/jcom.2000.0572]
• 7: DIOP, S., AND FLIESS, M. On nonlinear observability. In Proceedings of First European Control Conference (Grenoble, France, July 2-5 1991), C. Commault and coll., Eds., vol. 1, Hermes, pp. 152-157.
• 8: EISENBUD, D. Commutative Algebra with a View Toward Algebraic Geometry. No. 150 in Graduate Texts ia Mathematics. Springer, 1994.
• 9: FLIESS, M. Automatique et corps diffrentiels. Forum Mahematicum 1, 3 (1989), 227-238.
• 10: GALLO, G., AND MISHRA, B. Efficient algorithms and bounds for Wu-Ritt characteristic sets. In Effective methods in algebraic geometry (proceedings of MEGA '90) (Livorno, Italy, Apr. 17-21 1991), F. Mora and C. Traverso, Eds., vol. 94 of Progress in Mathematics, Birkhiuser, pp. 119-142.
• 11: Keith O. Geddes, Convergence behavior of the Newton iteration for first order differential equations, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.189-199, June 01, 1979
• 12: Marc Giusti , Grégoire Lecerf , Bruno Salvy, A Gröbner free alternative for polynomial system solving, Journal of Complexity, v.17 n.1, p.154-211, March 1, 2001 [doi>10.1006/jcom.2000.0571]
• 13: GOLDIETER, A. A model for circadian oscillations in the Drosophila period protein. Proceedings of the Royal Society London B, 261 (1995), 319-324.
• 14: HERMANN, P., AND KRENER, A. J. Nonlinear controllability and observability. IEEE Transactions on Automatic Control AC-22, 5 (1977), 728-740.
• 15: Evelyne Hubert, Factorization-free decomposition algorithms in differential algebra, Journal of Symbolic Computation, v.29 n.4-5, p.641-662, April/May 2000 [doi>10.1006/jsco.1999.0344]
• 16: Alberto Isidori, Nonlinear control systems: an introduction (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1989
• 17: JOHNSON, J. Kihler differentials and differential algebra. Annals of Mathematics 89 (1969), 92-98.
• 18: KALMAN, R. On the general theory of control systems. In Proceedings of the first international congress on automatic control (Moscow, SSSR, 1961), vol. 1, Butterworths, London, pp. 481-492.
• 19: KALTOFEN, E. Computational differentiation and algebraic complexity theory. In Workshop Report on First Theory Institute on Computational Differentiation (Argonne, Illinois, Dec. 1993), C. H. Bischo, A. Griewank, and P. M. Khademi, Eds., pp. 28-30. vol. ANL/MCS-TM-183 of Tech. Rep. Argonne National Laboratory.
• 20: KOLCHIN, E. R. Differential Algebra and Algebraic Groups. Academic Press, New York, 1973.
• 21: Lennart Ljung, System identification (2nd ed.): theory for the user, Prentice Hall PTR, Upper Saddle River, NJ, 1999
• 22: LJUNG, L., AND GLAD, T. Parametrization of nonlinear model structures as linear regressions. In 11th IFAC Word Congress (Tellin, Estonia, Aug. 1990), pp. 67-71.
• 23: Lennart Ljung , Torkel Glad, On global identifiability for arbitrary model parametrizations, Automatica (Journal of IFAC), v.30 n.2, p.265-276, Feb. 1994 [doi>10.1016/0005-1098(94)90029-9]
• 24: NOIRET, C. Utilisation du ealcul formel pour l'identifiabilitg de modules paramdtriques et nouveaux algorithmes en estimation de paramOtres. PAD thesis, Universit de technologie de Compiegne, Dec. 2000.
• 25: OLLIVIER, F. Le problme de l'identifiabilitd structurelle globalc: approche thdorique, mdthodes effectives et bornes de complexitd. PhD thesis, Icole polytechnique, June 1990.
• 26: POHJANPALO, H. System identifiability based on the power series expansion of the solution. Mathematical Bioseiences 41, 1-2 (1978), 21-33.
• 27: R.ITT, J. F. Differential Algebra. Dover Publications, 1966.
• 28: SADIK, B. A bound for the order of characteristic set elements of an ordinary prime differential ideal and some applications. Applicable Algebra in Engineering Communications and Computing 10, 3 (Mar. 2000), 251-268.
• 29: SCHOST, E. Sur la rdsolution des systmes polynomiaux 5 paramtres. PhD thesis, Ecole polytechnique, Dec. 2000.
• 30: VAJDA, S., GODFREY, K. R., AND IABITZ, H. Similarity transformation approach to identifiability analysis of non linear comportemental models. Mathematical Bioseiences 93, 2 (1989), 217-248.
• 31: Joachim von zur Gathen , Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, NY, 1999
• 32: WALTER, E. ldentifiability of State Space Model, vol. 46 of Lectures Notes in Biomathematics. Springer, New York, 1982.
• 33: ZIPPEL, R. Effective Polynomial Computation. Kluwer Academic Publishers, 1993.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation
      F.1.3 Complexity Measures and Classes

General Terms:
Algorithms, Performance, Theory, Verification

Keywords:
identifiability, observability, seminumerical algorithm