Characterization of generic properties of linear structured systems for efficient computations. (English) Zbl 1265.93120
Summary: 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.
MSC:
| 93C05 | Linear systems in control theory |
| 94C15 | Applications of graph theory to circuits and networks |
References:
| [1] | Commault C., Dion J. M., Perez A.: Disturbance rejection for structured systems. IEEE Trans. Automat. Control AC-36 (1991), 884-887 · Zbl 0754.93023 · doi:10.1109/9.85072 |
| [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 · Zbl 0485.93042 · doi:10.1109/TAC.1982.1103041 |
| [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 · Zbl 0493.93014 · doi:10.1016/S0167-6911(82)80029-7 |
| [4] | Dion J. M., Commault C.: Feedback decoupling of structured systems. IEEE Trans. Automat. Control AC-38 (1993), 1132-1135 · Zbl 0800.93470 · doi:10.1109/9.231471 |
| [5] | Dion J. M., Commault, C., Montoya J.: Simultaneous decoupling and disturbance rejection - a structural approach. Internat. J. Control 59 (1994), 1325-1344 · Zbl 0800.93477 · doi:10.1080/00207179408923133 |
| [6] | Glover K., Silverman L. M.: Characterization of structural controllability. IEEE Trans. Automat. Control AC-21 (1976), 534-537 · Zbl 0332.93012 · doi:10.1109/TAC.1976.1101257 |
| [7] | Gondran M., Minoux M.: Graphs and Algorithms. Wiley, New York 1984 · Zbl 1172.05001 |
| [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 · Zbl 0266.05114 · doi:10.1137/0202019 |
| [9] | Hosoe S.: Determination of generic dimensions of controllable subspaces and applications. IEEE Trans. Automat. Control AC-25 (1980), 1192-1196 · Zbl 0483.93017 · doi:10.1109/TAC.1980.1102506 |
| [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 · Zbl 0875.93117 · doi:10.1016/0167-6911(95)00039-9 |
| [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 · Zbl 0875.93117 |
| [13] | Hovelaque V., Djidi N., Commault, C., Dion J. M.: Decoupling problem for structured systems via a primal-dual algorithm. Proc. European Control Conference (ECC97), Brussels 1997 · Zbl 0878.93015 |
| [14] | Kuhn H. W.: The Hungarian method for the assignment problem. Nav. Res. Log. Quat. 2 (1955), 83-97 · Zbl 0143.41905 · doi:10.1002/nav.3800020109 |
| [15] | Lin C. T.: Structural controllability. IEEE Trans. Automat. Control AC-19 (1974), 201-208 · Zbl 0343.93009 · doi:10.1109/TAC.1974.1100557 |
| [16] | Linnemann A.: Decoupling of structured systems. Systems Control Lett. 1 (1981), 79-86 · Zbl 0475.93049 · doi:10.1016/S0167-6911(81)80040-0 |
| [17] | Murota K.: System analysis by graphs and matroids, Algorithms and Combinatorics. Springer-Verlag, New York 1987 · Zbl 0624.05001 |
| [18] | Reinschke K. J.: Multivariable Control: A Graph-heoretic Approach. Springer-Verlag, New York 1988 · Zbl 0682.93006 |
| [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 · Zbl 0934.15012 · doi:10.1016/S0024-3795(97)10023-4 |
| [20] | Schizas C., Evans F. J.: A graph theoretic approach to multivariable control system design. Automatica 17 (1981), 371-377 · Zbl 0476.93041 · doi:10.1016/0005-1098(81)90054-6 |
| [21] | Shields R. W., Pearson J. B.: Structural controllability of multi-input linear systems. IEEE Trans. Automat. Control AC-21 (1976), 203-212 · Zbl 0324.93007 · doi:10.1109/TAC.1976.1101198 |
| [22] | Söte W.: Eine graphische Methode zur Ermittlung der Nullstellen in Mehrgrössensystemen. Reglungstechnik 28 (1980), 346-348 · Zbl 0459.93027 |
| [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 · Zbl 0724.93019 · doi:10.1016/0024-3795(91)90091-A |
| [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 · Zbl 0952.93056 · doi:10.1137/S0363012996310119 |
| [26] | Woude J. W. van der: The generic canonical form of a regular structured matrix pencil. Linear Algebra Appl. 353 (2002), 267-288 · Zbl 1055.15019 · doi:10.1016/S0024-3795(02)00315-4 |
| [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 · Zbl 1023.93002 |
| [28] | Yamada T.: A network flow algorithm to find an elementary I/O matching. Networks 18 (1988), 105-109 · Zbl 0641.90039 · doi:10.1002/net.3230180203 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
