Analysis of large Markov chains using stochastic automata networks
Büyük Markov zincirlerinin rassal özdevinimli ağ kullanılarak çözümlemesi
- Tez No: 112578
- Danışmanlar: DOÇ. DR. TUĞRUL DAYAR
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Markov zinciri, rassal özdevinimli ağlar, neredeyse tama men bölünebilirlik, birleştirilebilirlik, dolaylı birleştirme-ayrıştırma, Markov chain, Stochastic automata network, Near complete de- composability, lumpability, iterative aggregation-disaggregation
- Yıl: 2001
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 134
Özet
VI ÖZET Oleg Gusak Bilgisayar Mühendisliği, Doktora Tez Yöneticisi: Doç. Dr. Tuğrul Dayar Temmuz, 2001 Bu çalışma, rassal özdevinimli ağ olarak modellenen sonlu Markov zincirlerinin çözümlemesi alanında var olan araştırmaya katkıda bulunmaktadır, ilk olarak, bu tez Markov zincirlerinin neredeyse tamamen bölünebilirlik kavramını rassal özdevinimli ağlara genişleterek, alttaki Markov zincirinin çözülmesinde aslında var olan zorluğun kestirilmesini ve bu kavrama dayalı çözüm tekniklerinin araştırılmasını mümkün kılmaktadır. Bir rassal özdevinimli ağın altındaki Markov zincirinin neredeyse tamamen bölünebilir bloklara ayrışmış halini bul manın basit yolu, sisteme karşı gelen matrisin sıfırdan farklı elemanlarının hesap edilmesini gerektirir. Bu, çok büyük sistemler için bellek ve uygu lama zamanı sınırlamalarından dolayı seyrek matris gösterimiyle dahi mümkün değildir. Bu tezde, bu problem için, verilen bir rassal özdevinimli ağın herbir bileşenini çözümlemeye dayalı, bir etkili ayrıştırmalı çözüm algoritması sunul maktadır. Sayısal sonuçlar, verilen algoritmanın basit yöntemden çok daha iyi randıman verdiğini göstermektedir. ikinci olarak, bu çalışma bir rassal özdevinimli ağa karşı gelen matris için kontrol edilmesi kolay birleştirilebilirlik koşulları vermektedir. Sisteme karşı gelen matrisin tensör gösteriminin neden olduğu birleştirilebilir bir bölünme var olduğunda, rassal özdevinimli ağ modelinin altındaki Markov zincirinin değişmez durum dağılımının etkili bir dolaylı birleştirme-ayrıştırma algorit ması kullanılarak bulunabileceği gösterilmektedir. Sürekli-zamanlı ve kesintili- zamanlı rassal özdevinimli ağ modelleri üzerinde yapılan deneylerin sonuçları, önerilen algoritmanın son derece çetin bir rakip olan blok Gauss-Seidel'den hem ardışık tekrar sayısında hem de çözüme yakınsama için geçen süre yönünden daha iyi randıman verdiğini göstermektedir.vıı Son olarak, dolaylı birleştirme-ayrıştırma algoritmasının başarımı, birleştiri lebilir bölünmelerde nispi olarak büyük bloklara sahip sürekli-zamanlı rassal özdevinimli ağlar üzerinde araştırılmaktadır. Dolaylı birleştirme-ayrıştırma algoritmasının herbir ardışık tekrarında, büyük blokları çözmede karşılaşılan güçlükleri aşmak için rassal özdevinimli ağlar için blok Gauss-Seidel'm özyinele meli uygulaması kullanılmaktadır. Dolaylı birleştirme-ayrıştırma algoritmasının başarımı blok Gauss-Seidel'inki ile karşılaştırılmaktadır. Deney sonuçları, dolaylı birleştirme-ayrıştırmayı blok Gauss-Seidel'i geçecek şekilde ayarlamanın müm kün olduğunu göstermektedir.
Özet (Çeviri)
IV ABSTRACT ANALYSIS OF LARGE MARKOV CHAINS USING STOCHASTIC AUTOMATA NETWORKS Oleg Gusak Ph.D. in Computer Engineering Advisor: Assoc. Prof. Tuğrul Dayar July, 2001 This work contributes to the existing research in the area of analysis of fi nite Markov chains (MCs) modeled as stochastic automata networks (SANs). First, this thesis extends the near complete decomposability concept of Markov chains to SANs so that the inherent difficulty associated with solving the un derlying MC can be forecasted and solution techniques based on this concept can be investigated. A straightforward approach to finding a nearly completely decomposable (NCD) partitioning of the MC underlying a SAN requires the computation of the nonzero elements of its global generator. This is not feasi ble for very large systems even in sparse matrix representation due to memory and execution time constraints. In this thesis, an efficient decompositional so lution algorithm to this problem that is based on analyzing the NCD structure of each component of a given SAN is introduced. Numerical results show that the given algorithm performs much better than the straightforward approach. Second, this work specifies easy to check lumpability conditions for the generator of a SAN. When there exists a lumpable partitioning induced by the tensor representation of the generator, it is shown that an efficient iterative aggregation-disaggregation algorithm (IAD) may be employed to compute the steady state distribution of the MC underlying the SAN model. The results of experiments with continuous-time and discrete-time SAN models show that the proposed algorithm performs better than the highly competitive block Gauss- Seidel (BGS) in terms of both the number of iterations and the time to converge to the solution. Finally, the performance of the IAD algorithm on continuous-time SANsV having relatively large blocks in lumpable partitionings is investigated. To overcome difficulties associated with solving large diagonal blocks at each iter ation of the IAD algorithm, the recursive implementation of BGS for SANs is employed. The performance of IAD is compared with that of BGS. The results of experiments show that it is possible to tune IAD so that it outperforms BGS.
Benzer Tezler
- On the numerical analysis of infinite multi-dimensional Markov chains
Sonsuz çok boyutlu Markov zincirlerinin sayısal çözümlemesi üzerine
MUHSİN CAN ORHAN
Doktora
İngilizce
2017
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. TUĞRUL DAYAR
- Yeni zelanda GPS zaman serileri verisinin bayesci istatistik ile incelenmesi
Investigation of the New Zealand time series data with bayesian statistics
KUBİLAY ÖZCAN
Yüksek Lisans
Türkçe
2023
Jeoloji Mühendisliğiİstanbul Teknik ÜniversitesiJeoloji Mühendisliği Ana Bilim Dalı
PROF. DR. GÜRSEL SUNAL
PROF. DR. MEHMET SİNAN ÖZEREN
- Marmara Bölgesindeki sismik olayların stokastik modellerle incelenmesi
Investigation of seismic events in the Marmara Region with stochastic models
ÜLKÜ GÜRLEN
Doktora
Türkçe
2024
İstatistikOndokuz Mayıs Üniversitesiİstatistik Ana Bilim Dalı
PROF. DR. VEDAT SAĞLAM
- Stochastic roadmap simulation: An efficient representation and algorithm for analyzing molecular motion
Stokastik yol haritasi simulasyonu: Molekuler hareket analizi icin verimli bir temsil ve algoritma
MEHMET SERKAN APAYDIN
Doktora
İngilizce
2004
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolStanford UniversityMühendislik ve Doğa Bilimleri Ana Bilim Dalı
PROF. DR. JEAN-CLAUDE LATOMBE