A probabilistic algorithm to test local algebraic observability in polynomial time

Alexandre Sedoglavic 1, 2
1 ALIEN - Algebra for Digital Identification and Estimation
Inria Lille - Nord Europe, Inria Saclay - Ile de France, Ecole Centrale de Lille, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR8146
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 differential system. Last, we estimate the probability of success of our algorithm and we present some benchmarks from our Maple implementation.
Type de document :
Communication dans un congrès
International Symposium on Symbolic and Algebraic Computation, Jul 2001, London, Ontorio, Canada, 2001
Liste complète des métadonnées

Littérature citée [31 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00126995
Contributeur : Alexandre Sedoglavic <>
Soumis le : samedi 27 janvier 2007 - 11:46:49
Dernière modification le : jeudi 10 mai 2018 - 01:32:24
Document(s) archivé(s) le : mercredi 7 avril 2010 - 02:31:43

Fichier

Sedoglavic2001a.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00126995, version 1

Citation

Alexandre Sedoglavic. A probabilistic algorithm to test local algebraic observability in polynomial time. International Symposium on Symbolic and Algebraic Computation, Jul 2001, London, Ontorio, Canada, 2001. 〈inria-00126995〉

Partager

Métriques

Consultations de la notice

272

Téléchargements de fichiers

171