Alexander Weber,
Gunther Reissig,
Ferdinand Svaricek.
A linear time algorithm to verify strong structural controllability.
Proc. 53rd IEEE Conf. Decision and Control (CDC),
Los Angeles, CA, U.S.A.,
15-17 Dec. 2014, pp. 5574-5580.
Full text.
(Definitive publication; restricted access.)
Full text.
(Free access.)
Abstract:
We prove that strong structural controllability of a
pair of structural matrices (A,B) can be verified in time linear
in n+r+v, where A is square, n and r denote the number of
columns of A and B, respectively, and v is the number of nonzero
entries in (A,B). We also present an algorithm realizing
this bound, which depends on a recent, high-level method to
verify strong structural controllability and uses sparse matrix
data structures. Linear time complexity is actually achieved
by separately storing both the structural matrix (A,B) and its
transpose, linking the two data structures through a third one,
and a novel, efficient scheme to update all the data during the
computations. We illustrate the performance of our algorithm
using systems of various sizes and sparsity.
BibTeX entry:
@InProceedings{WeberReissigSvaricek14,
author = {Alexander Weber and Gunther Reissig and Ferdinand Svaricek},
title = {A linear time algorithm to verify strong structural controllability},
booktitle = {Proc. 53nd IEEE Conf. Decision and Control (CDC), Los Angeles, CA, U.S.A., 15-17 } # dec # { 2014},
pages = {5574-5580},
year = {2014},
address = {New York},
publisher = {IEEE}
doi = {10.1109/CDC.2014.7040261},
eprint = {1412.6792}
}
Impressum und Haftungsausschluß