Tez No	İndirme	Tez Künye	Durumu
470044		On the numerical analysis of infinite multi-dimensional Markov chains / Sonsuz çok boyutlu Markov zincirlerinin sayısal çözümlemesi üzerine Yazar:MUHSİN CAN ORHAN Danışman: PROF. DR. TUĞRUL DAYAR Yer Bilgisi: İhsan Doğramacı Bilkent Üniversitesi / Mühendislik ve Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:	Onaylandı Doktora İngilizce 2017 148 s.
Birden fazla alt sistemden oluşan ve Markov özelliğine sahip bir sistemi çok boyutlu bir Markov zinciri olarak göstermek mümkündür. Bu Markov zincirinin ulaşılabilir durum uzayı, genellikle çarpım durum uzayının bir öz alt kümesidir. Böyle bir Markov zincirine karşı gelen matrisin sıkıştırılmış olarak saklanması ve Kronecker işlemlerin etkili bir şekilde gerçekleştirilebilmesi, ulaşılabilir durum uzayının alt sistem durum uzaylarının alt kümelerinin Kartezyen çarpımlarının birleşimi olarak yazılmasını gerektirir. Bu çalışmada ilk olarak, üç veya daha fazla boyutlu bir sistemin ulaşılabilir durum uzayının en az sayıda alt sistem durum uzaylarının alt kümelerinin Kartezyen çarpımlarına bölümleme probleminin, NP-tam bir problem olduğunu gösteriyoruz. Bu problemi çözmek için, eniyi çözümü bulması kesin olmayan, biri birleştirme ve diğeri geliştirme temelli olmak üzere iki algoritma öneriyoruz. Literatürde yer alan ve rasgele olarak oluşturulmuş örneklerle yaptığımız deneyler, geliştirme temelli algoritmanın daha çok zaman ve bellek gerektirdiğini, ancak neredeyse her zaman daha az sayıda bölümleme bulabildiğini gösteriyor. Markov zincirine karşılık gelen matris, Kronecker çarpımları kullanılarak sıkıştırılmış olarak gösterildiğinde, çözümleme yöntemleri vektör-Kronecker terim çarpımının üzerine bina edilir. Kronecker terimlerdeki çarpan matrisler yoğun olduğunda, karma algoritması vektör-Kronecker terim çarpımını etkili bir şekilde hesaplayabilir. çarpan matrisler seyrek olduğunda ise, Markov zincirine karşılık gelen matrisin sıfırdan farklı elemanlarını çarpım esnasında oluşturup vektörde karşılık gelen elemanlarla çarpmak daha etkili olabilmektedir. Karma algoritmasını, Kronecker terimin çarpan matrislerindeki tamamı sıfır olan satır ve sütünları gözardı edecek şekilde değiştirmeyi öneriyoruz. Bu değişiklik, sonucu sıfır olan kayan noktalı sayı işlemlerinin gerçekleştirilmemesini sağlıyor. çok sayıda modelde, değiştirilmiş karma algoritması pek çok kayan noktalı sayı işleminden kaçınılmasını sağlıyor. Yine bazı modellerde, değiştirilmiş karma algoritmasının sıfırdan farklı elemenları çarpım esnasında oluşturan algoritmaya kıyasla daha az kayan noktalı sayı işlemi ve bellek gerektiriyor. Markov zincirine karşılık gelen matris, Kronecker çarpımları kullanılarak sıkıştırılmış olarak gösterilse bile, işlemler için gereken bellek miktarı ulaşılabilir durum uzayının büyüklüğüyle doğru orantılı olarak değişmektedir. özellikle boyut sayısı arttığında, bu daha büyük bir sorun oluşturmaktadır. Hiyerarşik Tucker ayrıştırması kullanarak, çözüm vektörlerinin görece sıkıştırılmış olarak tutulup, temel vektör-Kronecker terim çarpma işlemlerinin görece etkili olarak gerçekleştirilebildiğini gösteriyoruz. Sürekli zamanlı bir Markov zinciri olarak modellenmiş bir rassal kimyasal sistemin zamana bağlı değişimi kimyasal ana denklemi olarak da bilinen bir adi diferansiyel denklem sistemi olarak tanımlanabilir. Kimyasal ana denklemi, zamanı ayrıklaştırarak ve sayılabilir sonsuz durum uzayınının kesilerek elde edilmiş doğrusal sistemin çözülmesiyle çözümlenebilir. Durum uzayının ihmal edilebilir az sayıda durum içererek, kesilmiş durum uzayı dışında az miktarda olasılık kitlesi kalacak şekilde kesilmesi ise apaçık değildir. Hiyerarşik Tucker ayrıştırması kullanarak adi diferansiyel denklem çözücüsünün ihtiyaç duyduğu bellek miktarını azaltılabileceğini gösteriyoruz. Ayrıca, sonsuz durum uzayını kesmek için tahmin vektörlerini kullanan yenilikçi bir yöntem öneriyoruz. Sayısal deneyler uyarlamalı kesim stratejilerinin zaman ve bellek ihtiyacını, sabit kesim stratejilerine kıyasla ciddi olarak azalttığını gösteriyor. Son olarak, birden fazla sınıfa ait müşteri kabul eden, müşterilerin sınıfa bağımlı Markov varış sürecine göre geldikleri ve çok sayıda sunucusu olan bir yeniden denemeli kuyruk sistemini ele alıyoruz. Ele aldığımız sistemde, servis zamanlarınının sınıfa bağımlı evre-tipli, yeniden deneme zamanlarının ise çevrimsiz sınıfa bağımlı evre-tipli dağılım gösterdiklerini farz ediyoruz. Bu sistemin ölçümkallığının gerek ve yeter koşulunu ise sürüklenme fonksiyonlarına dayanan ölçütler kullanarak elde ediyoruz. Sonsuz durum uzayını uygun bir şekilde seçilmiş Lyapunov fonksiyonu kullanarak kesiyoruz. Elde ettiğimiz kesilmiş modeli ise çok boyutlu bir Markov zincir olarak tanımlayıp bu zincire karşılık gelen matrisin Kronecker temelli sayısal çözümlemesini gerçekleştiriyoruz.
A system with multiple interacting subsystems that exhibits the Markov property can be represented as a multi-dimensional Markov chain (MC). Usually the reachable state space of this MC is a proper subset of its product state space, that is, Cartesian product of its subsystem state spaces. Compact storage of the infinitesimal generator matrix underlying such a MC and efficient implementation of analysis methods using Kronecker operations require the set of reachable states to be represented as a union of Cartesian products of subsets of subsystem state spaces. We first show that the problem of partitioning the reachable state space of a three or higher dimensional system with a minimum number of partitions into Cartesian products of subsets of subsystem state spaces is NP-complete. Two algorithms, one merge based the other refinement based, that yield possibly non-optimal partitionings are presented. Results of experiments on a set of problems from the literature and those that are randomly generated indicate that, although it may be more time and memory consuming, the refinement based algorithm almost always computes partitionings with a smaller number of partitions than the merge based algorithm. When the infinitesimal generator matrix underlying the MC is represented compactly using Kronecker products, analysis methods based on vector-Kronecker product multiplication need to be employed. When the factors in the Kronecker product terms are relatively dense, vector-Kronecker product multiplication can be performed efficiently by the shuffle algorithm. When the factors are relatively sparse, it may be more efficient to obtain nonzero elements of the generator matrix in Kronecker form on-the-fly and multiply them with corresponding elements of the vector. We propose a modification to the shuffle algorithm that multiplies relevant elements of the vector with submatrices of factors in which zero rows and columns are omitted. This approach avoids unnecessary floating-point operations that evaluate to zero during the course of the multiplication. Numerical experiments on a large number of models indicate that, in many cases the modified shuffle algorithm performs a smaller number of floating-point operations than the shuffle algorithm and the algorithm that generates nonzeros on-the-fly, sometimes with minimum number of floating-point operations and amount of memory possible. Although the generator matrix is stored compactly using Kronecker products, solution vectors used in the analysis still require memory proportional to the size of the reachable state space. This becomes a bigger problem as the number of dimensions increases. We show that it is possible to use the hierarchical Tucker decomposition (HTD) to store the solution vectors during Kronecker-based Markovian analysis relatively compactly and still carry out the basic operation of vector-matrix multiplication in Kronecker form relatively efficiently. The time evolution of a stochastic chemical system modelled as a continuous-time MC (CTMC) can be described as a system of ordinary differential equations (ODEs) known as the chemical master equation (CME). The CME can be analyzed by discretizing time and solving a linear system obtained by truncating the countably infinite state space at each time step. However, it is not trivial to choose a truncated state space that includes few states with negligible probabilities and leaves out only a small probability mass. We show that it is possible to decrease the memory requirement of the ODE solver using HTD with adaptive truncation strategies and we propose a novel approach to truncate the countably infinite state space using prediction vectors. Numerical experiments indicate that adaptive truncation strategies improve time and memory efficiency significantly when fixed truncation strategies are inefficient. Finally, we consider a multi-class multi-server retrial queueing system in which customers arrive according to a class-dependent Markovian arrival process (MAP). Service and retrial times follow class-dependent phase-type (PH) distributions with the further assumption that PH distributions of retrial times are acyclic. Here, we obtain a necessary and sufficient condition for ergodicity from criteria based on drifts. The countably infinite state space of the model is truncated with an appropriately chosen Lyapunov function. The truncated model is described as a multi-dimensional MC and a Kronecker representation of its infinitesimal generator matrix is numerically analyzed.