Complexity of checking the existence of a stabilizing decentralized controller
- Creators
- Lavaei, Javad
- Sojoudi, Somayeh
Abstract
Given an interconnected system, this paper is concerned with the time complexity of verifying if any given unrepeated mode of the system is a decentralized fixed mode (DFM). It is shown that checking the decentralized fixedness of any distinct mode is tantamount to testing the strong connectivity of a digraph formed based on the system. It is subsequently proved that the time complexity of this decision problem using the proposed approach is the same as the complexity of matrix multiplication. This work concludes that the identification of distinct decentralized fixed modes (by means of a deterministic algorithm, rather than a randomized one) is computationally very easy, although the existing algorithms for solving this problem would wrongly imply that it is cumbersome. This paper provides not only a complexity analysis, but also an efficient algorithm for tackling the underlying problem.
Additional Information
© 2009 AACC. This work has been supported by AFOSR and Air Force MURI.Attached Files
Published - Lavaei2009p80112009_American_Control_Conference_Vols_1-9.pdf
Files
Name | Size | Download all |
---|---|---|
md5:955b9719f828c0285f95183ba08b1ffc
|
553.5 kB | Preview Download |
Additional details
- Eprint ID
- 18189
- Resolver ID
- CaltechAUTHORS:20100507-095228368
- Air Force Office of Scientific Research (AFOSR)
- Air Force Multi University Research Initiative (MURI)
- Created
-
2010-05-16Created from EPrint's datestamp field
- Updated
-
2021-11-08Created from EPrint's last_modified field