PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Parallel Digraphs-building Computer Algorithm for Finding a Set of Characteristic Polynomial Realisations of Dynamic System

Treść / Zawartość
Identyfikatory
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
This paper presents in-depth the parallel computer algorithm for the determination of characteristic polynomial realisations of dynamic system. The main differences between the depicted method and other state of- the-art solutions include finding not few realisations, but a whole set, and the fact that the found realisations are always minimal among all possible. As digraphsbuilding methods used in the algorithm are NP-complete or NP-hard problems, the algorithm is paralleled and GPGPU (General-Purpose computing on Graphics Processor Units) computation is proposed as the only feasible solution. The article describes in detail the proposed method, discusses it’s complexity, presents optimisation solutions and still open problems. The working algorithm is illustrated with a numerical example and compared to results of other known methods.
Twórcy
autor
  • Faculty of Electrical Engineering, Warsaw University of Technology, Koszykowa 75, 00-662 Warsaw, Poland
  • Faculty of Electrical Engineering, Warsaw University of Technology, Koszykowa 75, 00-662 Warsaw, Poland, www: http://nas.isep.pw.edu.pl.
Bibliografia
  • [1] J. Bang-Jensen, G. Gutin, Digraphs: Theory, Algorithms and Applications (2nd Edition), Springer-Verlag: London, 2009.
  • [2] L. Benvenuti, L. Farina, “A tutorial on the positive realization problem”, IEEE Transactions on Automatic Control, vol. 49, no. 5, 2004, 651–664.
  • [3] A. Berman, M. Neumann, R. J. Stern, Nonnegative Matrices in Dynamic Systems, Wiley: New York, 1989.
  • [4] M. Bisiacco, E. Fornasini, G. Marchesini, “Dynamic regulation of 2D systems: A state-space approach”, Linear Algebra and Its Applications, vol. 122–124, 1989, 195–218.
  • [5] T. Blyth, E. Robertson, Basic Linear Algebra (2nd Edition), Springer: London, 2002.
  • [6] M. Bona, Combinatorics of Permutations(Second Edition), Chapman Hall, CRC Press, 2012.
  • [7] R. Bru, C. Coll, S. Romero, E. Sanchez, “Reachability indices of positive linear systems”, Electronic Journal of Linear Algebra, vol. 11, 2004, 88–102.
  • [8] R. Bru, S. Romero-Vivo, E. Sanchez, “Reachability indices od periodic positive systems via positive shift-similarity”, Linear Algebra and Its Applications, vol. 429, 2008, 1288–1301.
  • [9] E. Fornasini, G. Marchesini, “State-space realization theory of two-dimensional filters”, IEEE Trans, Autom. Contr., vol. 21, 1976, 481–491.
  • [10] E. Fornasini, M. E. Valcher, “Directed graphs, 2D state models, and characteristic polynomials of irreducible matrix pairs”, Linear Algebra and Its Applications, vol. 263, 1997, 275–310.
  • [11] E. Fornasini, M. E. Valcher, “On the positive reachability of 2D positive systems”, LCNIS, 2003, 297–304.
  • [12] E. Fornasini, M. E. Valcher, “Controllability and reachability of 2D positive systems: a graph theoretic approach”, IEEE Transaction on Circuits and Systems I, no. 52, 2005, 576–585.
  • [13] L. R. Foulds, Graph Theory Applications, Springer Verlag, 1991.
  • [14] C. Godsil, G. Royle, Algebraic Graph Theory, Springer Verlag, 2001.
  • [15] S. Hong, T. Oguntebi, K. Olukotun, “Ef􀏐icient parallel graph exploration on multi-core CPU and GPU”. In: Parallel Architectures and Compilation Techniques (PACT), 2011 International Conference on, 2011, 78–88.
  • [16] R. A. Horn, C. R. Johnson, Topics in Matrix Analysis, Cambridge Univ. Press, 1991.
  • [17] K. Hryniów, “Parallel pattern mining on Graphics Processing Units”. In: Proceedings of 2013 14th International Carpathian Control Conference (ICCC), 2013, 134–139.
  • [18] K. Hryniów, K. A. Markowski, “Conditions for digraphs representation of the characteristic polynomial”. In: Young Scientists Towards the Challenges of Modern Technology, 2014, 77–80.
  • [19] K. Hryniów, K. A. Markowski, “Parallel digraphsbuilding algorithm for polynomial realisations”. In: Proceedings of 2014 15th International Carpathian Control Conference (ICCC), 2014, 174–179.
  • [20] K. Hryniów, K. A. Markowski, “Reachability index calculation by parallel digraphs-building”. In: 19th International Conference on Methods and Models in Automation and Robotics (MMAR), Miedzyzdroje, Poland, September 2-5, 2014, 2014, 808–813.
  • [21] K. Hryniów, K. A. Markowski, “Digraphs-building of complete set of minimal characteristic polynomial realisations as means for solving minimal realisation problem of nD systems”, International Journal of Control, 2015, (Submitted to).
  • [22] K. Hryniów, K. A. Markowski, “Optimisation of digraphs creation for parallel algorithm for finding a complete set of solutions of characteristic polynomial”. In: 20th International Conference on Methods and Models in Automation and Robotics (MMAR), 2015, 2015, 1139–1144.
  • [23] K. Hryniów, K. A. Markowski. “Classes of digraph structures corresponding to characteristic polynomials”. In: R. Szewczyk, C. Zieliński, and M. Kaliczyńska, eds., Challenges in Automation, Robotics and Measurement Techniques, Advances in Intelligent Systems and Computing, 329–339. Springer International Publishing, 2015.
  • [24] K. Hryniów, K. A. Markowski. “Optimisation of digraphs-based realisations for polynomials of one and two variables”. In: R. Szewczyk, C. Zieliński, and M. Kaliczyńska, eds., Progress in Automation, Robotics and Measuring Techniques, volume 350 of Advances in Intelligent Systems and Computing, 73–83. Springer International Publishing, 2015.
  • [25] R. Impagliazzo, R. Paturi, “On the complexity of k-SAT”, Journal of Computer and System Sciences, vol. 62, 2001, 367–375.
  • [26] T. Kaczorek, “Realization problem for general model of two-dimensional linear systems”, Bulletin of the Polish Academy of Sciences, Technical Sciences, vol. 35, no. 11–12, 1987, 633–637.
  • [27] T. Kaczorek, Positive 1D and 2D systems, Springer Verlag: London, 2001.
  • [28] T. Kaczorek, “Positive realization for 2D systems with delays”. In: Proceedings of 2007 International Workshop on Multidimensional (nD) Systems, 2007, 137 – 141.
  • [29] T. Kaczorek, “Positive realization of 2D general model”, Logistyka, vol. nr 3, 2007, 1–13.
  • [30] T. Kaczorek, M. Busłowicz, “Minimal realization problem for positive multivariable linear systems with delay”, Int. J. Appl. Math. Comput. Sci., no. 14(2), 2004, 181 – 187.
  • [31] T. Kaczorek, L. Sajewski, The Realization Problem for Positive and Fractional Systems, Springer International Publishing: Berlin, 2014.
  • [32] D. Luebke and G. Humphreys, “How GPUs work”, IEEE Computer, vol. 40, 2007, 96–100.
  • [33] K. A. Markowski, “Determination of positive realization of two dimensional systems using digraph theory and GPU computing method”. In: International Symposiumon Theoretical Electrical Engineering, 24th – 26th June 2013: Pilsen, Czech Republic, 2013, II7–II8.
  • [34] K. A. Markowski, “Determination of Reachability Index Set of Positive 2D System Using Digraph Theory and GPU Computing Method”. In: 18th International Conference on Methods and Models in Automation and Robotics (MMAR), Miedzyzdroje, Poland, August 26-29, 2013, 2013, 705–710.
  • [35] K. A. Markowski, “Determination of minimal realisation of one-dimensional continuous-time fractional linear system”, International Journal of Dynamics and Control, 2016 (Accepted).
  • [36] W. D. Wallis, A Beginner’s Guide to Graph Theory, Biiokhäuser, 2007.
  • [37] L. Xu, H. Fan, Z. Lin, N. Bose, “A directconstruction approach to multidimensional realization and LFR uncertainty modeling”, Multidimensional Systems and Signal Processing, vol. 19, no. 3–4, 2008, 323–359.
  • [38] L. Xu, L. Wu, Q. Wu, Z. Lin, Y. Xiao, “Reduced-order realization of Fornasini-Marchesini model for 2D systems”. In: Circuits and Systems, 2004. ISCAS ’04. Proceedings of the 2004 International Symposium on, vol. 3, 2004, III–289–292.
  • [39] L. Xu, L. Wu, Q. Wu, Z. Lin, Y. Xiao, “On realization of 2D discrete systems by Fornasini-Marchesini model”, International Journal of Control, Automation, and Systems, vol. 4, no. 3, 2005, 631–639.
  • [40] L. Xu, Q. Wu, Z. Lin, Y. Xiao, Y. Anazawa, “Futher results on realisation of 2D filters by Fornasini- Marchesini model”. In: 8th International Conference on Control, Automation, Robotics and Vision, Kunming, China, 6-9th December, 2004, 1460–1464.
Uwagi
PL
Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-ab5d6680-b084-4987-8a30-64f301f0074b
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.