Premium
Square and stretch multigrid for stochastic matrix eigenproblems
Author(s) -
Treister Eran,
Yavneh Irad
Publication year - 2010
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.708
Subject(s) - multigrid method , mathematics , eigenvalues and eigenvectors , grid , matrix (chemical analysis) , convergence (economics) , representation (politics) , square matrix , mathematical optimization , square (algebra) , feature (linguistics) , column (typography) , algorithm , geometry , symmetric matrix , mathematical analysis , connection (principal bundle) , partial differential equation , linguistics , physics , materials science , philosophy , quantum mechanics , politics , political science , law , economics , composite material , economic growth
A novel multigrid algorithm for computing the principal eigenvector of column‐stochastic matrices is developed. The method is based on an approach originally introduced by Horton and Leutenegger ( Perform. Eval. Rev. 1994; 22 :191–200) whereby the coarse‐grid problem is adapted to yield a better and better coarse representation of the original problem. A special feature of the present approach is the squaring of the stochastic matrix—followed by a stretching of its spectrum—just prior to the coarse‐grid correction process. This procedure is shown to yield good convergence properties, even though a cheap and simple aggregation is used for the restriction and prolongation matrices, which is important for maintaining competitive computational costs. A second special feature is a bottom–up procedure for defining coarse‐grid aggregates. Copyright © 2010 John Wiley & Sons, Ltd.