Entry Sidi:2008:VEM from computmathappl2000.bib

Last update: Sat Mar 2 02:07:13 MST 2019                Valid HTML 4.0!

Index sections

Top | Symbols | Numbers | Math | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

BibTeX entry

@Article{Sidi:2008:VEM,
  author =       "Avram Sidi",
  title =        "Vector extrapolation methods with applications to
                 solution of large systems of equations and to
                 {PageRank} computations",
  journal =      j-COMPUT-MATH-APPL,
  volume =       "56",
  number =       "1",
  pages =        "1--24",
  month =        jul,
  year =         "2008",
  CODEN =        "CMAPDK",
  DOI =          "https://doi.org/10.1016/j.camwa.2007.11.027",
  ISSN =         "0898-1221 (print), 1873-7668 (electronic)",
  ISSN-L =       "0898-1221",
  MRclass =      "65F50 (65F10 65F15)",
  MRnumber =     "MR2427680 (2009j:65109)",
  MRreviewer =   "Cristina Tablino Possio",
  bibdate =      "Wed Mar 1 21:50:12 MST 2017",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/computmathappl2000.bib;
                 http://www.math.utah.edu/pub/tex/bib/pagerank.bib",
  URL =          "http://www.sciencedirect.com/science/article/pii/S0898122107008188",
  ZMnumber =     "1145.65312",
  abstract =     "An important problem that arises in different areas of
                 science and engineering is that of computing the limits
                 of sequences of vectors {x'n}, where x'n@?C^N with N
                 very large. Such sequences arise, for example, in the
                 solution of systems of linear or nonlinear equations by
                 fixed-point iterative methods, and lim'n'->'~x'n are
                 simply the required solutions. In most cases of
                 interest, however, these sequences converge to their
                 limits extremely slowly. One practical way to make the
                 sequences {x'n} converge more quickly is to apply to
                 them vector extrapolation methods. In this work, we
                 review two polynomial-type vector extrapolation methods
                 that have proved to be very efficient convergence
                 accelerators; namely, the minimal polynomial
                 extrapolation (MPE) and the reduced rank extrapolation
                 (RRE). We discuss the derivation of these methods,
                 describe the most accurate and stable algorithms for
                 their implementation along with the effective modes of
                 usage in solving systems of equations, nonlinear as
                 well as linear, and present their convergence and
                 stability theory. We also discuss their close
                 connection with the method of Arnoldi and with GMRES,
                 two well-known Krylov subspace methods for linear
                 systems. We show that they can be used very effectively
                 to obtain the dominant eigenvectors of large sparse
                 matrices when the corresponding eigenvalues are known,
                 and provide the relevant theory as well. One such
                 problem is that of computing the PageRank of the Google
                 matrix, which we discuss in detail. In addition, we
                 show that a recent extrapolation method of Kamvar et
                 al. that was proposed for computing the PageRank is
                 very closely related to MPE. We present a
                 generalization of the method of Kamvar et al. along
                 with a very economical algorithm for this
                 generalization. We also provide the missing convergence
                 theory for it.",
  acknowledgement = ack-nhfb,
  fjournal =     "Computers and Mathematics with Applications",
  journal-URL =  "http://www.sciencedirect.com/science/journal/08981221",
  keywords =     "Eigenvalue problems; Google matrix; Iterative methods;
                 Krylov subspace methods; Large sparse systems of
                 equations; Minimal polynomial extrapolation; PageRank
                 computations; Power iterations; Reduced rank
                 extrapolation; Singular linear systems; Stochastic
                 matrices; Vector extrapolation methods",
}

Related entries