Peter Buchholz, Tuğrul Dayar

Block SOR for Kronecker structured representations

Dokumente und Dateien


Bitte nutzen Sie beim Zitieren immer folgende Url:

Kurzfassung in Englisch

Hierarchical Markovian Models (HMMs) are composed of multiple low level models (LLMs) and high level model (HLM) that defines the interaction among LLMs. The essence of the HMM approach is to model the system at hand in the form of interacting components so that its (larger) underlying continous-time Markov chain (CTMC) is not generated but implicitly represented as a sum of Kronecker products of (smaller) component matrices. The Kronecker structure of an HMM induces nested block partitionings in its underlying CTMC. These partitionings may be used in block versions of classical iterative methods based on splittings, such as block SOR (BSOR), to solve the underlying CTMC for its stationary vector. Therein the problem becomes that of solving multiple nonsingular linear systems whose coefficient matrices are the diagonal blocks of a particular partitioning. This paper shows that in each HLM state there may be diagonal blocks with identical off-diagonal parts and diagonals differing from each other by a multiple of the identity matrix. Such diagonal blocks are named candidate blocks. The paper explains how candidate blocks can be detected and how the can mutually benefit from a single real Schur factorization. It gives sufficient conditions for the existence of diagonal blocks with real eigenvalues and shows how these conditions can be checked using component matrices. It describes how the sparse real Schur factors of candidate blocks satisfying these conditions can be constructed from component matrices and their real Schur factors. It also demonstrates how fill in- of LU factorized (non-candidate) diagonal blocks can be reduced by using the column approximate minimum degree algorithm (COLAMD). Then it presents a three-level BSOR solver in which the diagonal blocks at the first level are solved using block Gauss-Seidel (BGS) at the second and the methods of real Schur and LU factorizations at the third level. Finally, on a set of numerical experiments it shows how these ideas can be used to reduce the storage required by the factors of the diagonal blocks at the third level and to improve the solution time compared to an all LU factorization implementation of the three-level BSOR solver.

weitere Metadaten

Erschienen in Technische Berichte
Titel der Schriftenreihe
Technische Berichte / Technische Universität Dresden, Fakultät Informatik ; 2003,02 (TUD-FI03-02 März 2003)
Markow-Ketten, Matrizenrechnung, Schurzerlegung, Schur-Faktorisierung, Algebra, Kronecker-Produkt
Markov chains, Kronecker based numerical techniques, block SOR, real Schur factorization, COLAMD ordering
DDC Klassifikation004
RVK KlassifikationSS 5514
HochschuleTechnische Universität Dresden
FakultätFakultät Informatik
Erstveröffentlichungjahr der Druckausgabe2003
Veröffentlichungsdatum (online)15.01.2013
persistente URNurn:nbn:de:bsz:14-qucosa-100464

Hinweis zum Urheberrecht

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