Search

A nonnegative matrix $A$ is called primitive if $A^k$ is positive for some integer $k>0$. A generalization of this concept to finite sets of matrices is as follows: a set of matrices $\mathcal M = \{A_1, A_2, \ldots, A_m \}$ is primitive if $A_{i_1} A_{i_2} \ldots A_{i_k}$ is positive for some indices $i_1, i_2, ..., i_k$. The concept of primitive sets of matrices comes up in a number of problems within the study of discrete-time switched systems. In this paper, we analyze the computational complexity of deciding if a given set of matrices is primitive and we derive bounds on the length of the shortest positive product. We show that while primitivity is algorithmically decidable, unless $P=NP$ it is not possible to decide primitivity of a matrix set in polynomial time. Moreover, we show that the length of the shortest positive sequence can be superpolynomial in the dimension of the matrices. On the other hand, defining ${\mathcal P}$ to be the set of matrices with no zero rows or columns, we give a simple combinatorial proof of a previously-known characterization of primitivity for matrices in ${\mathcal P}$ which can be tested in polynomial time. This latter observation is related to the well-known 1964 conjecture of Cerny on synchronizing automata; in fact, any bound on the minimal length of a synchronizing word for synchronizing automata immediately translates into a bound on the length of the shortest positive product of a primitive set of matrices in ${\mathcal P}$. In particular, any primitive set of $n \times n$ matrices in ${\mathcal P}$ has a positive product of length $O(n^3)$.

The concept of elementary flux vector is valuable in a number of applications of metabolic engineering. For instance, in metabolic flux analysis, each admissible flux vector can be expressed as a non-negative linear combination of a small number of elementary flux vectors. However a critical issue concerns the total number of elementary flux vectors which may be huge because it combinatorially increases with the size of the metabolic network. In this paper we present a fast algorithm that randomly computes a decomposition of admissible flux vectors in a minimal number of elementary flux vectors without explicitly enumerating all of them.

In this paper, we generalize the notion of persistence, which has been originally introduced for two-dimensional formations, to R^d for d>=3, seeking to provide a theoretical framework for real world applications, which often are in three-dimensional space as opposed to the plane. Persistence captures the desirable property that a formation moves as a cohesive whole when certain agents maintain their distances from certain other agents. We verify that many of the properties of rigid and/or persistent formations established in R^2 are also valid for higher dimensions. Analysing the closed subgraphs and directed paths in persistent graphs, we derive some further properties of persistent formations. We also provide an easily checkable necessary condition for persistence. We then turn our attention to consider some practical issues raised in multi-agent formation control in three-dimensional space. We display a new phenomenon, not present in R^2, whereby subsets of agents can behave in a problematic way. When this behaviour is precluded, we say that the graph depicting the multi-agent formation has structural persistence. In real deployment of controlled multi-agent systems, formations with underlying structurally persistent graphs are of interest. We analyse the characteristics of structurally persistent graphs and provide a streamlined test for structural persistence. We study the connections between the allocation of degrees of freedom (DOFs) across agents and the characteristics of persistence and/or structural persistence of a directed graph. We also show how to transfer DOFs among agents, when the formation changes with new agent(s) added, to preserve persistence and/or structural persistence.

During recent years, it has been shown that a number of problems in matrix theory are NP-hard, including robust nonsingularity, robust stability, robust positive semidefiniteness, robust bounded norm, state feedback stabilization with structural and norm constraints, etc. In this paper, we use standard bounds on empirical probabilities as well as recent results from statistical learning theory on the VC-dimension of families of sets defined by a finite number of polynomial inequalities, to show that for each of the above problems, as well as for still more general and more difficult problems, there exists a polynomial-time randomized algorithm that can provide a yes or no answer to arbitrarily small levels of accuracy and confidence.

The purpose of this paper is twofold: (a) to provide a tutorial introduction to some key concepts from the theory of computational complexity, highlighting their relevance to systems and control theory, and (b) to survey the relatively recent research activity lying at the interface between these fields. We begin with a brief introduction to models of computation, the concepts of undecidability, polynomial-time algorithms, NP-completeness, and the implications of intractability results. We then survey a number of problems that arise in systems and control theory, some of them classical, some of them related to current research. We discuss them from the point of view of computational complexity and also point out many open problems. In particular, we consider problems related to stability or stabilizability of linear systems with parametric uncertainty, robust control, time-varying linear systems, nonlinear and hybrid systems, and stochastic optimal control.

In this paper, we consider simple classes of nonlinear systems and prove that basic questions related to their stability and controllability are either undecidable or computationally intractable (NP-hard). As a special case, we consider a class of hybrid systems in which the state space is partitioned into two halfspaces, and the dynamics in each halfspace correspond to a different linear system.

The classical polynomial approach to pole placement involves the computation of a particular solution of a given Diophantine equation. The solution corresponds to a proper controller whose order is fixed by the number of nonminimum phase zeros of the plant transfer function, by its order, and by the desired closed-loop characteristic polynomial. This controller might be unstable for some desired closed-loop characteristic polynomials, even though the plant can be stabilized by a stable controller. Now, unstable controllers are known to deteriorate closed-loop system performances, compared with stable ones. Hence, we propose a procedure to build, for a specific class of plants, a stable pole placement controller when the classical pole placement controller is unstable. The properties of both stable and unstable controllers are compared via simulations. It appears that, for the considered plants, the stable controller improves at least one of the following properties, compared with its unstable counterpart: step response transient, gain margin, measurement noise rejection. The results obtained with our procedure are also compared with the results obtained via Middleton's approach, which consists in modifying the desired closed-loop poles so as to obtain a stable and minimum phase controller with the classical pole placement method. Finally, our pole placement design with stable controller is applied to solve a particular simultaneous partial pole placement problem.

We propose a simple test for checking strong stabilizability. The test necessitates the construction of a single Routh table.