Systems analysis by graphs and matroids. Structural solvability and controllability (Q1092044)

Graph theory, as a branch of combinatorial mathematics has achieved remarkable development in the past several decades, leading to fruitful generalizations and extensions such as network theory and matroid theory. It has become widely recognized that some of the concepts and results in combinatorics serve also as useful mathematical tools for the analysis of engineering systems. This book is a monograph devoted to the study of the structural analysis of systems of linear or nonlinear equations and to that of the structural controllability of linear time-invariant dynamical systems through graph- theoretic models. The major usefulness of the presented theory seems to be oriented to the case of large-scale dynamical systems. The reader will become acquainted with the concepts of matroid theory and its corresponding matroid theoretic approach. This book is of interest to graduate students and researchers. Chapter 1 is devoted to mathematical preliminaries along with conventions. Algebraic concepts concerning algebraic independence and ranks of matrices are introduced. Basic concepts about matroids as pairs of a finite set and a collection of subsets with a set of properties are given along with relevant results in graph theory and matroid theory such as Dulmage-Mendelsohn decomposition of bipartite graphs. The principal partition of submodular functions is mentioned with some emphasis on the algorithmic aspects. In Chapter 2, a graph-theoretic method is developed for the structural analysis of a system of linear/nonlinear equations. In particular, a sound mathematical basis is given to some of the graphical techniques that have been successfully incorporated in some chemical process simulators developed in Japan. In particular examples on: (a) A reactor- separator model, (b) Hydrogen production system of application of the graphical technique are given subsequently. In Chapter 3, graph-theoretic conditions are given to the structural controllability of a linear dynamical system expressed in the descriptor form. Several descriptions of a dynamical system are compared from the viewpoint of structural analysis, especially with reference to the associated natural graph the controllability, which play important roles in connection with the graph-theoretic characterizations of structural controllability, are also given. The structural controllability of a descriptor system is equivalently expressed in terms of the Dulmage- Mendelsohn decomposition of the associated bipartite graph, and some of the known results on structural controllability are derived thereformas corollaries. In Chapter 4, two physical observations are made for providing the physical basis for the more elaborate and faithful mathematical models adopted in the latter half of this book. Firstly, it is explained that two different kinds are to be distinguished among the nonvanishing numbers characterizing real-world systems, and secondly some algebraic implications of the principle of dimensional homogeneity are pointed out. These observations motivate the notions of ``mixed matrix'' and ``physical matrix'' which are introduced as mathematical models of the matrices encountered in real problems, reflecting the dual viewpoint from structural analysis and dimensional analysis. Chapter 5 develops a matroid-theoretic method for the structural analysis of a system of equations. The rank identity theorem is enounced and proved. Then, it is rephrased in combinational terms. By recognizing the combinatorial nature of the rank identity, and efficient algorithm for computing the rank of a mixed matrix is then given. Furthermore, unique block-triangular canonical forms for layered mixed matrices and for mixed matrices are defined which have significant applications to the efficient solution of a system of linear/nonlinear equations. The canonical forms of mixed matrices, bridging the LU-decomposition and the Dulmage- Mendelsohn decomposition, provide a powerful method for the hierarchical decomposition of a system of linear/nonlinear equations into subsystems. Examples of the real world are outlined. Chapter 6 is devoted to the investigation of the structural controllability of a dynamical system by means of matroid-theoretic concepts under the mathematical model established in Chapter 4 from physical observations. The dynamical degree, first introduced in Chapter 3 for descriptor-type systems, is now characterized in connection with the independent-flow problem, which is a polymatroidal extension of the network flow problem, presented together with illustrative references in Chapter 1. Then, the matroidal conditions are derived for the structural controllability followed by a description of the combinatorial algorithm for testing them. Subsequently, some illustrative examples are presented. The Chapter ends with a discussion presenting relations to other works. Finally, the results obtained and the problems left unanswered are summarized in the conclusion.