Minimal Controllability Problems on Linear Structural Descriptor Systems

• 成果类型: Article
• 署名作者: Terasaki, Shun; Sato, Kazuhiro
• 署名单位: University of Tokyo
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2021.3079359
• 发表日期: 2022
• 页码: 2522-2528
• 关键词: Controllability; Linear systems; Directed graphs; bipartite graph; time complexity; NP-hard problem; indexes; descriptor system; Dulmage-Mendelsohn (DM) decomposition; Large-scale system; structural controllability

摘要

We consider minimal controllability problems (MCPs) on linear structural descriptor systems. We address two problems of determining the minimum number of input nodes such that a descriptor system is structurally controllable. We show that MCP0 for structural descriptor systems can be solved in polynomial time. This is the same as the existing results on typical structural linear time-invariant (LTI) systems. However, the derivation of the result is considerably different because the derivation technique of the existing result cannot be used for descriptor systems. Instead, we use the Dulmage-Mendelsohn decomposition. Moreover, we prove that the results for MCP1 are different from those for usual LTI systems. In fact, MCP1 for descriptor systems is an NP-hard problem, while MCP1 for LTI systems can be solved in polynomial time.