2522:
1904:
2124:
1554:
2517:{\displaystyle {\tilde {H}}_{n}={\begin{bmatrix}h_{1,1}&h_{1,2}&h_{1,3}&\cdots &h_{1,n}\\h_{2,1}&h_{2,2}&h_{2,3}&\cdots &h_{2,n}\\0&h_{3,2}&h_{3,3}&\cdots &h_{3,n}\\\vdots &\ddots &\ddots &\ddots &\vdots \\\vdots &&0&h_{n,n-1}&h_{n,n}\\0&\cdots &\cdots &0&h_{n+1,n}\end{bmatrix}}}
1899:{\displaystyle H_{n}={\begin{bmatrix}h_{1,1}&h_{1,2}&h_{1,3}&\cdots &h_{1,n}\\h_{2,1}&h_{2,2}&h_{2,3}&\cdots &h_{2,n}\\0&h_{3,2}&h_{3,3}&\cdots &h_{3,n}\\\vdots &\ddots &\ddots &\ddots &\vdots \\0&\cdots &0&h_{n,n-1}&h_{n,n}\end{bmatrix}}.}
2751:
Due to practical storage consideration, common implementations of
Arnoldi methods typically restart after a fixed number of iterations. One approach is the Implicitly Restarted Arnoldi Method (IRAM) by Lehoucq and Sorensen, which was popularized in the free and open source software package
332:
2586:. Also Francis' algorithm itself can be considered to be related to power iterations, operating on nested Krylov subspace. In fact, the most basic form of Francis' algorithm appears to be to choose
2113:
2739:
1474:
798:
1986:
1951:
532:
384:
188:
444:
236:
224:
1507:
746:
2742:
Arnoldi iteration demonstrating convergence of Ritz values (red) to the eigenvalues (black) of a 400x400 matrix, composed of uniform random values on the domain
408:
118:
65:
The
Arnoldi method belongs to a class of linear algebra algorithms that give a partial result after a small number of iterations, in contrast to so-called
3034:
1479:
The orthogonalization method has to be specifically chosen such that the lower
Arnoldi/Krylov components are removed from higher Krylov vectors. As
3155:
3180:
3175:
3027:
2756:. Another approach is the Krylov-Schur Algorithm by G. W. Stewart, which is more stable and simpler to implement than IRAM.
2885:
2765:
813:
927:
One less than the dimension of the Krylov subspace, or equivalently the *degree* of the Krylov space. Must be >= 1.
3201:
3134:
3020:
2996:
2981:
2966:
2050:
3165:
3092:
2847:
R. B. Lehoucq & D. C. Sorensen (1996). "Deflation
Techniques for an Implicitly Restarted Arnoldi Iteration".
843:
1418:
3124:
2886:"ARPACK Users Guide: Solution of Large-Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods"
2578:
is a
Hessenberg matrix of modest size, its eigenvalues can be computed efficiently, for instance with the
2037:. This optimality problem has a unique solution if and only if the Arnoldi iteration does not break down.
751:
2947:
W. E. Arnoldi, "The principle of minimized iterations in the solution of the matrix eigenvalue problem,"
1960:
1925:
506:
358:
3078:
73:). The partial result in this case being the first few vectors of the basis the algorithm is building.
70:
3129:
2583:
1998:
3043:
346:
166:
327:{\displaystyle K_{n}={\begin{bmatrix}b&Ab&A^{2}b&\cdots &A^{n-1}b\end{bmatrix}}.}
455:
342:
2794:
2619:
It is often observed in practice that some of the Ritz eigenvalues converge to eigenvalues of
824:. In most applications of the Arnoldi iteration, including the eigenvalue algorithm below and
413:
193:
3088:
2648:
can be approximated. Typically, the Ritz eigenvalues converge to the largest eigenvalues of
1482:
3083:
2613:
2553:
724:
51:
31:
3005:
comes with ARPACK built-in. Both stored and implicit matrices can be analyzed through the
8:
3062:
2723:
However, the details are not fully understood yet. This is in contrast to the case where
190:. However, much potentially useful computation is wasted by using only the final result,
2834:
2795:"The principle of minimized iterations in the solution of the matrix eigenvalue problem"
939:
An m x (n + 1) array, where the columns are an orthonormal basis of the Krylov subspace.
393:
103:
20:
3006:
2911:
92:
An intuitive method for finding the largest (in absolute value) eigenvalue of a given
2992:
2977:
2962:
2931:
2816:
2732:
1396:
77:
3098:
2923:
2864:
2856:
2806:
2728:
2030:
47:
35:
3139:
900:"""Compute a basis of the (n + 1)-Krylov subspace of the matrix A.
351:
121:
55:
3057:
23:
2927:
2889:
2860:
3195:
3103:
2935:
2820:
81:
59:
3012:
2579:
125:
2954:
2556:
is to compute the eigenvalues in the Krylov subspace. The eigenvalues of
387:
160:
43:
2811:
2869:
2660:
should be used instead. This can be related to the characterization of
338:
39:
3119:
2605:. Improved versions include one or more shifts, and higher powers of
2738:
2716:(and thus the Ritz eigenvalues) will be close to the eigenvalues of
349:. The resulting set of vectors is thus an orthogonal basis of the
2883:
2989:
Preconditioned
Arnoldi Methods for Systems of Nonlinear Equations
2547:
163:
corresponding to the eigenvalue with the largest absolute value,
69:
which must complete to give any useful results (see for example,
1997:
can be characterized by the following optimality condition. The
800:. This ensures the orthogonality of all the generated vectors.
3170:
3160:
3002:
2753:
903:
This is the space spanned by the vectors {b, Ab, ..., A^n b}.
847:
825:
390:
good approximations of the eigenvectors corresponding to the
152:
normalizing the result after every application of the matrix
58:, which makes it particularly useful when dealing with large
2846:
945:
An (n + 1) x n array. A on basis Q. It is upper
Hessenberg.
87:
2669:
as the matrix whose characteristic polynomial minimizes ||
835:-loop takes one matrix-vector product and approximately 4
2976:, Society for Industrial and Applied Mathematics, 1997.
2837:
Washington State
University. Retrieved 14 December 2022
2731:. In that situation, the Arnoldi iteration becomes the
2155:
1576:
1337:
258:
2127:
2053:
1963:
1928:
1557:
1485:
1421:
754:
727:
509:
416:
396:
361:
239:
196:
169:
106:
76:
When applied to
Hermitian matrices it reduces to the
2884:
R. B. Lehoucq; D. C. Sorensen & C. Yang (1998).
226:. This suggests that instead, we form the so-called
2912:"A Krylov--Schur Algorithm for Large Eigenproblems"
2516:
2107:
1980:
1945:
1898:
1501:
1468:
792:
740:
526:
438:
402:
378:
326:
218:
182:
112:
1953:with the Arnoldi vectors as an orthogonal basis;
3193:
2916:SIAM Journal on Matrix Analysis and Applications
2849:SIAM Journal on Matrix Analysis and Applications
2959:Numerical Methods for Large Eigenvalue Problems
16:Iterative method for approximating eigenvectors
2746:
2548:Finding eigenvalues with the Arnoldi iteration
2108:{\displaystyle AQ_{n}=Q_{n+1}{\tilde {H}}_{n}}
2044:matrices in subsequent iterations is given by
1173:# Subtract the projections on previous vectors
458:to produce a sequence of orthonormal vectors,
410:largest eigenvalues, for the same reason that
386:. We may expect the vectors of this basis to
337:The columns of this matrix are not in general
3028:
1284:# Add the produced vector to the list, unless
828:, the algorithm has converged at this point.
3042:
54:by constructing an orthonormal basis of the
2684:|| in the following way. A good way to get
534:. Explicitly, the algorithm is as follows:
3035:
3021:
812:is the zero vector. This happens when the
2868:
2810:
2735:, for which the theory is more complete.
80:. The Arnoldi iteration was invented by
38:. Arnoldi finds an approximation to the
2737:
2644:eigenvalues, and not all eigenvalues of
2552:The idea of the Arnoldi iteration as an
2535:matrix formed by adding an extra row to
1526:by construction, they are orthogonal to
449:
88:Krylov subspaces and the power iteration
3166:Basic Linear Algebra Subprograms (BLAS)
2972:Lloyd N. Trefethen and David Bau, III,
2909:
2792:
446:approximates the dominant eigenvector.
3194:
1469:{\displaystyle H_{n}=Q_{n}^{*}AQ_{n}.}
124:: starting with an arbitrary initial
3016:
2961:, Manchester University Press, 1992.
2652:. To get the smallest eigenvalues of
2692:) small is to choose the polynomial
793:{\displaystyle q_{1},\dots ,q_{k-1}}
721:-loop projects out the component of
2766:generalized minimal residual method
1338:Properties of the Arnoldi iteration
1083:# Use it as the first Krylov vector
341:, but we can extract an orthogonal
13:
2609:may be applied in a single steps.
1981:{\displaystyle {\mathcal {K}}_{n}}
1967:
1946:{\displaystyle {\mathcal {K}}_{n}}
1932:
1308:# If that happens, stop iterating.
527:{\displaystyle {\mathcal {K}}_{n}}
513:
379:{\displaystyle {\mathcal {K}}_{n}}
365:
14:
3213:
2949:Quarterly of Applied Mathematics
1149:# Generate a new candidate vector
2799:Quarterly of Applied Mathematics
2768:(GMRES) is a method for solving
1957:is orthogonally projected onto
1399:) matrix formed by the numbers
803:The algorithm breaks down when
454:The Arnoldi iteration uses the
159:This sequence converges to the
34:and an important example of an
2951:, volume 9, pages 17–29, 1951.
2903:
2877:
2840:
2827:
2786:
2135:
2093:
347:Gram–Schmidt orthogonalization
1:
2779:
2656:, the inverse (operation) of
1509:can be expressed in terms of
456:modified Gram–Schmidt process
2776:based on Arnoldi iteration.
1038:# Normalize the input vector
842:In the programming language
183:{\displaystyle \lambda _{1}}
7:
2759:
2747:Restarted Arnoldi iteration
1412:computed by the algorithm:
1359:matrix formed by the first
839:floating point operations.
10:
3218:
3079:System of linear equations
2612:This is an example of the
921:Initial vector (length m).
71:Householder transformation
3148:
3130:Cache-oblivious algorithm
3112:
3071:
3050:
2928:10.1137/S0895479800371529
2861:10.1137/S0895479895281484
2601:to the full dimension of
2040:The relation between the
1999:characteristic polynomial
540:with an arbitrary vector
503:span the Krylov subspace
46:of general (possibly non-
3202:Numerical linear algebra
3181:General purpose software
3044:Numerical linear algebra
2974:Numerical Linear Algebra
852:
439:{\displaystyle A^{n-1}b}
219:{\displaystyle A^{n-1}b}
2910:Stewart, G. W. (2002).
2793:Arnoldi, W. E. (1951).
2582:, or somewhat related,
345:, via a method such as
2888:. SIAM. Archived from
2743:
2712:. Hence, the zeros of
2518:
2109:
1982:
1947:
1900:
1503:
1502:{\displaystyle Aq_{i}}
1470:
794:
742:
528:
483:, such that for every
440:
404:
380:
328:
220:
184:
114:
3176:Specialized libraries
3089:Matrix multiplication
3084:Matrix decompositions
2741:
2519:
2110:
1983:
1948:
1901:
1504:
1471:
795:
748:in the directions of
743:
741:{\displaystyle q_{k}}
529:
450:The Arnoldi iteration
441:
405:
381:
329:
221:
185:
115:
2708:is an eigenvalue of
2704:) is small whenever
2614:Rayleigh-Ritz method
2554:eigenvalue algorithm
2125:
2051:
1961:
1926:
1555:
1483:
1419:
942:h : numpy.array
936:Q : numpy.array
846:with support of the
752:
725:
507:
414:
394:
359:
237:
194:
167:
104:
32:eigenvalue algorithm
3063:Numerical stability
2987:Jaschke, Leonhard:
1449:
918:b : array_like
912:A : array_like
2835:Francis' Algorithm
2833:David S. Watkins.
2744:
2584:Francis' algorithm
2514:
2508:
2105:
1978:
1943:
1896:
1887:
1499:
1466:
1435:
948:"""
831:Every step of the
814:minimal polynomial
790:
738:
524:
479:, ..., called the
436:
400:
376:
324:
315:
216:
180:
110:
3189:
3188:
2812:10.1090/qam/42792
2733:Lanczos iteration
2640:, it has at most
2138:
2096:
2031:monic polynomials
1918:can be viewed as
870:arnoldi_iteration
672: := ‖
403:{\displaystyle n}
113:{\displaystyle A}
78:Lanczos algorithm
28:Arnoldi iteration
3209:
3099:Matrix splitting
3037:
3030:
3023:
3014:
3013:
3001:Implementation:
2940:
2939:
2907:
2901:
2900:
2898:
2897:
2881:
2875:
2874:
2872:
2844:
2838:
2831:
2825:
2824:
2814:
2790:
2597:, and extending
2567:Ritz eigenvalues
2523:
2521:
2520:
2515:
2513:
2512:
2505:
2504:
2459:
2458:
2441:
2440:
2413:
2377:
2376:
2354:
2353:
2336:
2335:
2311:
2310:
2288:
2287:
2270:
2269:
2252:
2251:
2232:
2231:
2209:
2208:
2191:
2190:
2173:
2172:
2146:
2145:
2140:
2139:
2131:
2114:
2112:
2111:
2106:
2104:
2103:
2098:
2097:
2089:
2085:
2084:
2066:
2065:
1987:
1985:
1984:
1979:
1977:
1976:
1971:
1970:
1952:
1950:
1949:
1944:
1942:
1941:
1936:
1935:
1922:in the subspace
1905:
1903:
1902:
1897:
1892:
1891:
1884:
1883:
1866:
1865:
1798:
1797:
1775:
1774:
1757:
1756:
1732:
1731:
1709:
1708:
1691:
1690:
1673:
1672:
1653:
1652:
1630:
1629:
1612:
1611:
1594:
1593:
1567:
1566:
1508:
1506:
1505:
1500:
1498:
1497:
1475:
1473:
1472:
1467:
1462:
1461:
1448:
1443:
1431:
1430:
1363:Arnoldi vectors
1333:
1330:
1327:
1324:
1321:
1318:
1315:
1312:
1309:
1306:
1303:
1300:
1297:
1294:
1291:
1288:
1285:
1282:
1279:
1276:
1273:
1270:
1267:
1264:
1261:
1258:
1255:
1252:
1249:
1246:
1243:
1240:
1237:
1234:
1231:
1228:
1225:
1222:
1219:
1216:
1213:
1210:
1207:
1204:
1201:
1198:
1195:
1192:
1189:
1186:
1183:
1180:
1177:
1174:
1171:
1168:
1165:
1162:
1159:
1156:
1153:
1150:
1147:
1144:
1141:
1138:
1135:
1132:
1129:
1126:
1123:
1120:
1117:
1114:
1111:
1108:
1105:
1102:
1099:
1096:
1093:
1090:
1087:
1084:
1081:
1078:
1075:
1072:
1069:
1066:
1063:
1060:
1057:
1054:
1051:
1048:
1045:
1042:
1039:
1036:
1033:
1030:
1027:
1024:
1021:
1018:
1015:
1012:
1009:
1006:
1003:
1000:
997:
994:
991:
988:
985:
982:
979:
976:
973:
970:
967:
964:
961:
958:
955:
952:
949:
946:
943:
940:
937:
934:
931:
928:
925:
922:
919:
916:
913:
910:
907:
904:
901:
898:
895:
892:
889:
886:
883:
880:
877:
874:
871:
868:
865:
862:
859:
856:
799:
797:
796:
791:
789:
788:
764:
763:
747:
745:
744:
739:
737:
736:
682:
533:
531:
530:
525:
523:
522:
517:
516:
445:
443:
442:
437:
432:
431:
409:
407:
406:
401:
385:
383:
382:
377:
375:
374:
369:
368:
333:
331:
330:
325:
320:
319:
309:
308:
283:
282:
249:
248:
225:
223:
222:
217:
212:
211:
189:
187:
186:
181:
179:
178:
151:
119:
117:
116:
111:
36:iterative method
3217:
3216:
3212:
3211:
3210:
3208:
3207:
3206:
3192:
3191:
3190:
3185:
3144:
3140:Multiprocessing
3108:
3104:Sparse problems
3067:
3046:
3041:
2944:
2943:
2908:
2904:
2895:
2893:
2882:
2878:
2845:
2841:
2832:
2828:
2791:
2787:
2782:
2762:
2749:
2683:
2668:
2631:
2596:
2590:to be equal to
2577:
2565:are called the
2564:
2550:
2543:
2507:
2506:
2488:
2484:
2482:
2477:
2472:
2467:
2461:
2460:
2448:
2444:
2442:
2424:
2420:
2418:
2412:
2406:
2405:
2400:
2395:
2390:
2385:
2379:
2378:
2366:
2362:
2360:
2355:
2343:
2339:
2337:
2325:
2321:
2319:
2313:
2312:
2300:
2296:
2294:
2289:
2277:
2273:
2271:
2259:
2255:
2253:
2241:
2237:
2234:
2233:
2221:
2217:
2215:
2210:
2198:
2194:
2192:
2180:
2176:
2174:
2162:
2158:
2151:
2150:
2141:
2130:
2129:
2128:
2126:
2123:
2122:
2099:
2088:
2087:
2086:
2074:
2070:
2061:
2057:
2052:
2049:
2048:
2028:
2024:
2009:
1996:
1972:
1966:
1965:
1964:
1962:
1959:
1958:
1937:
1931:
1930:
1929:
1927:
1924:
1923:
1917:
1886:
1885:
1873:
1869:
1867:
1849:
1845:
1843:
1838:
1833:
1827:
1826:
1821:
1816:
1811:
1806:
1800:
1799:
1787:
1783:
1781:
1776:
1764:
1760:
1758:
1746:
1742:
1740:
1734:
1733:
1721:
1717:
1715:
1710:
1698:
1694:
1692:
1680:
1676:
1674:
1662:
1658:
1655:
1654:
1642:
1638:
1636:
1631:
1619:
1615:
1613:
1601:
1597:
1595:
1583:
1579:
1572:
1571:
1562:
1558:
1556:
1553:
1552:
1544:
1535:
1525:
1515:
1493:
1489:
1484:
1481:
1480:
1457:
1453:
1444:
1439:
1426:
1422:
1420:
1417:
1416:
1411:
1394:
1385:
1376:
1369:
1350:
1340:
1335:
1334:
1331:
1328:
1325:
1322:
1319:
1316:
1313:
1310:
1307:
1304:
1301:
1298:
1295:
1292:
1289:
1286:
1283:
1280:
1277:
1274:
1271:
1268:
1265:
1262:
1259:
1256:
1253:
1250:
1247:
1244:
1241:
1238:
1235:
1232:
1229:
1226:
1223:
1220:
1217:
1214:
1211:
1208:
1205:
1202:
1199:
1196:
1193:
1190:
1187:
1184:
1181:
1178:
1175:
1172:
1169:
1166:
1163:
1160:
1157:
1154:
1151:
1148:
1145:
1142:
1139:
1136:
1133:
1130:
1127:
1124:
1121:
1118:
1115:
1112:
1109:
1106:
1103:
1100:
1097:
1094:
1091:
1088:
1085:
1082:
1079:
1076:
1073:
1070:
1067:
1064:
1061:
1058:
1055:
1052:
1049:
1046:
1043:
1040:
1037:
1034:
1031:
1028:
1025:
1022:
1019:
1016:
1013:
1010:
1007:
1004:
1001:
998:
995:
992:
989:
986:
983:
980:
977:
974:
971:
968:
965:
962:
959:
956:
953:
950:
947:
944:
941:
938:
935:
932:
929:
926:
923:
920:
917:
915:An m × m array.
914:
911:
908:
905:
902:
899:
896:
893:
890:
887:
884:
881:
878:
875:
872:
869:
866:
863:
860:
857:
854:
811:
778:
774:
759:
755:
753:
750:
749:
732:
728:
726:
723:
722:
715:
714:
700:
691:
681:
673:
671:
658:
650:
639:
630:
622:
614:
605:
575:
562:
546:
518:
512:
511:
510:
508:
505:
504:
502:
493:
481:Arnoldi vectors
478:
471:
464:
452:
421:
417:
415:
412:
411:
395:
392:
391:
370:
364:
363:
362:
360:
357:
356:
352:Krylov subspace
314:
313:
298:
294:
292:
287:
278:
274:
272:
264:
254:
253:
244:
240:
238:
235:
234:
201:
197:
195:
192:
191:
174:
170:
168:
165:
164:
132:
130:
122:power iteration
105:
102:
101:
90:
60:sparse matrices
56:Krylov subspace
17:
12:
11:
5:
3215:
3205:
3204:
3187:
3186:
3184:
3183:
3178:
3173:
3168:
3163:
3158:
3152:
3150:
3146:
3145:
3143:
3142:
3137:
3132:
3127:
3122:
3116:
3114:
3110:
3109:
3107:
3106:
3101:
3096:
3086:
3081:
3075:
3073:
3069:
3068:
3066:
3065:
3060:
3058:Floating point
3054:
3052:
3048:
3047:
3040:
3039:
3032:
3025:
3017:
3011:
3010:
2999:
2985:
2970:
2952:
2942:
2941:
2922:(3): 601–614.
2902:
2876:
2855:(4): 789–821.
2839:
2826:
2784:
2783:
2781:
2778:
2761:
2758:
2748:
2745:
2681:
2664:
2627:
2594:
2573:
2560:
2549:
2546:
2539:
2525:
2524:
2511:
2503:
2500:
2497:
2494:
2491:
2487:
2483:
2481:
2478:
2476:
2473:
2471:
2468:
2466:
2463:
2462:
2457:
2454:
2451:
2447:
2443:
2439:
2436:
2433:
2430:
2427:
2423:
2419:
2417:
2414:
2411:
2408:
2407:
2404:
2401:
2399:
2396:
2394:
2391:
2389:
2386:
2384:
2381:
2380:
2375:
2372:
2369:
2365:
2361:
2359:
2356:
2352:
2349:
2346:
2342:
2338:
2334:
2331:
2328:
2324:
2320:
2318:
2315:
2314:
2309:
2306:
2303:
2299:
2295:
2293:
2290:
2286:
2283:
2280:
2276:
2272:
2268:
2265:
2262:
2258:
2254:
2250:
2247:
2244:
2240:
2236:
2235:
2230:
2227:
2224:
2220:
2216:
2214:
2211:
2207:
2204:
2201:
2197:
2193:
2189:
2186:
2183:
2179:
2175:
2171:
2168:
2165:
2161:
2157:
2156:
2154:
2149:
2144:
2137:
2134:
2116:
2115:
2102:
2095:
2092:
2083:
2080:
2077:
2073:
2069:
2064:
2060:
2056:
2026:
2022:
2005:
1992:
1988:. The matrix
1975:
1969:
1940:
1934:
1913:
1907:
1906:
1895:
1890:
1882:
1879:
1876:
1872:
1868:
1864:
1861:
1858:
1855:
1852:
1848:
1844:
1842:
1839:
1837:
1834:
1832:
1829:
1828:
1825:
1822:
1820:
1817:
1815:
1812:
1810:
1807:
1805:
1802:
1801:
1796:
1793:
1790:
1786:
1782:
1780:
1777:
1773:
1770:
1767:
1763:
1759:
1755:
1752:
1749:
1745:
1741:
1739:
1736:
1735:
1730:
1727:
1724:
1720:
1716:
1714:
1711:
1707:
1704:
1701:
1697:
1693:
1689:
1686:
1683:
1679:
1675:
1671:
1668:
1665:
1661:
1657:
1656:
1651:
1648:
1645:
1641:
1637:
1635:
1632:
1628:
1625:
1622:
1618:
1614:
1610:
1607:
1604:
1600:
1596:
1592:
1589:
1586:
1582:
1578:
1577:
1575:
1570:
1565:
1561:
1540:
1530:
1520:
1513:
1496:
1492:
1488:
1477:
1476:
1465:
1460:
1456:
1452:
1447:
1442:
1438:
1434:
1429:
1425:
1403:
1395:be the (upper
1390:
1381:
1374:
1367:
1346:
1339:
1336:
853:
807:
787:
784:
781:
777:
773:
770:
767:
762:
758:
735:
731:
705:
696:
687:
677:
662:
654:
641:
635:
626:
618:
610:
596:
570:
558:
554:= 2, 3, ...
544:
536:
521:
515:
498:
491:
487:, the vectors
476:
469:
462:
451:
448:
435:
430:
427:
424:
420:
399:
373:
367:
335:
334:
323:
318:
312:
307:
304:
301:
297:
293:
291:
288:
286:
281:
277:
273:
271:
268:
265:
263:
260:
259:
257:
252:
247:
243:
215:
210:
207:
204:
200:
177:
173:
128:
109:
89:
86:
67:direct methods
24:linear algebra
15:
9:
6:
4:
3:
2:
3214:
3203:
3200:
3199:
3197:
3182:
3179:
3177:
3174:
3172:
3169:
3167:
3164:
3162:
3159:
3157:
3154:
3153:
3151:
3147:
3141:
3138:
3136:
3133:
3131:
3128:
3126:
3123:
3121:
3118:
3117:
3115:
3111:
3105:
3102:
3100:
3097:
3094:
3090:
3087:
3085:
3082:
3080:
3077:
3076:
3074:
3070:
3064:
3061:
3059:
3056:
3055:
3053:
3049:
3045:
3038:
3033:
3031:
3026:
3024:
3019:
3018:
3015:
3008:
3004:
3000:
2998:
2997:2-84976-001-3
2994:
2990:
2986:
2983:
2982:0-89871-361-7
2979:
2975:
2971:
2968:
2967:0-7190-3386-1
2964:
2960:
2956:
2953:
2950:
2946:
2945:
2937:
2933:
2929:
2925:
2921:
2917:
2913:
2906:
2892:on 2007-06-26
2891:
2887:
2880:
2871:
2866:
2862:
2858:
2854:
2850:
2843:
2836:
2830:
2822:
2818:
2813:
2808:
2804:
2800:
2796:
2789:
2785:
2777:
2775:
2771:
2767:
2757:
2755:
2740:
2736:
2734:
2730:
2726:
2721:
2719:
2715:
2711:
2707:
2703:
2699:
2695:
2691:
2687:
2680:
2676:
2672:
2667:
2663:
2659:
2655:
2651:
2647:
2643:
2639:
2635:
2630:
2626:
2622:
2617:
2615:
2610:
2608:
2604:
2600:
2593:
2589:
2585:
2581:
2576:
2572:
2568:
2563:
2559:
2555:
2545:
2542:
2538:
2534:
2530:
2509:
2501:
2498:
2495:
2492:
2489:
2485:
2479:
2474:
2469:
2464:
2455:
2452:
2449:
2445:
2437:
2434:
2431:
2428:
2425:
2421:
2415:
2409:
2402:
2397:
2392:
2387:
2382:
2373:
2370:
2367:
2363:
2357:
2350:
2347:
2344:
2340:
2332:
2329:
2326:
2322:
2316:
2307:
2304:
2301:
2297:
2291:
2284:
2281:
2278:
2274:
2266:
2263:
2260:
2256:
2248:
2245:
2242:
2238:
2228:
2225:
2222:
2218:
2212:
2205:
2202:
2199:
2195:
2187:
2184:
2181:
2177:
2169:
2166:
2163:
2159:
2152:
2147:
2142:
2132:
2121:
2120:
2119:
2100:
2090:
2081:
2078:
2075:
2071:
2067:
2062:
2058:
2054:
2047:
2046:
2045:
2043:
2038:
2036:
2032:
2021:
2017:
2013:
2008:
2004:
2000:
1995:
1991:
1973:
1956:
1938:
1921:
1916:
1912:
1893:
1888:
1880:
1877:
1874:
1870:
1862:
1859:
1856:
1853:
1850:
1846:
1840:
1835:
1830:
1823:
1818:
1813:
1808:
1803:
1794:
1791:
1788:
1784:
1778:
1771:
1768:
1765:
1761:
1753:
1750:
1747:
1743:
1737:
1728:
1725:
1722:
1718:
1712:
1705:
1702:
1699:
1695:
1687:
1684:
1681:
1677:
1669:
1666:
1663:
1659:
1649:
1646:
1643:
1639:
1633:
1626:
1623:
1620:
1616:
1608:
1605:
1602:
1598:
1590:
1587:
1584:
1580:
1573:
1568:
1563:
1559:
1551:
1550:
1549:
1548:We then have
1546:
1543:
1539:
1533:
1529:
1523:
1519:
1512:
1494:
1490:
1486:
1463:
1458:
1454:
1450:
1445:
1440:
1436:
1432:
1427:
1423:
1415:
1414:
1413:
1410:
1406:
1402:
1398:
1393:
1389:
1384:
1380:
1373:
1366:
1362:
1358:
1354:
1349:
1345:
851:
849:
845:
840:
838:
834:
829:
827:
823:
820:is of degree
819:
815:
810:
806:
801:
785:
782:
779:
775:
771:
768:
765:
760:
756:
733:
729:
720:
712:
708:
704:
699:
695:
690:
686:
680:
676:
669:
665:
661:
657:
653:
648:
644:
638:
634:
629:
625:
621:
617:
613:
609:
603:
599:
595:
591:
588:
584:
581:
578:
573:
569:
566:
561:
557:
553:
550:
547:with norm 1.
543:
539:
535:
519:
501:
497:
490:
486:
482:
475:
468:
461:
457:
447:
433:
428:
425:
422:
418:
397:
389:
371:
354:
353:
348:
344:
340:
321:
316:
310:
305:
302:
299:
295:
289:
284:
279:
275:
269:
266:
261:
255:
250:
245:
241:
233:
232:
231:
229:
228:Krylov matrix
213:
208:
205:
202:
198:
175:
171:
162:
157:
155:
149:
146:
142:
139:
135:
127:
123:
107:
99:
95:
85:
83:
82:W. E. Arnoldi
79:
74:
72:
68:
63:
61:
57:
53:
49:
45:
41:
37:
33:
29:
25:
22:
3051:Key concepts
2988:
2973:
2958:
2948:
2919:
2915:
2905:
2894:. Retrieved
2890:the original
2879:
2852:
2848:
2842:
2829:
2805:(1): 17–29.
2802:
2798:
2788:
2773:
2769:
2763:
2750:
2724:
2722:
2717:
2713:
2709:
2705:
2701:
2697:
2693:
2689:
2685:
2678:
2674:
2670:
2665:
2661:
2657:
2653:
2649:
2645:
2641:
2637:
2633:
2628:
2624:
2620:
2618:
2611:
2606:
2602:
2598:
2591:
2587:
2580:QR algorithm
2574:
2570:
2566:
2561:
2557:
2551:
2540:
2536:
2532:
2528:
2526:
2117:
2041:
2039:
2034:
2019:
2015:
2011:
2010:minimizes ||
2006:
2002:
1993:
1989:
1954:
1919:
1914:
1910:
1908:
1547:
1541:
1537:
1531:
1527:
1521:
1517:
1510:
1478:
1408:
1404:
1400:
1391:
1387:
1382:
1378:
1371:
1364:
1360:
1356:
1352:
1347:
1343:
1341:
924:n : int
841:
836:
832:
830:
821:
817:
808:
804:
802:
718:
716:
710:
706:
702:
697:
693:
688:
684:
678:
674:
667:
663:
659:
655:
651:
646:
642:
636:
632:
627:
623:
619:
615:
611:
607:
601:
597:
593:
589:
586:
582:
579:
576:
571:
567:
564:
559:
555:
551:
548:
541:
537:
499:
495:
488:
484:
480:
473:
466:
459:
453:
350:
336:
227:
158:
153:
147:
144:
140:
137:
133:
131:, calculate
97:
93:
91:
75:
66:
64:
44:eigenvectors
27:
18:
2955:Yousef Saad
2870:1911/101832
1909:The matrix
1351:denote the
683:‖
161:eigenvector
40:eigenvalues
3093:algorithms
2991:. (2004).
2896:2007-06-30
2780:References
2696:such that
2033:of degree
2029:among all
1397:Hessenberg
1386:, and let
909:----------
906:Parameters
606: :=
549:Repeat for
339:orthogonal
3120:CPU cache
3009:function.
2936:0895-4798
2821:0033-569X
2729:Hermitian
2475:⋯
2470:⋯
2435:−
2410:⋮
2403:⋮
2398:⋱
2393:⋱
2388:⋱
2383:⋮
2358:⋯
2292:⋯
2213:⋯
2136:~
2094:~
1860:−
1836:⋯
1824:⋮
1819:⋱
1814:⋱
1809:⋱
1804:⋮
1779:⋯
1713:⋯
1634:⋯
1446:∗
850:library:
783:−
769:…
692: :=
631: :=
563: :=
426:−
303:−
290:⋯
206:−
172:λ
84:in 1951.
48:Hermitian
21:numerical
3196:Category
3149:Software
3113:Hardware
3072:Problems
2760:See also
2623:. Since
2569:. Since
592:− 1
52:matrices
2531:+1)-by-
2527:is an (
1536:, ...,
1516:, ...,
1377:, ...,
933:-------
930:Returns
494:, ...,
120:is the
100:matrix
3171:LAPACK
3161:MATLAB
3007:eigs()
3003:Matlab
2995:
2980:
2965:
2934:
2819:
2754:ARPACK
2118:where
1323:return
1311:return
1245:linalg
1059:linalg
855:import
844:Python
126:vector
30:is an
26:, the
3156:ATLAS
1161:range
1095:range
1020:shape
1008:zeros
972:zeros
957:1e-12
858:numpy
848:NumPy
826:GMRES
538:Start
343:basis
150:, ...
3135:SIMD
2993:ISBN
2978:ISBN
2963:ISBN
2932:ISSN
2817:ISSN
2764:The
2636:-by-
1355:-by-
1342:Let
1302:else
1275:>
1251:norm
1200:conj
1065:norm
717:The
583:from
388:span
42:and
3125:TLB
2924:doi
2865:hdl
2857:doi
2807:doi
2727:is
2632:is
2001:of
1545:,
1278:eps
1203:(),
1188:dot
1152:for
1131:dot
1086:for
951:eps
894:int
867:def
816:of
640:− h
577:for
156:.
19:In
3198::
2957:,
2930:.
2920:23
2918:.
2914:.
2863:.
2853:17
2851:.
2815:.
2801:.
2797:.
2772:=
2770:Ax
2720:.
2616:.
2592:Ae
2544:.
2025:||
1534:+2
1524:+1
1370:,
1269:if
1239:np
1182:np
1170:):
1158:in
1125:np
1116:):
1092:in
1053:np
1035:))
1011:((
1002:np
993:))
975:((
966:np
897:):
864:np
861:as
837:mk
713:−1
701:/
670:−1
649:−1
604:−1
587:to
585:1
574:−1
472:,
465:,
355:,
230::
143:,
136:,
134:Ab
96:×
62:.
50:)
3095:)
3091:(
3036:e
3029:t
3022:v
2984:.
2969:.
2938:.
2926::
2899:.
2873:.
2867::
2859::
2823:.
2809::
2803:9
2774:b
2725:A
2718:A
2714:p
2710:A
2706:x
2702:x
2700:(
2698:p
2694:p
2690:A
2688:(
2686:p
2682:1
2679:q
2677:)
2675:A
2673:(
2671:p
2666:n
2662:H
2658:A
2654:A
2650:A
2646:A
2642:n
2638:n
2634:n
2629:n
2625:H
2621:A
2607:A
2603:A
2599:n
2595:1
2588:b
2575:n
2571:H
2562:n
2558:H
2541:n
2537:H
2533:n
2529:n
2510:]
2502:n
2499:,
2496:1
2493:+
2490:n
2486:h
2480:0
2465:0
2456:n
2453:,
2450:n
2446:h
2438:1
2432:n
2429:,
2426:n
2422:h
2416:0
2374:n
2371:,
2368:3
2364:h
2351:3
2348:,
2345:3
2341:h
2333:2
2330:,
2327:3
2323:h
2317:0
2308:n
2305:,
2302:2
2298:h
2285:3
2282:,
2279:2
2275:h
2267:2
2264:,
2261:2
2257:h
2249:1
2246:,
2243:2
2239:h
2229:n
2226:,
2223:1
2219:h
2206:3
2203:,
2200:1
2196:h
2188:2
2185:,
2182:1
2178:h
2170:1
2167:,
2164:1
2160:h
2153:[
2148:=
2143:n
2133:H
2101:n
2091:H
2082:1
2079:+
2076:n
2072:Q
2068:=
2063:n
2059:Q
2055:A
2042:Q
2035:n
2027:2
2023:1
2020:q
2018:)
2016:A
2014:(
2012:p
2007:n
2003:H
1994:n
1990:H
1974:n
1968:K
1955:A
1939:n
1933:K
1920:A
1915:n
1911:H
1894:.
1889:]
1881:n
1878:,
1875:n
1871:h
1863:1
1857:n
1854:,
1851:n
1847:h
1841:0
1831:0
1795:n
1792:,
1789:3
1785:h
1772:3
1769:,
1766:3
1762:h
1754:2
1751:,
1748:3
1744:h
1738:0
1729:n
1726:,
1723:2
1719:h
1706:3
1703:,
1700:2
1696:h
1688:2
1685:,
1682:2
1678:h
1670:1
1667:,
1664:2
1660:h
1650:n
1647:,
1644:1
1640:h
1627:3
1624:,
1621:1
1617:h
1609:2
1606:,
1603:1
1599:h
1591:1
1588:,
1585:1
1581:h
1574:[
1569:=
1564:n
1560:H
1542:n
1538:q
1532:i
1528:q
1522:i
1518:q
1514:1
1511:q
1495:i
1491:q
1487:A
1464:.
1459:n
1455:Q
1451:A
1441:n
1437:Q
1433:=
1428:n
1424:H
1409:k
1407:,
1405:j
1401:h
1392:n
1388:H
1383:n
1379:q
1375:2
1372:q
1368:1
1365:q
1361:n
1357:n
1353:m
1348:n
1344:Q
1332:h
1329:,
1326:Q
1320:h
1317:,
1314:Q
1305::
1299:h
1296:/
1293:v
1290:=
1287:Q
1281::
1272:h
1266:)
1263:2
1260:,
1257:v
1254:(
1248:.
1242:.
1236:=
1233:h
1230:Q
1227:*
1224:h
1221:-
1218:v
1215:=
1212:v
1209:)
1206:v
1197:.
1194:Q
1191:(
1185:.
1179:=
1176:h
1167:k
1164:(
1155:j
1146:)
1143:Q
1140:,
1137:A
1134:(
1128:.
1122:=
1119:v
1113:1
1110:+
1107:n
1104:,
1101:1
1098:(
1089:k
1080:)
1077:2
1074:,
1071:b
1068:(
1062:.
1056:.
1050:/
1047:b
1044:=
1041:Q
1032:1
1029:+
1026:n
1023:,
1017:.
1014:A
1005:.
999:=
996:Q
990:n
987:,
984:1
981:+
978:n
969:.
963:=
960:h
954:=
891::
888:n
885:,
882:b
879:,
876:A
873:(
833:k
822:k
818:A
809:k
805:q
786:1
780:k
776:q
772:,
766:,
761:1
757:q
734:k
730:q
719:j
711:k
709:,
707:k
703:h
698:k
694:q
689:k
685:q
679:k
675:q
668:k
666:,
664:k
660:h
656:j
652:q
647:k
645:,
643:j
637:k
633:q
628:k
624:q
620:k
616:q
612:j
608:q
602:k
600:,
598:j
594:h
590:k
580:j
572:k
568:q
565:A
560:k
556:q
552:k
545:1
542:q
520:n
514:K
500:n
496:q
492:1
489:q
485:n
477:3
474:q
470:2
467:q
463:1
460:q
434:b
429:1
423:n
419:A
398:n
372:n
366:K
322:.
317:]
311:b
306:1
300:n
296:A
285:b
280:2
276:A
270:b
267:A
262:b
256:[
251:=
246:n
242:K
214:b
209:1
203:n
199:A
176:1
154:A
148:b
145:A
141:b
138:A
129:b
108:A
98:m
94:m
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.