Geodesic
Characterization of generic properties of linear structured systems for efficient computations
Kybernetika, Tome 38 (2002) no. 5, pp. 503-520 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

In this paper we investigate some of the computational aspects of generic properties of linear structured systems. In such systems only the zero/nonzero pattern of the system matrices is assumed to be known. For structured systems a number of characterizations of so-called generic properties have been obtained in the literature. The characterizations often have been presented by means of the graph associated to a linear structured system and are then expressed in terms of the maximal or minimal number of certain type of vertices contained in a combination of specific paths. In this paper we give new graph theoretic characterizations of structural invariants of structured systems. It turns out that these new characterizations allow to compute these invariants via standard and efficient algorithms from combinatorial optimization.
In this paper we investigate some of the computational aspects of generic properties of linear structured systems. In such systems only the zero/nonzero pattern of the system matrices is assumed to be known. For structured systems a number of characterizations of so-called generic properties have been obtained in the literature. The characterizations often have been presented by means of the graph associated to a linear structured system and are then expressed in terms of the maximal or minimal number of certain type of vertices contained in a combination of specific paths. In this paper we give new graph theoretic characterizations of structural invariants of structured systems. It turns out that these new characterizations allow to compute these invariants via standard and efficient algorithms from combinatorial optimization.
Classification : 93B10, 93B40, 93C05, 94C15
Keywords: linear structured system; graph theoretic characterizations of structural invariants 
@article{KYB_2002_38_5_a1,
     author = {Commault, Christian and Dion, Jean-Michel and van der Woude, Jacob W.},
     title = {Characterization of generic properties of linear structured systems for efficient computations},
     journal = {Kybernetika},
     pages = {503--520},
     year = {2002},
     volume = {38},
     number = {5},
     mrnumber = {1966942},
     zbl = {1265.93120},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2002_38_5_a1/}
}
TY  - JOUR
AU  - Commault, Christian
AU  - Dion, Jean-Michel
AU  - van der Woude, Jacob W.
TI  - Characterization of generic properties of linear structured systems for efficient computations
JO  - Kybernetika
PY  - 2002
SP  - 503
EP  - 520
VL  - 38
IS  - 5
UR  - http://geodesic.mathdoc.fr/item/KYB_2002_38_5_a1/
LA  - en
ID  - KYB_2002_38_5_a1
ER  - 
%0 Journal Article
%A Commault, Christian
%A Dion, Jean-Michel
%A van der Woude, Jacob W.
%T Characterization of generic properties of linear structured systems for efficient computations
%J Kybernetika
%D 2002
%P 503-520
%V 38
%N 5
%U http://geodesic.mathdoc.fr/item/KYB_2002_38_5_a1/
%G en
%F KYB_2002_38_5_a1
Commault, Christian; Dion, Jean-Michel; van der Woude, Jacob W. Characterization of generic properties of linear structured systems for efficient computations. Kybernetika, Tome 38 (2002) no. 5, pp. 503-520. http://geodesic.mathdoc.fr/item/KYB_2002_38_5_a1/

[1] Commault C., Dion J. M., Perez A.: Disturbance rejection for structured systems. IEEE Trans. Automat. Control AC-36 (1991), 884–887 | DOI | MR | Zbl

[2] Descusse J., Dion J. M.: On the structure at infinity of linear square decouplable systems. IEEE Trans. Automat. Control AC-27 (1982), 971–974 | DOI | MR

[3] Dion J. M., Commault C.: Smith–McMillan factorisations at infinity of rational matrix functions and their control interpretation. Systems Control Lett. 1 (1982), 312–320 | DOI | MR

[4] Dion J. M., Commault C.: Feedback decoupling of structured systems. IEEE Trans. Automat. Control AC-38 (1993), 1132–1135 | DOI | MR | Zbl

[5] Dion J. M., Commault, C., Montoya J.: Simultaneous decoupling and disturbance rejection – a structural approach. Internat. J. Control 59 (1994), 1325–1344 | DOI | MR | Zbl

[6] Glover K., Silverman L. M.: Characterization of structural controllability. IEEE Trans. Automat. Control AC-21 (1976), 534–537 | DOI | MR | Zbl

[7] Gondran M., Minoux M.: Graphs and Algorithms. Wiley, New York 1984 | MR | Zbl

[8] Hopcroft J. E., Karp R. M.: An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2 (1973), 225–231 | DOI | MR

[9] Hosoe S.: Determination of generic dimensions of controllable subspaces and applications. IEEE Trans. Automat. Control AC-25 (1980), 1192–1196 | DOI | MR

[10] Hovelaque V.: Analyse Structurelle, Géométrique, et Graphique des Systèmes Linéaires Structurés, Thèse de Doctorat. Inst. Nat. Polytechnique de Grenoble 1997

[11] Hovelaque V., Commault, C., Dion J. M.: Analysis of linear structured systems using a primal-dual algorithm. Systems Control Lett. 27 (1996), 73–85 | DOI | MR | Zbl

[12] Hovelaque V., Commault, C., Dion J. M.: Disturbance decoupling for linear structured systems via a primal-dual algorithm. Comp. Engrg. Syst. Appl. IMACS Lille (1996), 455–459

[13] Hovelaque V., Djidi N., Commault, C., Dion J. M.: Decoupling problem for structured systems via a primal-dual algorithm. In: Proc. European Control Conference (ECC97), Brussels 1997

[14] Kuhn H. W.: The Hungarian method for the assignment problem. Nav. Res. Log. Quat. 2 (1955), 83–97 | DOI | MR | Zbl

[15] Lin C. T.: Structural controllability. IEEE Trans. Automat. Control AC-19 (1974), 201–208 | DOI | MR | Zbl

[16] Linnemann A.: Decoupling of structured systems. Systems Control Lett. 1 (1981), 79–86 | DOI | MR | Zbl

[17] Murota K.: System analysis by graphs and matroids, Algorithms and Combinatorics. Springer–Verlag, New York 1987 | MR

[18] Reinschke K. J.: Multivariable Control: A Graph–heoretic Approach. Springer–Verlag, New York 1988 | MR

[19] Röbenack K., Reinschke K. J.: Digraph based determination of Jordan block size structure of singular matrix pencils. Linear Algebra Appl. 275–276 (1998), 495–507 | MR | Zbl

[20] Schizas C., Evans F. J.: A graph theoretic approach to multivariable control system design. Automatica 17 (1981), 371–377 | DOI | Zbl

[21] Shields R. W., Pearson J. B.: Structural controllability of multi-input linear systems. IEEE Trans. Automat. Control AC-21 (1976), 203–212 | DOI | MR

[22] Söte W.: Eine graphische Methode zur Ermittlung der Nullstellen in Mehrgrössensystemen. Reglungstechnik 28 (1980), 346–348 | Zbl

[23] Suda N., Wan, B., Ueno I.: The orders of infinite zeros of structured systems. Trans. Soc. Instr. Control Engineers 25 (1989), 346–348

[24] Woude J. W. van der: On the structure at infinity of a structured system. Linear Algebra Appl. 148 (1991), 145–169 | MR

[25] Woude J. W. van der: The generic number of invariant zeros of a structured linear system. SIAM J. Control Optim. 38 (2000), 1, 1–21 | DOI | MR

[26] Woude J. W. van der: The generic canonical form of a regular structured matrix pencil. Linear Algebra Appl. 353 (2002), 267–288 | MR

[27] Woude J. W. van der, Commault, C., Dion J. M.: Invariants for linear structured systems. Internal report of the Laboratoire d’Automatique de Grenoble 2000

[28] Yamada T.: A network flow algorithm to find an elementary I/O matching. Networks 18 (1988), 105–109 | DOI | MR | Zbl