Geri Dön

Experiments with two-stage iterative solvers and precondilioned krylov subipace methods on nearly completely decomposoble markov chovins

İki seviyeli dolaylı çözücüler ve iyileştirilmiş krylov altuzay yöntemleri ile neredeyse bölünebilir markov zincirleri üzerinde deneyler

  1. Tez No: 58592
  2. Yazar: WAÜL GUEOJEB
  3. Danışmanlar: DOÇ. DR. TUĞRUL DAYAR
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Markov chains, near complete decomposability, stationary iter¬ ative methods, projection methods, block iterative methods, preconditioning, ill-conditioning
  7. Yıl: 1997
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 139

Özet

ÖZET İKİ SEVİYELİ DOLAYLI ÇÖZÜCÜLER VE İYİLEŞTİRİLMİŞ KRYLOV ALTUZAY YÖNTEMLERİ İLE NEREDEYSE BÖLÜNEBİLİR MARKOV ZİNCİRLERİ ÜZERİNDE DENEYLER Wail Gueaieb Bilgisayar ve Enformatik Mühendisliği, Yüksek Lisans Tez Yöneticisi: Yrd. Doç. Dr. Tuğrul Dayar Haziran, 1997 iyileştirilmiş Krylov altuzay yöntemleri çoğunlukla son onbeş yılda geliş tirilmiş, başka şeyler yanında, Markov zincirlerinin durağan dağılımlarını elde etmede kullanman en son dolaylı çözücülerdir. İlgilenilen Markov zincirlerinin indirgenemez olduğu varsayılırsa, problem tekil bir katsayı matrisine sahip bir türdeş lineer cebirsel denklemler takımına bir normalleştirme şartı altında pozitif bir çözüm vektörü hesaplamaktan ibarettir. Yani, Ax = 0, |[a?||a = 1 (0.1) deki (n X l)'lik bilinmeyen durağan vektör x aranmaktadır. Burada A = I - PT n x n tekil bir M-matrisi ve P bir-adımlık rassal geçiş olasılık matrisidir. Son gelişmelere rağmen, mesleklerini icra eden başarım çözümleyicileri, yeni tasarlanmış algoritmaların başarımını var olanlarla kıyaslamak istediklerinde, veya eldeki bir sistem modelinin başarımını değerlendirmek için aday çözücülere gerek duyduklarında, hala çoğunlukla bölmeye dayanan dolaylı yöntemleri tercih etmektedirler. Esasında, Markov zincirleri, özellikle de hastalıklı neredeyse bölünebilir olanları üzerinde Krylov altuzay yöntemleri ile deneysel sonuçlar pek azdır. Biz bu alanda, özellikle de neredeyse bölünebilir Markov zincir lerinin bağlanma derecelerinin ve sıfırdan farklı yapılarının iyileştirilmiş Krylov altuzay yöntemlerinin yakınsama özellikleri ve yer gerekleri üzerindeki etkilerini anlamamıza yardım edecek araştırmalar için yer olduğuna inanıyoruz. Bazı araştırmacıların çalışmaları başka fakat ilintili yönde araştırmaları ne den olan önemli ve ilginç sorular ortaya çıkardı. Bu sorular şunlardır:“EğerVI sistem neredeyse bölünebilirse ve (blok ardarda üst yumuşatma - SOR gibi) iki seviyeli bir dolaylı çözücü kullanılacaksa, (0.1) denklemindeki global kat sayı matrisi A 'yi nasıl parçalara ayırmalı P'nin neredeyse bölünebilir normal yapısının zorunlu kıldığı blok ayrıştırmalar diğerlerine oranla mutlaka daha mı üstündür? Alternatif ayrıştırmalara yatırım yapmaya değer mi? Hatta, durumlar sabit adlandırılıp ayrıştırıldığmda blok ardarda üst yumuşatmanın (hatta nokta ardarda üst yumuşatmanın) başarımı dolaylı birleştirme-ayrıştırma algoritmasının başarımı ile nasıl kıyaslar? Son olarak, iyileştirilmiş Krylov altuzay yöntemleri varken iki seviyeli dolaylı çözücüleri kullanmanın bir değeri var mıdır?”Deneysel sonuçlar pek çok test vakasında iki seviyeli dolaylı çözücülerin seçilmiş iyileştiriciler için Krylov altuzay yöntemlerine göre neredeyse bölünebilir Markov zincirlerinden daha üstün olduklarını göstermektedir. İki seviyeli dolaylı çözücüler için, katsayı matrisinin basit bir ayrıştırılmasının neredeyse bölünebilir yapısının kullanılarak bulunacak bir taneden daha hızlı çözüm verdiği vakalar vardır. Anahtar kelimeler. Markov zincirleri, neredeyse bölünebilirlik, durağan dolaylı yöntemler, projeksiyon yöntemleri, blok dolaylı yöntemler, iyileştirme, hastalıklılık.

Özet (Çeviri)

III ABSTRACT EXPERIMENTS WITH TWO-STAGE ITERATIVE SOLVERS AND PRECONDITIONED KRYLOV SUBSPACE METHODS ON NEARLY COMPLETELY DECOMPOSABLE MARKOV CHAINS Wail Gueaieb M.S. in Computer Engineering and Information Science Supervisor: Assistant Professor Dr. Tuğrul Dayar June, 1997 Preconditioned Krylov subspace methods are state-of-the-art iterative solvers developed mostly in the last fifteen years that may be used, among other things, to solve for the stationary distribution of Markov chains. Assuming Markov chains of interest are irreducible, the problem amounts to computing a pos- itive solution vector to a homogeneous system of linear algebraic equations with a singular coefficient matrix under a normalization constraint. That is, the (n x 1) unknown stationary vector x in Ax = Q, llarllj = 1(0.1) is sought. Here A - I - PT, an n x n singular M-matrix, and P is the one-step stochastic transition probability matrix. Albeit the recent advances, practicing performance analysts stili widely pre- fer iterative methods based on splittings when they want to compare the per¬ formance of newly devised algorithms against existing ones, ör when they need candidate solvers to evaluate the performance of a system model at hand. in fact, experimental results with Krylov subspace methods on Markov chains, especially the ill-conditioned nearly completely decomposable (NCD) ones, are few. We believe there is room for research in this area specifically to help us understand the effect of the degree of coupling of NCD Markov chains and their nonzero structure on the convergence characteristics and space requirements of preconditioned Krylov subspace methods.IV The work of several researchers have raised important and interesting ques- tions that led to research in anotlıer, yet related direction. These questions are the following:“How must öne go about partitioning the global coefficient matrix A in equation (0.1) into blocks if the system is NCD and a two-stage iterative solver (such as block successive overrelaxation-SOR) is to be em- ployed? Are block partitionings dictated by the NCD normal form of P neces- sarily superior to others? Is it worth investing alternative partitionings? Better yet, for a fixed labelling and partitioning of the states, how does the perfor- mance of block SOR (ör even that of point SOR) compare to the performance of the iterative aggregation-disaggregation (IAD) algorithm? Finally, is there any merit in using two-stage iterative solvers when preconditioned Krylov subspace methods are available?”Experimental results show that in most of the test cases two-stage iterative solvers are superior to Krylov subspace methods with the chosen precondition- ers, on NCD Markov chains. For two-stage iterative solvers, there are cases in which a straightforward partitioning of the coefficient matrix gives a faster solution than can be obtained using the NCD normal form.

Benzer Tezler

  1. Tez No

    520102

    On the analysis and evaluation of sparse hybrid linear solvers

    Sparse hibrit doğrusal çözücülerinin analizi ve değerlendirilmesi

    AFRAH NAJIB ABDULLAH FAREA

    Yüksek Lisans

    İngilizce

    İngilizce

    2018

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Hesaplamalı Bilimler ve Mühendislik Ana Bilim Dalı

    PROF. DR. MUSTAFA SERDAR ÇELEBİ

  2. Tez No

    719688

    T4 ve T6 ısıl işlemli 6061 alüminyum levhanın iki eksenli gerilmeler altında şekil değiştirmesinin incelenmesi

    Investigation of deformation of T4 & T6 heat treated 6061 aluminum plate under biaxial stress

    EGEMEN UZ

    Yüksek Lisans

    Türkçe

    Türkçe

    2022

    Makine Mühendisliğiİstanbul Teknik Üniversitesi

    Makine Mühendisliği Ana Bilim Dalı

    PROF. DR. ŞAFAK YILMAZ

  3. Tez No

    143110

    Parallel solution of unsteady, incompressible three-dimensional Navier-Stokes equations with a new implicit method

    Zamana bağlı, sıkıştırılamaz, üç boyutlu Navier-Stokes denklemlerinin yeni bir kapalı metodlar paralel çözümü

    VİLDAN ÜSTOĞLU ÜNAL

    Doktora

    İngilizce

    İngilizce

    2003

    Astronomi ve Uzay Bilimleriİstanbul Teknik Üniversitesi

    Astronomi ve Uzay Bilimleri Ana Bilim Dalı

    PROF. DR. ÜLGEN GÜLÇAT

  4. Tez No

    866232

    Aerodynamic shape optimization of the DLR-F6 wing by using openfoam as CFD solver integrated with rsm

    DLR-F6 uçak kanadının RSM yöntemiyle entegre bir sekilde had çözücüsü olarak openfoam kullanılarak aerodinamik sekil optimizasyonu

    HALİL BULUŞ

    Yüksek Lisans

    İngilizce

    İngilizce

    2023

    Havacılık ve Uzay Mühendisliğiİstanbul Teknik Üniversitesi

    Makine Mühendisliği Ana Bilim Dalı

    DOÇ. DR. SERTAÇ ÇADIRCI

  5. Tez No

    570000

    Stochastic path planning in the presence of disambiguation and neutralization capabilities

    Belı̇rsı̇zlı̇ğı̇ gı̇derme ve etkı̇sı̇zleştı̇rme yeteneklerı̇nı̇n varlığında olasılıksal yol planlaması

    SERKAN YILDIRIM

    Doktora

    İngilizce

    İngilizce

    2019

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMarmara Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. ALİ FUAT ALKAYA

    DOÇ. DR. VURAL AKSAKALLI

Geri Dön