Zapraszamy na Krakow Quantum Informatics Seminar organizowane wspólnie przez Katedrę Informatyki AGH i IBM Software Lab Kraków. Spotkanie odbędzie się we wtorek 04.12.2018 w godzinach 9:00-10:00 w Centrum Informatyki w sali 1.20.
W programie:
Bartłomiej Grochal , AVSystem, Krakow
Tensor Networks approach to simulating Continuous-Time Stochastic Automata Networks
Abstract:
Performance Evaluation is a well-established discipline of Computer Science which employs advanced analytical methods, highly-developed mathematical models and sophisticated numerical algorithms in order to study theoretical properties of distributed systems. One of the most widespread approaches dedicated to such simulations are stochastic Markovian models [1], however their greatest limitation is the ubiquitous state space explosion problem [2]. A remedy for the aforementioned issue – widely known as the Stochastic Automata Networks formalism – was proposed in late '80s by Plateau [3]. Despite the thirty-years-old heritage of Plateau's idea, there is still no numerical algorithm proposed which could handle simulation of a notable class of systems efficiently.
On the other hand, the Tensor Networks formalism introduced by Orús [4] has proven efficiency in overcoming the curse of dimensionality issue [5] for quantum many-body systems. In fact, such an approach appears to be notably effective for numerous interdisciplinary phenomena, which general impact emerges from collective behaviour of system's components [6]. Therefore, I would like to present the main research contribution of my MSc thesis [7]: the concept of reducing the task of determining a transient probability distribution over Stochastic Automata Network states to the matter of contraction between Tensor Networks. This observation underlies the novel TNSAN algorithm, which addresses simulation of the aforementioned class of Stochastic Automata Networks, unmanageable by dedicated numerical methods proposed so far. I would also like to discuss implementation of the TNSAN algorithm and preliminary experimental results for the elementary problem of distributed, component-based systems – the resource sharing mechanism. Moreover, introduction to Stochastic Automata Networks and Tensor Networks is going to be presented before.
References
[1] W.J. Stewart. Introduction to the Numerical Solution of Markov Chains. 1st ed. Princeton University Press, 1994. ISBN:9780691036991.
[2] B. Plateau and W.J. Stewart. “Stochastic Automata Networks”. In: Computational Probability. Ed. by W.K. Grassmann. 1st ed. Springer, 2000. Chap. 5, pp. 113–151. ISBN: 9781441951007.
[3] B. Plateau and K. Atif. “Stochastic Automata Network For Modeling Parallel Systems”. In: IEEE Transactions on Software Engineering 17.10 (1991), pp. 1093–1108.
[4] R. Orús. “A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States”. In: Annals of Physics 349 (2004), pp. 117–158.
[5] J.C. Bridgeman and C.T. Chubb. “Hand-waving and Interpretive Dance: An Introductory Course on Tensor Networks”. In: Journal of Physics A: Mathematical and Theoretical 50.22 (2017), p. 223001.
[6] S.-J. Ran et al. “Review of Tensor Network Contraction Approaches”. In: ArXiv e-prints, 2017, arXiv: 1708.09213
[7] Bartłomiej Grochal, Tensor Networks approach to simulating Continuous-Time Stochastic Automata Networks;Master of Science Thesis supervised by Katarzyna Rycerz and Piotr Gawron , AGH University of Science and Technology, Department of Computer Science, Krakow, Poland, 2018, http://dice.cyfronet.pl/publications/filters/filter_MSc_Theses