Last update: Sat Mar 2 02:07:13 MST 2019
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
- 65F10,
56(8)2048
- accelerators,
48(3)629
- accurate,
43(8)1161,
47(6)921,
48(1)163,
48(10)1415,
50(8)1241,
55(11)2602,
56(4)1114,
57(4)560
- addition,
50(8)1303,
53(8)1228
- al,
39(7)265
- along,
50(3)347
- area,
41(7)1049,
43(1)111,
51(6)1127,
55(9)2033,
57(4)529,
58(9)1769
- Arnoldi,
39(3)125,
44(8)1117
- case,
39(7)49,
41(3)541,
46(5)978,
47(8)1484,
48(5)805,
48(10)1425,
49(2)303,
53(6)880,
53(8)1284,
56(2)556,
58(3)579,
58(5)1030
- close,
55(2)299
- computation,
39(1)209,
39(3)262,
40(2)291,
40(2)359,
41(3)399,
43(3)351,
43(6)671,
43(12)1591,
44(5)711,
44(10)1439,
45(4)731,
45(10)1775,
45(10)1781,
46(5)985,
47(8)1486,
47(12)1865,
48(1)1,
48(1)163,
48(5)853,
49(2)331,
49(7)1127,
49(11)1889,
50(5)823,
50(5)881,
55(6)1113,
55(8)1870,
55(10)2183,
56(2)469,
56(8)1918,
57(7)1107,
58(11)2402
- computing,
28(4)107,
40(2)405,
40(2)415,
40(2)417,
40(2)420,
41(5)579,
42(1)231,
42(8)1229,
44(3)511,
45(10)1774,
45(10)1775,
46(2)502,
46(2)515,
47(6)1145,
47(8)1155,
47(8)1480,
47(8)1483,
48(3)561,
48(10)1557,
53(1)41,
53(9)1421,
54(3)336,
54(3)448,
55(8)1720,
56(2)565,
57(3)420,
57(8)1324,
57(11)2001,
58(9)1830
- connection,
54(6)763,
58(5)841
- convergence,
39(1)69,
39(3)1,
39(7)95,
40(1)1,
40(1)37,
40(4)443,
40(4)559,
40(4)625,
40(6)735,
40(10)1127,
41(1)83,
41(1)229,
41(3)489,
41(5)627,
42(1)23,
43(8)1079,
44(1)13,
44(1)231,
44(3)277,
44(3)339,
44(3)347,
44(3)457,
44(7)877,
44(10)1445,
45(1)189,
45(10)1469,
46(1)165,
46(1)183,
46(2)239,
46(8)1337,
46(10)1461,
47(2)247,
47(2)441,
47(4)707,
47(4)767,
47(4)793,
47(6)1057,
47(10)1565,
47(10)1745,
48(3)347,
48(3)373,
48(3)455,
48(10)1477,
49(1)13,
49(11)1905,
50(5)719,
50(10)1755,
51(3)441,
51(6)999,
51(6)1093,
51(12)1751,
52(5)769,
52(5)791,
52(6)967,
52(6)1011,
52(6)1107,
52(8)1205,
52(10)1425,
53(3)605,
53(5)693,
53(5)770,
53(10)1567,
54(4)507,
55(4)745,
55(4)760,
55(6)1081,
55(6)1293,
55(7)1481,
55(8)1693,
55(10)2318,
55(11)2544,
55(12)2740,
56(5)1255,
56(6)1473,
56(7)1779,
56(8)2027,
56(8)2048,
56(9)2305,
56(10)2572,
56(12)3023,
56(12)3070,
57(2)240,
57(3)455,
57(4)513,
57(6)867,
57(7)1187,
57(11)1843,
57(11)1869,
58(3)579,
58(7)1320,
58(7)1397,
58(11)2167,
58(11)2221
- corresponding,
55(8)1644
- derivation,
46(4)633,
48(7)1135,
51(6)865,
57(5)744
- different,
42(1)91,
42(8)1239,
48(10)1779,
55(10)2295,
57(7)1073,
58(7)1391,
58(11)2152
- dominant,
47(2)161
- effective,
46(8)1435,
47(8)1309,
49(1)39,
49(7)1069,
50(10)1543,
55(8)1720,
55(9)2118,
56(10)2629,
58(11)2379
- efficient,
40(2)359,
40(4)453,
42(8)1217,
42(10)1311,
43(1)65,
45(1)165,
45(10)1757,
46(7)1055,
47(8)1309,
48(3)529,
48(5)885,
50(3)471,
51(1)51,
52(3)459,
53(2)329,
54(6)737,
54(7)879,
54(7)1101,
55(4)660,
55(12)2791,
56(3)822,
57(4)664,
57(11)1756,
58(1)65,
58(4)632,
58(7)1418,
58(10)1965,
58(11)2199
- eigenvalue,
39(7)1,
39(7)211,
40(4)589,
41(10)1317,
42(8)1177,
45(6)1319,
45(6)1339,
46(1)57,
46(5)783,
47(4)643,
47(8)1155,
48(7)1121,
49(5)789,
49(7)1279,
49(11)1941,
51(8)1251,
53(1)41,
53(5)789,
53(8)1271,
54(5)699,
55(6)1129,
55(9)1998,
55(11)2521,
56(1)172,
56(4)909,
56(11)2825,
56(12)3204,
57(10)1645
- eigenvector,
47(8)1155,
49(11)1867
- engineering,
40(2)418,
41(3)538,
45(1)273,
46(1)125,
46(2)508,
46(5)985,
47(6)1153,
47(8)1478,
55(5)970,
55(7)1363,
58(5)819
- example,
56(11)2789
- extrapolation,
45(1)189,
47(8)1463,
57(8)1313
- fixed-point,
39(7)17,
41(3)497,
41(7)917,
42(3)273,
42(6)909,
46(5)919,
46(12)1779,
47(2)195,
47(6)845,
47(6)913,
48(10)1461,
50(7)1051,
51(3)589
- generalization,
39(3)161,
41(3)497,
44(1)181,
46(5)681,
48(3)539,
53(1)104,
55(3)485,
55(8)1785,
56(11)2941,
57(2)332,
58(1)80,
58(4)711,
58(7)1383
- GMRES,
45(10)1757,
47(8)1335
- implementation,
41(7)1009,
41(10)1403,
42(8)1239,
55(6)1094,
55(7)1514,
57(11)1736
- interest,
46(1)69,
46(5)741,
47(12)vii--viii,
48(1)vii--viii,
51(3)387
- iteration,
39(7)81,
41(3)489,
41(5)579,
42(12)1565,
43(3)423,
43(10)1381,
43(12)1585,
44(3)347,
46(8)1201,
46(10)1535,
47(2)447,
47(4)707,
47(8)1195,
47(10)1745,
50(3)433,
50(3)575,
50(5)729,
50(10)1513,
51(6)1093,
52(6)1107,
53(5)741,
53(6)886,
53(6)977,
53(7)1012,
53(10)1567,
54(5)721,
54(7)879,
54(7)881,
54(7)895,
54(7)903,
54(7)910,
54(7)926,
54(7)933,
54(7)940,
54(7)955,
54(7)987,
54(7)993,
54(7)1003,
54(7)1010,
54(7)1018,
54(7)1047,
54(7)1064,
54(7)1071,
54(7)1079,
54(7)1086,
54(7)1092,
54(7)1112,
54(7)1133,
54(7)1139,
54(7)1154,
54(7)1188,
54(7)1197,
56(2)346,
56(2)411,
56(8)1948,
56(8)2027,
57(3)483,
58(1)88,
58(2)322,
58(3)528,
58(9)1755,
58(11)2091,
58(11)2098,
58(11)2160,
58(11)2167,
58(11)2172,
58(11)2177,
58(11)2182,
58(11)2190,
58(11)2199,
58(11)2260,
58(11)2347,
58(11)2360,
58(11)2444,
58(11)2486,
58(11)2489,
58(11)2495,
58(11)2514,
58(11)2518,
58(11)2528
- iterative,
39(3)85,
39(3)137,
40(2)171,
40(8)971,
40(10)1127,
40(10)1171,
41(1)103,
41(3)505,
42(1)131,
42(10)1485,
43(1)31,
43(1)81,
43(3)607,
44(1)175,
44(3)457,
44(5)833,
44(8)1109,
44(10)1307,
45(1)69,
45(4)623,
45(6)887,
46(8)1229,
47(2)441,
47(4)501,
47(4)529,
47(4)727,
47(4)767,
47(6)913,
48(1)73,
48(5)951,
48(12)1929,
49(11)1905,
50(5)935,
50(7)1179,
50(10)1559,
50(10)1587,
52(8)1205,
52(10)1403,
53(5)693,
53(6)972,
53(7)1153,
53(10)1572,
54(4)476,
54(4)579,
54(6)850,
54(6)872,
55(4)843,
55(8)1832,
55(10)2266,
55(10)2338,
55(10)2346,
55(11)2512,
55(12)2999,
56(1)290,
56(2)565,
56(3)727,
56(4)942,
56(4)978,
56(5)1314,
56(9)2305,
56(10)2455,
56(12)3046,
56(12)3070,
56(12)3246,
57(1)101,
57(3)455,
58(7)1397,
58(7)1441,
58(8)1589,
58(10)2022
- known,
51(6)1021
- Krylov,
44(1)125,
49(7)1045,
58(6)1093
- large,
39(3)125,
41(3)513,
41(7)813,
42(1)121,
42(10)1331,
43(1)131,
44(8)1117,
45(1)217,
45(10)1757,
46(4)603,
47(8)1483,
49(9)1387,
51(11)1705,
53(1)1,
53(3)491,
57(3)420,
57(5)799
- limit,
42(3)543,
43(3)413,
44(1)51,
44(3)445,
44(8)997,
44(10)1289,
45(1)189,
45(10)1781,
45(10)1781,
46(2)231,
46(7)999,
47(1)37,
47(6)859,
47(6)967,
48(3)577,
49(11)1669,
51(2)345,
51(9)1453,
52(3)485,
52(10)1577,
53(10)1518,
53(11)1644,
54(5)651,
55(9)2064,
56(5)1434,
56(9)2323,
56(11)2957,
57(4)677,
57(5)740,
58(4)649
- minimal,
40(1)63,
46(5)805,
46(7)1111,
47(10)1739,
48(3)419,
49(7)1233,
50(5)783,
53(12)1785,
54(3)350,
56(1)160,
56(2)387,
56(11)2825
- mode,
46(10)1611,
47(2)301,
49(9)1413
- N,
41(3)536,
41(3)538,
41(3)541,
41(3)542,
46(2)513,
46(2)513
- obtain,
49(2)331,
51(9)1493,
58(1)39
- one,
40(8)1037,
41(5)697,
45(10)1489,
46(5)813,
47(1)23,
47(6)955,
47(12)1827,
48(3)649,
54(5)617,
54(6)793,
55(2)132,
55(12)2981,
56(4)918,
56(7)1876,
56(10)2692,
56(12)3000,
58(9)1816
- PageRank,
57(10)1645
- point, fixed-,
39(7)17,
41(3)497,
42(3)273,
46(5)919,
46(12)1779,
47(2)195,
47(6)913,
48(10)1461,
50(7)1051
- polynomial,
39(1)209,
39(3)95,
39(7)95,
40(10)1205,
41(1)1,
41(3)269,
41(3)399,
41(7)879,
41(9)1085,
41(9)1125,
41(9)1173,
41(12)1559,
42(1)57,
42(6)767,
42(6)981,
42(8)1177,
42(8)1229,
43(10)1407,
44(1)253,
44(5)607,
44(5)633,
44(8)997,
44(12)1539,
45(1)9,
45(1)229,
45(4)843,
45(10)1611,
46(5)769,
46(8)1263,
46(8)1387,
47(2)441,
47(2)447,
47(4)719,
48(3)577,
48(5)789,
48(5)833,
48(9)1299,
48(12)1811,
49(9)1515,
49(11)1669,
50(1)263,
50(3)381,
50(5)919,
50(8)1231,
50(10)1697,
51(3)527,
51(3)605,
51(3)631,
51(8)1199,
51(9)1377,
51(9)1453,
51(12)1817,
53(10)1518,
54(3)336,
54(4)484,
54(5)679,
55(5)900,
55(6)1122,
55(6)1322,
56(2)411,
56(4)1040,
56(4)1045,
56(4)1114,
56(5)1358,
56(6)1587,
56(12)2993,
56(12)3236,
57(2)308,
57(2)332,
57(4)677,
57(10)1659,
58(1)104,
58(4)734,
58(7)1370,
58(9)1852,
58(11)2182
- power,
39(11)139,
42(6)981,
47(2)447,
47(4)541,
49(2)187,
49(9)1515,
51(2)285,
54(2)310,
56(4)918,
56(6)1617,
57(11)1835,
57(11)1883,
58(1)25,
58(3)403
- practical,
40(2)417,
40(10)1285,
41(9)1183,
46(12)1787,
48(10)1549
- proposed,
39(5)227
- rank,
50(7)1061,
52(6)861,
54(6)819,
55(6)1270,
57(10)1645
- recent,
40(12)1349,
42(3)561,
45(4)783,
55(4)733
- reduced,
45(1)37
- related,
39(5)81,
40(1)71,
44(12)1539,
47(1)91,
47(6)913,
51(3)497,
51(9)1405,
51(11)1663,
55(5)1068,
55(6)1333,
56(5)1271,
58(4)717,
58(7)1466,
58(9)1711,
58(9)1869
- relevant,
45(4)835
- required,
58(9)1762
- science,
39(3)260,
39(3)261,
39(3)263,
39(3)266,
39(7)264,
39(7)265,
40(2)415,
40(2)416,
41(3)542,
41(10)1343,
45(10)1781,
46(2)508,
46(2)517,
46(5)978,
46(5)980,
47(6)1153,
47(8)1478,
47(8)1482,
55(5)863,
55(7)1363,
56(2)469,
58(5)819
- sequence,
39(3)95,
39(3)205,
39(11)37,
39(11)57,
39(11)95,
40(2)239,
41(3)301,
41(9)1085,
41(9)1125,
41(9)1155,
45(12)1895,
47(10)1487,
48(3)629,
51(3)559,
52(6)1011,
53(7)1050,
53(12)1792,
54(4)525,
54(11)1380,
55(6)1293,
56(2)375,
56(2)469,
56(7)1726,
57(1)96,
57(5)702,
57(11)1800,
57(11)2001,
58(1)39,
58(2)329,
58(4)717,
58(9)1859
- show,
49(2)331
- simply,
39(3)266
- singular,
39(3)177,
40(2)249,
41(3)327,
41(3)483,
41(5)563,
41(12)1579,
42(3)465,
42(6)927,
42(10)1331,
43(3)351,
43(3)491,
43(6)681,
44(1)111,
44(3)323,
44(8)1157,
44(10)1289,
45(1)69,
45(1)469,
45(4)593,
45(4)605,
45(4)635,
45(10)1637,
46(5)751,
46(5)978,
46(12)1827,
47(2)391,
47(4)667,
47(4)683,
47(4)739,
47(8)1195,
47(8)1317,
48(5)913,
49(5)651,
49(5)765,
49(7)1059,
49(7)1279,
50(1)133,
50(3)399,
50(3)567,
50(8)1371,
50(10)1755,
51(3)507,
51(9)1463,
52(3)375,
52(3)539,
52(6)1031,
53(9)1429,
53(12)1854,
54(2)255,
55(6)1075,
55(11)2574,
55(12)2940,
56(1)30,
56(4)1025,
56(4)1059,
56(4)1146,
56(7)1820,
56(8)1975,
56(9)2145,
56(11)2825,
56(12)3195,
57(4)664,
57(5)821,
58(4)632,
58(5)930,
58(7)1425,
58(7)1449
- slowly,
46(5)719
- solving,
40(2)417,
40(6)721,
40(8)927,
40(8)1015,
40(12)1375,
41(1)157,
41(3)489,
41(12)1505,
42(8)1025,
42(8)1123,
42(10)1439,
43(1)131,
43(3)525,
44(3)457,
44(8)1249,
45(1)263,
45(4)823,
45(10)1757,
46(1)57,
47(4)529,
47(8)1429,
48(3)373,
48(5)709,
48(9)1285,
48(10)1651,
49(7)1113,
50(1)73,
50(1)217,
50(1)281,
51(5)769,
51(6)937,
51(8)1335,
52(3)459,
52(6)1021,
53(3)491,
53(6)977,
53(9)1439,
53(10)1481,
53(10)1572,
54(3)319,
54(7)895,
54(7)903,
54(7)926,
54(7)987,
54(7)1010,
54(7)1071,
54(7)1133,
54(7)1162,
55(1)101,
55(3)563,
55(4)760,
55(4)819,
55(5)900,
55(5)912,
55(8)1832,
55(9)1974,
55(10)2363,
55(12)2823,
55(12)2953,
55(12)2993,
56(2)346,
56(2)453,
56(3)754,
56(8)1948,
56(8)2027,
56(10)2455,
56(10)2550,
56(12)3046,
56(12)3246,
56(12)3261,
57(1)101,
57(2)230,
57(4)612,
57(5)757,
57(9)1485,
57(10)1651,
57(11)1748,
57(11)1877,
58(4)619,
58(4)632,
58(4)678,
58(7)1418,
58(8)1589,
58(9)1725,
58(9)1844,
58(10)1936,
58(10)1970,
58(11)2084,
58(11)2160,
58(11)2167,
58(11)2172,
58(11)2190,
58(11)2209,
58(11)2231,
58(11)2379,
58(11)2395,
58(11)2523,
61(6)1704
- sparse,
42(1)121,
43(1)131,
45(10)1757,
48(3)589,
53(1)1,
58(6)1152
- stable,
39(1)169,
39(3)247,
44(5)799,
45(6)935,
46(4)639,
47(6)859,
48(5)853,
49(1)81,
50(5)701,
51(6)1011,
51(9)1539,
53(10)1492,
56(3)754,
56(4)847
- stochastic,
39(3)147,
40(4)421,
42(1)199,
42(6)871,
43(6)641,
45(1)329,
46(5)741,
46(7)1073,
46(7)1165,
47(6)903,
48(10)1603,
49(9)1549,
50(5)809,
51(2)179,
51(2)285,
51(9)1445,
52(1)137,
52(1)161,
53(5)729,
53(6)977,
55(5)879,
55(5)1007,
55(8)1766,
55(10)2329,
55(11)2413,
56(3)697,
56(7)1773,
56(9)2145,
56(10)2700,
56(10)2724,
56(12)3157,
57(1)54,
58(1)48,
58(11)2236
- subspace,
44(1)125,
49(7)1045,
49(11)1853,
55(11)2395,
58(6)1093
- such,
49(2)331
- theory,
39(1)55,
39(1)183,
39(1)245,
39(3)260,
39(3)265,
39(5)227,
39(12)1,
40(2)415,
40(2)416,
40(6)835,
40(6)845,
41(3)538,
41(5)619,
41(7)917,
41(9)1199,
41(10)1465,
42(12)1523,
43(8)975,
44(5)763,
45(1)391,
45(4)555,
46(2)502,
46(2)512,
46(5)979,
47(6)1145,
47(8)1257,
47(10)1535,
47(10)1745,
49(5)841,
49(11)1709,
49(11)1867,
51(1)17,
51(9)1405,
51(12)1761,
52(6)997,
52(8)1299,
52(10)1439,
52(10)1563,
53(2)156,
53(2)287,
53(3)461,
53(5)803,
53(7)1107,
53(9)1390,
54(2)242,
54(2)267,
54(5)664,
54(5)730,
54(7)1000,
55(5)1034,
55(8)1754,
55(9)2086,
56(2)375,
56(7)1899,
56(9)2418,
56(12)3046,
57(3)367,
57(5)691,
57(9)1438,
57(9)1547,
57(11)1792
- two,
39(1)103,
39(7)237,
39(9)1,
39(12)101,
40(4)589,
40(6)835,
40(8)971,
41(5)579,
41(7)1033,
42(1)157,
43(12)1529,
44(1)51,
44(1)241,
45(6)1327,
46(7)1081,
46(7)1095,
46(8)1337,
46(12)1779,
47(1)1,
47(2)195,
47(2)461,
47(10)1487,
48(3)387,
48(10)1549,
48(10)1701,
49(2)321,
49(2)335,
49(5)777,
51(1)153,
52(10)1543,
52(12)1711,
53(3)347,
54(11)1367,
55(9)2108,
55(11)2506,
55(11)2643,
56(1)43,
56(1)151,
56(5)1457,
56(8)2043,
56(10)2481,
57(7)1147,
57(10)1701,
58(1)88,
58(2)329,
58(6)1081,
58(7)1287,
59(1)595
- used,
56(10)2724
- vector,
39(3)247,
40(4)523,
41(3)399,
41(3)461,
41(7)917,
42(12)1527,
43(8)1153,
44(10)1357,
45(4)647,
45(10)1591,
47(6)1123,
48(5)779,
48(5)841,
54(11)1353,
54(11)1403,
55(6)1164,
55(12)2746,
56(2)311,
56(6)1626,
57(6)885,
57(7)1196,
57(10)1682,
58(8)1550
- very,
42(10)1331
- well,
41(10)1465
- when,
46(7)1065
- which,
40(4)607,
54(3)357,
56(9)2268,
58(10)1887
- work,
51(5)849,
53(2)305