License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.07071.7
URN: urn:nbn:de:0030-drops-10679
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2007/1067/
Go to the corresponding Portal

Marek, Ivo ; Pultarová, Ivana ; Mayer, Petr

Convergence of iterative aggregation/disaggregation methods based on splittings with cyclic iteration matrices

pdf-format:
07071.MarekIvo.Paper.1067.pdf (0.2 MB)

Abstract

Iterative aggregation/disaggregation methods (IAD) belong to competitive tools for computation the characteristics of Markov chains as shown in some publications devoted to testing and comparing various methods designed to this purpose. According to Dayar T., Stewart W.J., ``Comparison of
partitioning techniques for two-level iterative solvers on large, sparse Markov chains,'' SIAM J. Sci. Comput., Vol.21, No. 5, 1691-1705 (2000), the IAD methods are effective in particular when applied to large ill posed problems. One of the purposes of this
paper is to contribute to a possible explanation of this fact. The
novelty may consist of the fact that the IAD algorithms do converge independently of whether the iteration matrix of the corresponding process is primitive or not. Some numerical tests
are presented and possible applications mentioned; e.g. computing the PageRank.

BibTeX - Entry

@InProceedings{marek_et_al:DagSemProc.07071.7,
  author =	{Marek, Ivo and Pultarov\'{a}, Ivana and Mayer, Petr},
  title =	{{Convergence of iterative aggregation/disaggregation methods based on splittings with cyclic iteration matrices}},
  booktitle =	{Web Information Retrieval and Linear Algebra Algorithms},
  pages =	{1--27},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7071},
  editor =	{Andreas Frommer and Michael W. Mahoney and Daniel B. Szyld},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2007/1067},
  URN =		{urn:nbn:de:0030-drops-10679},
  doi =		{10.4230/DagSemProc.07071.7},
  annote =	{Keywords: Iterative aggregation methods, stochastic matrix, stationary probability vector, Markov chains, cyclic iteration matrix, Google matrix, PageRank.}
}

Keywords: Iterative aggregation methods, stochastic matrix, stationary probability vector, Markov chains, cyclic iteration matrix, Google matrix, PageRank.
Collection: 07071 - Web Information Retrieval and Linear Algebra Algorithms
Issue Date: 2007
Date of publication: 28.06.2007

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI