Peter Buchholz, Tuğrul Dayar

Block SOR Preconditional Projection Methods for Kronecker Structured Markovian Representations

Dokumente und Dateien

Hinweis

Bitte nutzen Sie beim Zitieren immer folgende Url:

http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-100508

Kurzfassung in Englisch

Kronecker structured representations are used to cope with the state space explosion problem in Markovian modeling and analysis. Currently an open research problem is that of devising strong preconditioners to be used with projection methods for the computation of the stationary vector of Markov chains (MCs) underlying such representations. This paper proposes a block SOR (BSOR) preconditioner for hierarchical Markovian Models (HMMs) that are composed of multiple low level models and a high level model that defines the interaction among low level models. The Kronecker structure of an HMM yields nested block partitionings in its underlying continuous-time MC which may be used in the BSOR preconditioner. The computation of the BSOR preconditioned residual in each iteration of a preconditioned projection method becoms the problem of solving multiple nonsingular linear systems whose coefficient matrices are the diagonal blocks of the chosen partitioning. The proposed BSOR preconditioner solvers these systems using sparse LU or real Schur factors of diagonal blocks. The fill-in of sparse LU factorized diagonal blocks is reduced using the column approximate minimum degree algorithm (COLAMD). A set of numerical experiments are presented to show the merits of the proposed BSOR preconditioner.

weitere Metadaten

Erschienen in Technische Berichte
Titel der Schriftenreihe
(Deutsch)
Technische Berichte / Technische Universität Dresden, Fakultät Informatik ; 2003,05 (TUD-FI03-05 Mai 2003)
Schlagwörter
(Deutsch)
Markow-Ketten, Matrizenrechnung, Schurzerlegung, Schur-Faktorisierung, Algebra
Schlagwörter
(Englisch)
Markov chains, Kronecker based numerical techniques, block SOR, preconditioning, projection methods, real Schur factorization, COLAMD ordering
DDC Klassifikation004
RVK KlassifikationSS 5514
Institution(en) 
HochschuleTechnische Universität Dresden
FakultätFakultät Informatik
DokumententypForschungsbericht
SpracheEnglisch
Erstveröffentlichungjahr der Druckausgabe2003
Veröffentlichungsdatum (online)15.01.2013
persistente URNurn:nbn:de:bsz:14-qucosa-100508
ISSN1430-211X

Hinweis zum Urheberrecht

Diese Website ist eine Installation von Qucosa - Quality Content of Saxony!
Sächsische Landesbibliothek Staats- und Universitätsbibliothek Dresden