Analysis of large Markov chains using stochastic automata networks

Büyük Markov zincirlerinin rassal özdevinimli ağ kullanılarak çözümlemesi

Tez No: 112578
Yazar: OLEG GUSAK
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, Rastgele özdevinir ağlar, Markov chain, Stochastic automata network, Near complete de- composability, lumpability, iterative aggregation-disaggregation, Compatibility, Stochastic automata networks
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ı: Belirtilmemiş.

Ö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

Tez No
201
Çimentonun sertleşmesi üzerinde kimyasal komponentlerin etkisi
Başlık çevirisi yok
NACİYE TÜRKEL
Yüksek Lisans
Türkçe
1986
Kimya Mühendisliği Uludağ Üniversitesi
Kimya Ana Bilim Dalı
PROF. DR. MUSTAFA CEBE
Tez No
204
Nükleer rezonasta moleküler yapıların incelenmesi (yapısal faz geçiş kuramları üzerine bir inceleme)
Başlık çevirisi yok
ABDURRAHMAN ANDİÇ
Yüksek Lisans
Türkçe
1986
Fizik ve Fizik Mühendisliği Uludağ Üniversitesi
Fizik Ana Bilim Dalı
PROF. DR. AYTAÇ YALÇINER
Tez No
261
Makro besin elementlerinin (NPK) İzmir'de Mayıs ayında açığa dikilen 4-6 cm çevre büyüklüğündeki Gladiolus cinsine ait“hunting song”ve“Novalüx”kültür çeşitlerinin yumrularının gelişmeleri üzerine etkileri
Başlık çevirisi yok
TAHA ALİ AMEN
Yüksek Lisans
Türkçe
1985
Ziraat Ege Üniversitesi
Peyzaj Mimarlığı Ana Bilim Dalı
DOÇ. DR. ADNAN HATİPOĞLU
Tez No
262
Dokuma kumaşlarda örgü tipinin ham kumaşın boyutları ve geometrik özellikleri üzerindeki etkilerinin araştırılması
Başlık çevirisi yok
EMEL ÖNDER
Yüksek Lisans
Türkçe
1985
Tekstil ve Tekstil Mühendisliği Ege Üniversitesi
Tekstil Mühendisliği Ana Bilim Dalı
DOÇ. DR. GÜNGÖR BAŞER
Tez No
265
İki katlı pamuk ipliklerinden dokunan kumaşlarda örgüye bağlı olarak maksimum atkı sıklığının değişimi üzerinde bir araştırma
Başlık çevirisi yok
MELTEM ASLI NARTER
Yüksek Lisans
Türkçe
1985
Tekstil ve Tekstil Mühendisliği Ege Üniversitesi
Tekstil Mühendisliği Ana Bilim Dalı
DOÇ. DR. GÜNGÖR BAŞER

Geri Dön