475 research outputs found
Spectral quantities associated to pairs of matrices are hard, when not impossible, to compute and to approximate
No full textCaption title.Includes bibliographical references (p. 9-11).Supported by the ARO. DAAL-03-92-G-0115John N. Tsitsiklis, Vincent D. Blondel
Efficient algorithms for deciding the type of growth of products of integer matrices
No full textFor a given finite set Sigma of matrices with nonnegative integer entries we study the growth with t of max {parallel to A(1)... A(t)parallel to : A(i) epsilon Sigma}.
We show how to determine in polynomial time whether this growth is bounded, polynomial, or exponential, and we characterize all possible behaviors. (c) 2007 Elsevier Inc. All rights reserved
On the complexity of computing the capacity of codes that avoid forbidden difference patterns
No full textSome questions related to the computation of the capacity of codes that avoid forbidden difference patterns are analysed. The maximal number of it-bit sequences whose pairwise differences do not contain some given forbidden difference patterns is known to increase exponentially with n; the coefficient of the exponent is the capacity of the forbidden patterns. In this paper, new inequalities for the capacity are given that allow for the approximation of the capacity with arbitrary high accuracy. The computational cost of the algorithm derived from these inequalities is fixed once the desired accuracy is given. Subsequently, a polynomial time algorithm is given for determining if the capacity of a set is positive while the same problem is shown to be NP-hard when the sets of forbidden patterns are defined over an extended set of symbols. Finally, the existence of extremal norms is proved for any set of matrices arising in the capacity computation. Based on this result, a second capacity approximating algorithm is proposed. The usefulness of this algorithm is illustrated by computing exactly the capacity of particular codes that were only known approximately
Overlap-free words and spectra of matrices
No full textOverlap-free words are words over the binary alphabet A = (a, b} that do not contain factors of the form xvxvx, where x is an element of A and v is an element of A*. We analyze the asymptotic growth of the number u(n) of overlap-free words of length n as n -> infinity. We obtain explicit formulas for the minimal and maximal rates of growth of u(n) in terms of spectral characteristics (the joint spectral subradius and the joint spectral radius) of certain sets of matrices of dimension 20 x 20. Using these descriptions we provide new estimates of the rates of growth that are within 0.4% and 0.03% of their exact values. The best previously known bounds were within 11% and 3%, respectively. We then prove that the value of u(n) actually has the same rate of growth for "almost all" natural numbers n. This average growth is distinct from the maximal and minimal rates and can also be expressed in terms of a spectral quantity (the Lyapunov exponent). We use this expression to estimate it. In order to obtain Our estimates, we introduce new algorithms to compute the spectral characteristics of sets of matrices. These algorithms can be used in other contexts and are of independent interest. (C) 2009 Elsevier B.V. All rights reserved
When is a pair of matrices mortal?
No full textIncludes bibliographical references (p. 6).Supported by the ARO. DAAL-03-92-G-0115Vincent D. Blondel, John N. Tsitsiklis
Complexity of stability and controllability of elementary hybrid systems
No full textCaption title.Includes bibliographical references (p. 16-18).Supported by ARO. DAAL-03-92-G-0115 Supported by NATO. CRG-961115Vincent D. Blondel, John N. Tsitsiklis
Computing the growth of the number of overlap-free words with spectra of matrices
No full textOverlap-free words are words over the alphabet Aâ=âa, b that do not contain factors of the form xvxvx, where xâ âA and vâ âA*. We analyze the asymptotic growth of the number unof overlap-free words of length n. We obtain explicit formulas for the minimal and maximal rates of growth of unin terms of spectral characteristics (the lower spectral radius and the joint spectral radius) of one set of matrices of dimension 20. Using these descriptions we provide estimates of the rates of growth that are within 0.4% and 0.03 % of their exact value. The best previously known bounds were within 11% and 3% respectively. We prove that unactually has the same growth for "almost all" n. This "average" growth is distinct from the maximal and minimal rates and can also be expressed in terms of a spectral quantity (the Lyapunov exponent). We use this expression to estimate it. © 2008 Springer-Verlag Berlin Heidelberg.Overlap-free words are words over the alphabet Aâ=âa, b that do not contain factors of the form xvxvx, where xâ âA and vâ âA*. We analyze the asymptotic growth of the number unof overlap-free words of length n. We obtain explicit formulas for the minimal and maximal rates of growth of unin terms of spectral characteristics (the lower spectral radius and the joint spectral radius) of one set of matrices of dimension 20. Using these descriptions we provide estimates of the rates of growth that are within 0.4% and 0.03 % of their exact value. The best previously known bounds were within 11% and 3% respectively. We prove that unactually has the same growth for "almost all" n. This "average" growth is distinct from the maximal and minimal rates and can also be expressed in terms of a spectral quantity (the Lyapunov exponent). We use this expression to estimate it. © 2008 Springer-Verlag Berlin Heidelberg.Overlap-free words are words over the alphabet Aâ=âa, b that do not contain factors of the form xvxvx, where xâ âA and vâ âA*. We analyze the asymptotic growth of the number unof overlap-free words of length n. We obtain explicit formulas for the minimal and maximal rates of growth of unin terms of spectral characteristics (the lower spectral radius and the joint spectral radius) of one set of matrices of dimension 20. Using these descriptions we provide estimates of the rates of growth that are within 0.4% and 0.03 % of their exact value. The best previously known bounds were within 11% and 3% respectively. We prove that unactually has the same growth for "almost all" n. This "average" growth is distinct from the maximal and minimal rates and can also be expressed in terms of a spectral quantity (the Lyapunov exponent). We use this expression to estimate it. © 2008 Springer-Verlag Berlin Heidelberg
On Krause's Multi-Agent Consensus Model With State-Dependent Connectivity
No full textWe study a model of opinion dynamics introduced by Krause: each agent has an opinion represented by a real number, and updates its opinion by averaging all agent opinions that differ from its own by less than one. We give a new proof of convergence into clusters of agents, with all agents in the same cluster holding the same opinion. We then introduce a particular notion of equilibrium stability and provide lower bounds on the inter-cluster distances at a stable equilibrium. To better understand the behavior of the system when the number of agents is large, we also introduce and study a variant involving a continuum of agents, obtaining partial convergence results and lower bounds on inter-cluster distances, under some mild assumptions
Explicit solutions for root optimization of a polynomial family
No full textGiven a family of real or complex monic polynomials of fixed degree with one fixed affine constraint on their coefficients, consider the problem of minimizing the root radius (largest modulus of the roots) or abscissa (largest real part of the roots). We give constructive methods for finding globally optimal solutions to these problems. In the real case, our methods are based on theorems that extend results in Raymond Chen's 1979 PhD thesis. In the complex case, our methods are based on theorems that are new, easier to state but harder to prove than in the real case. Examples are presented illustrating the results, including several fixed-order controller optimal design problems
- …
