Derivation of the conjugate gradient method

11759: 11082: 4797: 4197: 11754:{\displaystyle {\begin{aligned}{\boldsymbol {r}}_{i}&={\boldsymbol {b}}-{\boldsymbol {Ax}}_{i}\\&={\boldsymbol {b}}-{\boldsymbol {A}}({\boldsymbol {x}}_{0}+{\boldsymbol {V}}_{i}{\boldsymbol {y}}_{i})\\&={\boldsymbol {r}}_{0}-{\boldsymbol {AV}}_{i}{\boldsymbol {y}}_{i}\\&={\boldsymbol {r}}_{0}-{\boldsymbol {V}}_{i+1}{\boldsymbol {\tilde {H}}}_{i}{\boldsymbol {y}}_{i}\\&={\boldsymbol {r}}_{0}-{\boldsymbol {V}}_{i}{\boldsymbol {H}}_{i}{\boldsymbol {y}}_{i}-h_{i+1,i}({\boldsymbol {e}}_{i}^{\mathrm {T} }{\boldsymbol {y}}_{i}){\boldsymbol {v}}_{i+1}\\&=\lVert {\boldsymbol {r}}_{0}\rVert _{2}{\boldsymbol {v}}_{1}-{\boldsymbol {V}}_{i}(\lVert {\boldsymbol {r}}_{0}\rVert _{2}{\boldsymbol {e}}_{1})-h_{i+1,i}({\boldsymbol {e}}_{i}^{\mathrm {T} }{\boldsymbol {y}}_{i}){\boldsymbol {v}}_{i+1}\\&=-h_{i+1,i}({\boldsymbol {e}}_{i}^{\mathrm {T} }{\boldsymbol {y}}_{i}){\boldsymbol {v}}_{i+1}{\text{.}}\end{aligned}}} 4792:{\displaystyle {\begin{aligned}&\mathbf {r} _{0}:=\mathbf {b} -\mathbf {Ax} _{0}\\&\mathbf {p} _{0}:=\mathbf {r} _{0}\\&k:=0\\&{\text{do while }}k<n\\&\qquad \alpha _{k}:={\frac {\mathbf {p} _{k}^{\mathsf {T}}\mathbf {r} _{k}}{\mathbf {p} _{k}^{\mathsf {T}}\mathbf {Ap} _{k}}}\\&\qquad \mathbf {x} _{k+1}:=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}\\&\qquad {\text{if }}|\alpha _{k}|{\text{ is sufficiently small, then exit loop}}\\&\qquad \mathbf {r} _{k+1}:=\mathbf {r} _{k}-\alpha _{k}\mathbf {Ap} _{k}\\&\qquad \mathbf {p} _{k+1}:={\boldsymbol {r}}_{k+1}-\sum _{i=0}^{k}{\frac {{\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ar}}_{k+1}}{{\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ap}}_{i}}}{\boldsymbol {p}}_{i}\\&\qquad k:=k+1\\&{\text{return }}\mathbf {x} _{k+1}{\text{ as the result}}\end{aligned}}} 7657: 7166: 13341: 12814: 12171: 7652:{\displaystyle {\begin{aligned}{\boldsymbol {V}}_{i}&={\begin{bmatrix}{\boldsymbol {v}}_{1}&{\boldsymbol {v}}_{2}&\cdots &{\boldsymbol {v}}_{i}\end{bmatrix}}{\text{,}}\\{\boldsymbol {\tilde {H}}}_{i}&={\begin{bmatrix}h_{11}&h_{12}&h_{13}&\cdots &h_{1,i}\\h_{21}&h_{22}&h_{23}&\cdots &h_{2,i}\\&h_{32}&h_{33}&\cdots &h_{3,i}\\&&\ddots &\ddots &\vdots \\&&&h_{i,i-1}&h_{i,i}\\&&&&h_{i+1,i}\end{bmatrix}}={\begin{bmatrix}{\boldsymbol {H}}_{i}\\h_{i+1,i}{\boldsymbol {e}}_{i}^{\mathrm {T} }\end{bmatrix}}\end{aligned}}} 12993: 9511: 12488: 11850: 265: 1181: 13336:{\displaystyle {\begin{aligned}\beta _{i}&=-{\frac {{\boldsymbol {r}}_{i+1}^{\mathrm {T} }{\boldsymbol {Ap}}_{i}}{{\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ap}}_{i}}}\\&=-{\frac {{\boldsymbol {r}}_{i+1}^{\mathrm {T} }({\boldsymbol {r}}_{i}-{\boldsymbol {r}}_{i+1})}{\alpha _{i}{\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ap}}_{i}}}\\&={\frac {{\boldsymbol {r}}_{i+1}^{\mathrm {T} }{\boldsymbol {r}}_{i+1}}{{\boldsymbol {r}}_{i}^{\mathrm {T} }{\boldsymbol {r}}_{i}}}{\text{.}}\end{aligned}}} 9213: 12809:{\displaystyle {\begin{aligned}\alpha _{i}&={\frac {{\boldsymbol {r}}_{i}^{\mathrm {T} }{\boldsymbol {r}}_{i}}{{\boldsymbol {r}}_{i}^{\mathrm {T} }{\boldsymbol {Ap}}_{i}}}\\&={\frac {{\boldsymbol {r}}_{i}^{\mathrm {T} }{\boldsymbol {r}}_{i}}{({\boldsymbol {p}}_{i}-\beta _{i-1}{\boldsymbol {p}}_{i-1})^{\mathrm {T} }{\boldsymbol {Ap}}_{i}}}\\&={\frac {{\boldsymbol {r}}_{i}^{\mathrm {T} }{\boldsymbol {r}}_{i}}{{\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ap}}_{i}}}{\text{.}}\end{aligned}}} 8868: 12166:{\displaystyle {\begin{aligned}{\boldsymbol {P}}_{i}^{\mathrm {T} }{\boldsymbol {AP}}_{i}&={\boldsymbol {U}}_{i}^{-\mathrm {T} }{\boldsymbol {V}}_{i}^{\mathrm {T} }{\boldsymbol {AV}}_{i}{\boldsymbol {U}}_{i}^{-1}\\&={\boldsymbol {U}}_{i}^{-\mathrm {T} }{\boldsymbol {H}}_{i}{\boldsymbol {U}}_{i}^{-1}\\&={\boldsymbol {U}}_{i}^{-\mathrm {T} }{\boldsymbol {L}}_{i}{\boldsymbol {U}}_{i}{\boldsymbol {U}}_{i}^{-1}\\&={\boldsymbol {U}}_{i}^{-\mathrm {T} }{\boldsymbol {L}}_{i}\end{aligned}}} 10672: 1642: 10362: 926: 9506:{\displaystyle {\begin{aligned}{\boldsymbol {x}}_{i}&={\boldsymbol {x}}_{0}+{\boldsymbol {V}}_{i}{\boldsymbol {H}}_{i}^{-1}(\lVert {\boldsymbol {r}}_{0}\rVert _{2}{\boldsymbol {e}}_{1})\\&={\boldsymbol {x}}_{0}+{\boldsymbol {V}}_{i}{\boldsymbol {U}}_{i}^{-1}{\boldsymbol {L}}_{i}^{-1}(\lVert {\boldsymbol {r}}_{0}\rVert _{2}{\boldsymbol {e}}_{1})\\&={\boldsymbol {x}}_{0}+{\boldsymbol {P}}_{i}{\boldsymbol {z}}_{i}\end{aligned}}} 8582: 6901: 10410: 9868: 9689: 7862: 1420: 10140: 1176:{\displaystyle {\begin{aligned}\alpha _{i}&={\frac {{\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {r}}_{i}}{{\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ap}}_{i}}}{\text{,}}\\{\boldsymbol {x}}_{i+1}&={\boldsymbol {x}}_{i}+\alpha _{i}{\boldsymbol {p}}_{i}{\text{,}}\\{\boldsymbol {r}}_{i+1}&={\boldsymbol {r}}_{i}-\alpha _{i}{\boldsymbol {Ap}}_{i}\end{aligned}}} 3822: 8451: 4192: 3583: 5693: 8863:{\displaystyle {\boldsymbol {H}}_{i}={\boldsymbol {L}}_{i}{\boldsymbol {U}}_{i}={\begin{bmatrix}1\\c_{2}&1\\&\ddots &\ddots \\&&c_{i-1}&1\\&&&c_{i}&1\end{bmatrix}}{\begin{bmatrix}d_{1}&b_{2}\\&d_{2}&b_{3}\\&&\ddots &\ddots \\&&&d_{i-1}&b_{i}\\&&&&d_{i}\end{bmatrix}}} 3395: 9131: 2368: 6692: 10100: 10886: 10667:{\displaystyle {\begin{aligned}{\boldsymbol {x}}_{i}&={\boldsymbol {x}}_{i-1}+\alpha _{i-1}{\boldsymbol {p}}_{i-1}{\text{,}}\\{\boldsymbol {r}}_{i}&={\boldsymbol {r}}_{i-1}-\alpha _{i-1}{\boldsymbol {Ap}}_{i-1}{\text{,}}\\{\boldsymbol {p}}_{i}&={\boldsymbol {r}}_{i}+\beta _{i-1}{\boldsymbol {p}}_{i-1}{\text{.}}\end{aligned}}} 9700: 670: 1254: 6607: 9522: 5865: 7668: 6081: 10357:{\displaystyle {\begin{aligned}{\boldsymbol {x}}_{i}&={\boldsymbol {x}}_{0}+{\boldsymbol {P}}_{i}{\boldsymbol {z}}_{i}\\&={\boldsymbol {x}}_{0}+{\boldsymbol {P}}_{i-1}{\boldsymbol {z}}_{i-1}+\zeta _{i}{\boldsymbol {p}}_{i}\\&={\boldsymbol {x}}_{i-1}+\zeta _{i}{\boldsymbol {p}}_{i}{\text{.}}\end{aligned}}} 12985: 6335: 12480: 251: 3635: 1593:

are not picked well, then progress will be slow. In particular, the gradient descent method would be slow. This can be seen in the diagram, where the green line is the result of always picking the local gradient direction. It zig-zags towards the minimum, but repeatedly overshoots. In contrast, if we

8244: 701:

on some ellipsoid, then choose a direction and travel along that direction, until we hit the point where the ellipsoid is minimized in that direction. This is not necessarily the minimum, but it is progress towards it. Visually, it is moving along a line, and stopping as soon as we reach a point

4035: 3432: 5530: 2173: 3265: 2071: 553: 345: 8933: 6896:{\displaystyle {\boldsymbol {v}}_{i}={\begin{cases}{\boldsymbol {r}}_{0}&{\text{if }}i=1{\text{,}}\\{\boldsymbol {Av}}_{i-1}-\sum _{j=1}^{i-1}({\boldsymbol {v}}_{j}^{\mathrm {T} }{\boldsymbol {Av}}_{i-1}){\boldsymbol {v}}_{j}&{\text{if }}i>1{\text{.}}\end{cases}}} 6186: 1661:

The concept of conjugate directions came from classical geometry of ellipse. For an ellipse, two semi-axes center are mutually conjugate with respect to the ellipse iff the lines are parallel to the tangent bounding parallelogram, as pictured. The concept generalizes to

9935: 8044: 10767: 9863:{\displaystyle {\begin{aligned}{\boldsymbol {P}}_{i}&={\begin{bmatrix}{\boldsymbol {P}}_{i-1}&{\boldsymbol {p}}_{i}\end{bmatrix}}{\text{,}}\\{\boldsymbol {z}}_{i}&={\begin{bmatrix}{\boldsymbol {z}}_{i-1}\\\zeta _{i}\end{bmatrix}}{\text{.}}\end{aligned}}} 5954: 9684:{\displaystyle {\begin{aligned}{\boldsymbol {P}}_{i}&={\boldsymbol {V}}_{i}{\boldsymbol {U}}_{i}^{-1}{\text{,}}\\{\boldsymbol {z}}_{i}&={\boldsymbol {L}}_{i}^{-1}(\lVert {\boldsymbol {r}}_{0}\rVert _{2}{\boldsymbol {e}}_{1}){\text{.}}\end{aligned}}} 6476: 7857:{\displaystyle h_{ji}={\begin{cases}{\boldsymbol {v}}_{j}^{\mathrm {T} }{\boldsymbol {Av}}_{i}&{\text{if }}j\leq i{\text{,}}\\\lVert {\boldsymbol {w}}_{i+1}\rVert _{2}&{\text{if }}j=i+1{\text{,}}\\0&{\text{if }}j>i+1{\text{.}}\end{cases}}} 5703: 1415:{\displaystyle {\boldsymbol {r}}_{i+1}={\boldsymbol {b}}-{\boldsymbol {Ax}}_{i+1}={\boldsymbol {b}}-{\boldsymbol {A}}({\boldsymbol {x}}_{i}+\alpha _{i}{\boldsymbol {p}}_{i})={\boldsymbol {r}}_{i}-\alpha _{i}{\boldsymbol {A}}{\boldsymbol {p}}_{i}} 9205: 8115: 12851: 6684: 6191: 12355: 11048: 8236: 7077: 6465: 3817:{\displaystyle {\boldsymbol {p}}_{n-1}={\boldsymbol {p}}_{n-1,0}-\sum _{i=0}^{n-2}{\frac {{\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ap}}_{n-1,0}}{{\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ap}}_{i}}}{\boldsymbol {p}}_{i}} 7155: 772: 168: 2143: 5519: 2519: 1591: 1518: 1249: 8446:{\displaystyle {\boldsymbol {H}}_{i}={\begin{bmatrix}a_{1}&b_{2}\\b_{2}&a_{2}&b_{3}\\&\ddots &\ddots &\ddots \\&&b_{i-1}&a_{i-1}&b_{i}\\&&&b_{i}&a_{i}\end{bmatrix}}{\text{.}}} 4030: 4187:{\displaystyle {\boldsymbol {p}}_{k}={\boldsymbol {r}}_{k}-\sum _{i=0}^{k-1}{\frac {{\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ar}}_{k}}{{\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ap}}_{i}}}{\boldsymbol {p}}_{i}} 3578:{\displaystyle {\boldsymbol {p}}_{2}={\boldsymbol {p}}_{20}-\sum _{i=0}^{1}{\frac {{\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ap}}_{20}}{{\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ap}}_{i}}}{\boldsymbol {p}}_{i}} 5688:{\displaystyle \mathbf {p} _{k}:={\boldsymbol {r}}_{k}-\sum _{i=0}^{k-1}{\frac {{\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ar}}_{k-1}}{{\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ap}}_{i}}}{\boldsymbol {p}}_{i}} 5949: 1750: 7920: 2004: 918: 278: 2425: 5436: 5365: 5197: 3165: 3085: 11842: 2953: 2869: 2817: 2735: 2683: 2631: 548: 5294: 5091: 5023: 3923: 3390:{\displaystyle {\boldsymbol {p}}_{1}={\boldsymbol {p}}_{10}-{\frac {{\boldsymbol {p}}_{0}^{\mathrm {T} }{\boldsymbol {Ap}}_{10}}{{\boldsymbol {p}}_{0}^{\mathrm {T} }{\boldsymbol {Ap}}_{0}}}{\boldsymbol {p}}_{0}} 9126:{\displaystyle {\begin{aligned}c_{i}&=b_{i}/d_{i-1}{\text{,}}\\d_{i}&={\begin{cases}a_{1}&{\text{if }}i=1{\text{,}}\\a_{i}-c_{i}b_{i}&{\text{if }}i>1{\text{.}}\end{cases}}\end{aligned}}} 1996: 1821: 6090: 10095:{\displaystyle {\begin{aligned}{\boldsymbol {p}}_{i}&={\frac {1}{d_{i}}}({\boldsymbol {v}}_{i}-b_{i}{\boldsymbol {p}}_{i-1}){\text{,}}\\\zeta _{i}&=-c_{i}\zeta _{i-1}{\text{.}}\end{aligned}}} 2363:{\displaystyle (t_{i}{\boldsymbol {p}}_{i}+{\boldsymbol {p}}_{j}dt_{j})^{\mathrm {T} }{\boldsymbol {A}}(t_{i}{\boldsymbol {p}}_{i}+{\boldsymbol {p}}_{j}dt_{j})=C'+O(dt_{j}^{2}),\quad \forall i\neq j} 10881:{\displaystyle {\begin{aligned}{\boldsymbol {r}}_{i}^{\mathrm {T} }{\boldsymbol {r}}_{j}&=0{\text{,}}\\{\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ap}}_{j}&=0{\text{.}}\end{aligned}}} 7954: 271:

Geometrically, the quadratic function can be equivalently presented by writing down its value at every point in space. The points of equal value make up its contour surfaces, which are concentric

65: 12998: 12493: 11855: 11087: 10772: 10415: 10145: 9940: 9705: 9527: 9218: 8938: 7171: 4942: 4202: 931: 1868: 665:{\displaystyle \alpha _{0}={\frac {{\boldsymbol {p}}_{0}^{\mathrm {T} }({\boldsymbol {b}}-{\boldsymbol {Ax}}_{0})}{{\boldsymbol {p}}_{0}^{\mathrm {T} }{\boldsymbol {A}}{\boldsymbol {p}}_{0}}}} 4886: 6602:{\displaystyle {\mathcal {K}}({\boldsymbol {A}},{\boldsymbol {r}}_{0})=\mathrm {span} \{{\boldsymbol {r}}_{0},{\boldsymbol {Ar}}_{0},{\boldsymbol {A}}^{2}{\boldsymbol {r}}_{0},\ldots \}} 5860:{\displaystyle {\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ar}}_{k+1}={\begin{cases}0,\;i<k\\-{\boldsymbol {r}}_{k+1}^{T}{\boldsymbol {r}}_{k+1}/\alpha _{k},\;i=k\end{cases}}} 3630: 7000: 10953: 3861: 3427: 3260: 420: 129: 12846: 12350: 12318: 12289: 12260: 11791: 10918: 10733: 10704: 10402: 10132: 9900: 8566: 8537: 8483: 7949: 6959: 6390: 3228: 1922: 863: 801: 699: 485: 456: 6076:{\displaystyle {\boldsymbol {r}}_{k+1}^{T}{\boldsymbol {A}}{\boldsymbol {p}}_{i}={\boldsymbol {r}}_{k+1}^{T}{\frac {{\boldsymbol {r}}_{i}-{\boldsymbol {r}}_{i+1}}{\alpha _{i}}}} 8508: 8167: 8145: 1890: 390:

Minimizing the quadratic function is then a problem of moving around the plane, searching for that shared center of all those ellipsoids. The center can be found by computing

90: 5226: 5126: 12980:{\displaystyle {\boldsymbol {p}}_{i+1}^{\mathrm {T} }{\boldsymbol {Ap}}_{i}=({\boldsymbol {r}}_{i+1}+\beta _{i}{\boldsymbol {p}}_{i})^{\mathrm {T} }{\boldsymbol {Ap}}_{i}=0} 3959: 9139: 8049: 6330:{\displaystyle \mathbf {p} _{k+1}:={\boldsymbol {r}}_{k+1}+{\frac {\mathbf {r} _{k+1}^{\top }\mathbf {r} _{k+1}}{\mathbf {r} _{k}^{\top }\mathbf {r} _{k}}}\mathbf {p} _{k}} 4833: 1453: 12475:{\displaystyle {\boldsymbol {r}}_{i+1}^{\mathrm {T} }{\boldsymbol {r}}_{i}=({\boldsymbol {r}}_{i}-\alpha _{i}{\boldsymbol {Ap}}_{i})^{\mathrm {T} }{\boldsymbol {r}}_{i}=0} 2096: 132: 12204: 828: 12231: 9927: 6615: 10984: 10759: 8175: 3111: 3026: 2997: 2974: 2890: 2756: 2572: 2451: 2168: 11074: 7005: 6930: 8925: 8898: 1949: 246:{\displaystyle f({\boldsymbol {x}})={\boldsymbol {x}}^{\mathrm {T} }{\boldsymbol {A}}{\boldsymbol {x}}-2{\boldsymbol {b}}^{\mathrm {T} }{\boldsymbol {x}}{\text{.}}} 6399: 3954: 10979: 7088: 3191: 708: 2091: 1774: 1636: 1616: 385: 365: 5446: 2459: 1531: 1458: 1189: 13462: 5876: 1673: 7870: 868: 2373: 5370: 5299: 5131: 3116: 3036: 11796: 4944:, that is, taking a conjugate gradient step gets us exactly back to where we were. This is only possible if the local gradient is already zero. 2907: 2823: 2771: 2689: 2637: 2585: 162:

The conjugate gradient method can be seen as a special case of the conjugate direction method applied to minimization of the quadratic function

490: 5231: 5028: 4960: 3866: 13634: 13583: 2066:{\displaystyle {\boldsymbol {x}}^{\mathrm {T} }{\boldsymbol {A}}{\boldsymbol {x}}-2{\boldsymbol {b}}^{\mathrm {T} }{\boldsymbol {x}}=C} 340:{\displaystyle {\boldsymbol {x}}^{\mathrm {T} }{\boldsymbol {A}}{\boldsymbol {x}}-2{\boldsymbol {b}}^{\mathrm {T} }{\boldsymbol {x}}=C} 13608: 6181:{\displaystyle \alpha _{k}={\frac {\mathbf {r} _{k}^{\top }\mathbf {r} _{k}}{\mathbf {p} _{k}^{\top }\mathbf {A} \mathbf {p} _{k}}}} 1954: 1779: 6355:

The conjugate gradient method can also be seen as a variant of the Arnoldi/Lanczos iteration applied to solving linear systems.

387:

decreases, the ellipsoids become smaller and smaller, until at its minimal value, the ellipsoid shrinks to their shared center.

13603: 13455: 8039:{\displaystyle {\boldsymbol {y}}_{i}={\boldsymbol {H}}_{i}^{-1}(\lVert {\boldsymbol {r}}_{0}\rVert _{2}{\boldsymbol {e}}_{1})} 131:

explicitly. The conjugate gradient method can be derived from several different perspectives, including specialization of the

13431: 1251:

are to be picked. Notice in particular how the residual is calculated iteratively step-by-step, instead of anew every time:

37: 10404:

to scale and compensate for the scaling in the constant factor, we potentially can have simpler recurrences of the form:

4897: 1826: 10367:

The relations above straightforwardly lead to the direct Lanczos method, which turns out to be slightly more complex.

3197:

works, with additional degrees of freedom that we can later use to pick the ones that would simplify the computation:

13629: 13562: 13448: 4838: 2456:

The conjugate direction method is imprecise in the sense that no formulae are given for selection of the directions

13593: 13520: 6962: 3594: 3193:. Thus the problem of finding conjugate axes is less constrained than the problem of orthogonalization, so the 6967: 4952:

This algorithm can be significantly simplified by some lemmas, resulting in the conjugate gradient algorithm.

10923: 3831: 3403: 3236: 393: 102: 13552: 12822: 12326: 12294: 12265: 12236: 11767: 10894: 10709: 10680: 10378: 10108: 9876: 8542: 8513: 8459: 7925: 6935: 6366: 3204: 1898: 839: 777: 675: 461: 432: 13506: 13410: 8491: 8150: 8128: 1873: 1752:

are mutually conjugate with respect to the ellipsoid iff each axis is parallel to the tangent bounding

136: 73: 29: 9200:{\displaystyle {\boldsymbol {x}}_{i}={\boldsymbol {x}}_{0}+{\boldsymbol {V}}_{i}{\boldsymbol {y}}_{i}} 8110:{\displaystyle {\boldsymbol {x}}_{i}={\boldsymbol {x}}_{0}+{\boldsymbol {V}}_{i}{\boldsymbol {y}}_{i}} 5202: 5102: 13639: 13557: 21: 9020: 7693: 6716: 5755: 13471: 6679:{\displaystyle {\boldsymbol {v}}_{i}={\boldsymbol {w}}_{i}/\lVert {\boldsymbol {w}}_{i}\rVert _{2}} 4805: 3194: 1425: 96: 17: 11043:{\displaystyle {\boldsymbol {r}}_{0}=\lVert {\boldsymbol {r}}_{0}\rVert _{2}{\boldsymbol {v}}_{1}} 12182: 8170: 806: 12209: 9905: 8231:{\displaystyle {\boldsymbol {H}}_{i}={\boldsymbol {V}}_{i}^{\mathrm {T} }{\boldsymbol {AV}}_{i}} 7072:{\displaystyle \{{\boldsymbol {v}}_{1},{\boldsymbol {v}}_{2},\ldots ,{\boldsymbol {v}}_{i-1}\}} 13382: 13516: 10738: 6460:{\displaystyle \{{\boldsymbol {v}}_{1},{\boldsymbol {v}}_{2},{\boldsymbol {v}}_{3},\ldots \}} 3090: 3011: 2982: 2959: 2875: 2741: 2557: 2430: 11053: 7150:{\displaystyle {\boldsymbol {AV}}_{i}={\boldsymbol {V}}_{i+1}{\boldsymbol {\tilde {H}}}_{i}} 6909: 767:{\displaystyle {\boldsymbol {x}}_{1}={\boldsymbol {x}}_{0}+\alpha _{0}{\boldsymbol {p}}_{0}} 13511: 8903: 8876: 2522: 1927: 10370: 3928: 8: 13490: 10958: 5514:{\displaystyle \mathbf {p} _{k}^{T}\mathbf {r} _{k}=\mathbf {r} _{k}^{T}\mathbf {r} _{k}} 3170: 2514:{\displaystyle {\boldsymbol {p}}_{0},{\boldsymbol {p}}_{1},{\boldsymbol {p}}_{2},\ldots } 1654: 1586:{\displaystyle {\boldsymbol {p}}_{0},{\boldsymbol {p}}_{1},{\boldsymbol {p}}_{2},\ldots } 1513:{\displaystyle {\boldsymbol {p}}_{0},{\boldsymbol {p}}_{1},{\boldsymbol {p}}_{2},\ldots } 1244:{\displaystyle {\boldsymbol {p}}_{0},{\boldsymbol {p}}_{1},{\boldsymbol {p}}_{2},\ldots } 2148: 13420: 4025:{\displaystyle {\boldsymbol {p}}_{k,0}=\mathbf {r} _{k}=\mathbf {b} -\mathbf {Ax} _{k}} 2521:. Specific choices lead to various methods including the conjugate gradient method and 2076: 1759: 1621: 1601: 370: 350: 1455:

prematurely, which would bring numerical problems. However, for particular choices of

13427: 6350: 6346: 2138:{\displaystyle {\boldsymbol {x}}^{\mathrm {T} }{\boldsymbol {A}}{\boldsymbol {x}}=C'} 144: 140: 2093:, we can translate it so that its center is at origin. This changes the equation to 154:

The intent of this article is to document the important steps in these derivations.

13526: 13397: 8573: 8569: 93: 25: 264: 13567: 8485:

in the iteration, and the Arnoldi iteration is reduced to the Lanczos iteration.

6468: 13363: 5944:{\displaystyle \mathbf {r} _{i+1}=\mathbf {r} _{i}-\alpha _{k}\mathbf {Ap} _{i}} 1745:{\displaystyle t_{0}{\boldsymbol {p}}_{0},\dots ,t_{n-1}{\boldsymbol {p}}_{n-1}} 1598:, then there will be no overshoot, and we would obtain the global minimum after 550:. This has a simple closed-form solution that does not involve matrix inversion: 13485: 13378: 13374: 8238:

becomes symmetric and thus tridiagonal. It then can be more clearly denoted by

7867:

When applying the Arnoldi iteration to solving linear systems, one starts with

1753: 7915:{\displaystyle {\boldsymbol {r}}_{0}={\boldsymbol {b}}-{\boldsymbol {Ax}}_{0}} 3925:. Since conjugate directions can be scaled by a nonzero value, we scale it by 913:{\displaystyle {\boldsymbol {r}}_{0}={\boldsymbol {b}}-{\boldsymbol {Ax}}_{0}} 13623: 13531: 1650: 12176:

is symmetric and lower triangular simultaneously and thus must be diagonal.

2420:{\displaystyle {\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {Ap}}_{j}=0} 13440: 13411:

An introduction to the conjugate gradient method without the agonizing pain

5431:{\displaystyle \mathbf {p} _{0},\mathbf {p} _{1},\dots ,\mathbf {p} _{j-1}} 5360:{\displaystyle \mathbf {r} _{0},\mathbf {r} _{1},\dots ,\mathbf {r} _{j-1}} 5192:{\displaystyle \mathbf {p} _{0},\mathbf {p} _{1},\dots ,\mathbf {p} _{j-1}} 3160:{\displaystyle {\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {p}}_{j}=1} 3080:{\displaystyle {\boldsymbol {p}}_{i}^{\mathrm {T} }{\boldsymbol {p}}_{j}=0} 11837:{\displaystyle {\boldsymbol {P}}_{i}^{\mathrm {T} }{\boldsymbol {AP}}_{i}} 2948:{\displaystyle {\boldsymbol {p}}_{2}^{\mathrm {T} }{\boldsymbol {Ap}}_{3}} 2864:{\displaystyle {\boldsymbol {p}}_{1}^{\mathrm {T} }{\boldsymbol {Ap}}_{3}} 2812:{\displaystyle {\boldsymbol {p}}_{1}^{\mathrm {T} }{\boldsymbol {Ap}}_{2}} 2730:{\displaystyle {\boldsymbol {p}}_{0}^{\mathrm {T} }{\boldsymbol {Ap}}_{3}} 2678:{\displaystyle {\boldsymbol {p}}_{0}^{\mathrm {T} }{\boldsymbol {Ap}}_{2}} 2626:{\displaystyle {\boldsymbol {p}}_{0}^{\mathrm {T} }{\boldsymbol {Ap}}_{1}} 13401: 6393: 543:{\displaystyle f({\boldsymbol {x}}_{0}+{\boldsymbol {p}}_{0}\alpha _{0})} 426: 10677:

As premises for the simplification, we now derive the orthogonality of

10371:

The conjugate gradient method from imposing orthogonality and conjugacy

5289:{\displaystyle \mathbf {p} _{i}^{T}\mathbf {r} _{j}=0,\;\forall i<j} 5086:{\displaystyle \mathbf {r} _{i}^{T}\mathbf {r} _{j}=0,\;\forall i<j} 5018:{\displaystyle \mathbf {p} _{i}^{T}\mathbf {r} _{j}=0,\;\forall i<j} 3918:{\displaystyle {\boldsymbol {p}}_{k,0}=\nabla f({\boldsymbol {x}}_{k})} 148: 1641: 13547: 5099:

By the geometric construction, the tangent plane to the ellipsoid at

272: 1520:, this will not occur before convergence, as we will prove below. 1646: 3033:

This resembles the problem of orthogonalization, which requires

13598: 13588: 13418:

Saad, Y. (2003). "Chapter 6: Krylov Subspace Methods, Part I".

422:

explicitly, but this is precisely what we are trying to avoid.

7082:

Put in matrix form, the iteration is captured by the equation

10105:

With this formulation, we arrive at a simple recurrence for

1991:{\displaystyle {\boldsymbol {c}}+t_{i}{\boldsymbol {p}}_{i}} 1816:{\displaystyle {\boldsymbol {c}}+t_{i}{\boldsymbol {p}}_{i}} 705:

We can now repeat this procedure, starting at our new point

13383:"Methods of conjugate gradients for solving linear systems" 9115: 7850: 6889: 5853: 4194:. Plugging it in, we have the conjugate gradient algorithm: 2533:

We can tabulate the equations that we need to set to zero:

5128:

contains each of the previous conjugate direction vectors

13390:

Journal of Research of the National Bureau of Standards

9808: 9732: 8733: 8633: 8268: 7577: 7294: 7198: 12996: 12854: 12825: 12491: 12358: 12329: 12297: 12268: 12239: 12212: 12185: 11853: 11799: 11770: 11085: 11056: 10987: 10961: 10926: 10897: 10770: 10741: 10712: 10683: 10413: 10381: 10143: 10111: 9938: 9908: 9879: 9703: 9525: 9216: 9142: 8936: 8906: 8879: 8585: 8545: 8516: 8494: 8462: 8247: 8178: 8153: 8131: 8052: 7957: 7928: 7873: 7671: 7169: 7091: 7008: 6970: 6938: 6912: 6695: 6618: 6479: 6402: 6369: 6194: 6093: 5957: 5879: 5706: 5533: 5449: 5373: 5302: 5296:. The second equation is true since by construction, 5234: 5205: 5134: 5105: 5031: 4963: 4900: 4841: 4808: 4200: 4038: 3962: 3931: 3869: 3834: 3638: 3597: 3435: 3406: 3268: 3239: 3207: 3173: 3119: 3093: 3039: 3014: 2985: 2962: 2910: 2878: 2826: 2774: 2744: 2692: 2640: 2588: 2560: 2462: 2433: 2376: 2176: 2151: 2099: 2079: 2007: 1957: 1930: 1901: 1876: 1829: 1782: 1762: 1676: 1624: 1604: 1534: 1461: 1428: 1257: 1192: 929: 871: 842: 809: 780: 711: 678: 556: 493: 464: 435: 396: 373: 353: 281: 171: 105: 76: 40: 6337:, which is the proper conjugate gradient algorithm. 60:{\displaystyle {\boldsymbol {Ax}}={\boldsymbol {b}}} 6363:In the Arnoldi iteration, one starts with a vector 4937:{\displaystyle \mathbf {x} _{k+1}=\mathbf {x} _{k}} 1895:Note that we need to scale each directional vector 13419: 13335: 12979: 12840: 12808: 12474: 12344: 12312: 12283: 12254: 12225: 12198: 12165: 11836: 11785: 11753: 11068: 11042: 10973: 10947: 10912: 10880: 10753: 10727: 10698: 10666: 10396: 10356: 10126: 10094: 9921: 9894: 9862: 9683: 9505: 9199: 9125: 8919: 8892: 8862: 8560: 8531: 8502: 8477: 8445: 8230: 8161: 8139: 8109: 8038: 7943: 7914: 7856: 7651: 7149: 7071: 6994: 6953: 6924: 6895: 6678: 6601: 6459: 6384: 6329: 6180: 6075: 5943: 5859: 5687: 5513: 5430: 5359: 5288: 5220: 5191: 5120: 5085: 5017: 4936: 4880: 4827: 4791: 4186: 4024: 3948: 3917: 3855: 3816: 3624: 3577: 3421: 3389: 3254: 3222: 3185: 3159: 3105: 3079: 3020: 2991: 2968: 2947: 2884: 2863: 2811: 2750: 2729: 2677: 2625: 2566: 2513: 2445: 2419: 2362: 2162: 2137: 2085: 2065: 1990: 1943: 1916: 1884: 1862: 1815: 1768: 1744: 1630: 1610: 1585: 1512: 1447: 1414: 1243: 1175: 912: 857: 833:We can summarize this as the following algorithm: 822: 795: 766: 693: 664: 542: 479: 450: 414: 379: 359: 339: 245: 123: 84: 59: 11302: 8147:is symmetric positive-definite. With symmetry of 7922:, the residual corresponding to an initial guess 7270: 7135: 1863:{\displaystyle \{{\boldsymbol {p}}_{j}:j\neq i\}} 13621: 13373: 8456:This enables a short three-term recurrence for 10891:The residuals are mutually orthogonal because 4881:{\displaystyle \nabla f(\mathrm {x} _{k+1})=0} 256:which allows us to apply geometric intuition. 13456: 13364:http://user.it.uu.se/~matsh/opt/f8/node5.html 7951:. After each step of iteration, one computes 6358: 4835:, then the algorithm has converged, that is, 13470: 11548: 11532: 11493: 11477: 11019: 11003: 9648: 9632: 9426: 9410: 9306: 9290: 8120: 8012: 7996: 7777: 7755: 7066: 7009: 6667: 6651: 6596: 6530: 6454: 6403: 6340: 1857: 1830: 13422:Iterative methods for sparse linear systems 8125:For the rest of discussion, we assume that 4498: is sufficiently small, then exit loop 13463: 13449: 5840: 5764: 5273: 5070: 5002: 9873:In fact, there are short recurrences for 3625:{\displaystyle {\boldsymbol {p}}_{n-1,0}} 12262:by solely imposing the orthogonality of 6995:{\displaystyle {\boldsymbol {Av}}_{i-1}} 1776:, the tangent plane to the ellipsoid at 1640: 263: 13594:Basic Linear Algebra Subprograms (BLAS) 13311: 13292: 13272: 13247: 13219: 13216: 13197: 13164: 13149: 13121: 13090: 13087: 13068: 13054: 13051: 13026: 12961: 12958: 12934: 12903: 12885: 12882: 12857: 12828: 12784: 12781: 12762: 12748: 12729: 12701: 12698: 12668: 12637: 12620: 12601: 12573: 12570: 12551: 12537: 12518: 12456: 12432: 12429: 12404: 12386: 12361: 12332: 12300: 12271: 12242: 12179:Now we can derive the constant factors 12149: 12127: 12097: 12085: 12073: 12051: 12021: 12009: 11987: 11957: 11945: 11942: 11923: 11901: 11882: 11879: 11860: 11824: 11821: 11802: 11773: 11726: 11711: 11692: 11636: 11621: 11602: 11559: 11537: 11519: 11504: 11482: 11451: 11436: 11417: 11377: 11365: 11353: 11338: 11316: 11299: 11279: 11264: 11242: 11230: 11227: 11212: 11187: 11175: 11160: 11151: 11143: 11122: 11119: 11110: 11092: 11030: 11008: 10990: 10948:{\displaystyle {\boldsymbol {v}}_{i+1}} 10929: 10900: 10849: 10846: 10827: 10796: 10777: 10715: 10686: 10639: 10608: 10589: 10562: 10559: 10522: 10503: 10476: 10439: 10420: 10384: 10335: 10304: 10282: 10251: 10233: 10218: 10196: 10184: 10169: 10150: 10114: 10009: 9984: 9945: 9882: 9813: 9786: 9757: 9737: 9710: 9659: 9637: 9611: 9592: 9563: 9551: 9532: 9489: 9477: 9462: 9437: 9415: 9389: 9369: 9357: 9342: 9317: 9295: 9269: 9257: 9242: 9223: 9187: 9175: 9160: 9145: 8615: 8603: 8588: 8548: 8519: 8496: 8465: 8250: 8218: 8215: 8196: 8181: 8155: 8133: 8097: 8085: 8070: 8055: 8023: 8001: 7975: 7960: 7931: 7902: 7899: 7890: 7876: 7760: 7720: 7717: 7698: 7620: 7582: 7267: 7236: 7217: 7203: 7176: 7132: 7112: 7097: 7094: 7050: 7029: 7014: 6976: 6973: 6941: 6855: 6834: 6831: 6812: 6761: 6758: 6721: 6698: 6656: 6636: 6621: 6580: 6568: 6553: 6550: 6535: 6500: 6491: 6438: 6423: 6408: 6372: 6218: 6044: 6029: 6003: 5988: 5982: 5960: 5806: 5783: 5731: 5728: 5709: 5675: 5660: 5657: 5638: 5618: 5615: 5596: 5551: 4721: 4706: 4703: 4684: 4664: 4661: 4642: 4597: 4174: 4159: 4156: 4137: 4123: 4120: 4101: 4056: 4041: 3965: 3902: 3872: 3856:{\displaystyle {\boldsymbol {p}}_{k,0}} 3837: 3804: 3789: 3786: 3767: 3741: 3738: 3719: 3662: 3641: 3600: 3565: 3550: 3547: 3528: 3514: 3511: 3492: 3453: 3438: 3409: 3377: 3362: 3359: 3340: 3326: 3323: 3304: 3286: 3271: 3242: 3210: 3141: 3122: 3061: 3042: 2935: 2932: 2913: 2851: 2848: 2829: 2799: 2796: 2777: 2717: 2714: 2695: 2665: 2662: 2643: 2613: 2610: 2591: 2528: 2495: 2480: 2465: 2401: 2398: 2379: 2277: 2262: 2243: 2207: 2192: 2120: 2115: 2102: 2053: 2040: 2028: 2023: 2010: 1978: 1959: 1904: 1878: 1835: 1823:is a hyperplane spanned by the vectors 1803: 1784: 1726: 1689: 1567: 1552: 1537: 1523: 1494: 1479: 1464: 1402: 1396: 1372: 1354: 1329: 1320: 1312: 1292: 1289: 1280: 1260: 1225: 1210: 1195: 1159: 1156: 1131: 1106: 1085: 1060: 1035: 1011: 1008: 989: 975: 956: 900: 897: 888: 874: 845: 783: 754: 729: 714: 681: 649: 643: 625: 608: 605: 596: 575: 517: 502: 467: 438: 399: 327: 314: 302: 297: 284: 234: 221: 209: 204: 191: 179: 108: 78: 53: 45: 42: 13622: 8510:is symmetric positive-definite, so is 5228:is perpendicular to the tangent, thus 4377: 4344: 3422:{\displaystyle {\boldsymbol {p}}_{20}} 3255:{\displaystyle {\boldsymbol {p}}_{10}} 672:Geometrically, we start at some point 415:{\displaystyle {\boldsymbol {A}}^{-1}} 157: 124:{\displaystyle {\boldsymbol {A}}^{-1}} 13444: 12841:{\displaystyle {\boldsymbol {p}}_{i}} 12345:{\displaystyle {\boldsymbol {r}}_{i}} 12313:{\displaystyle {\boldsymbol {p}}_{i}} 12284:{\displaystyle {\boldsymbol {r}}_{i}} 12255:{\displaystyle {\boldsymbol {p}}_{i}} 11786:{\displaystyle {\boldsymbol {p}}_{i}} 10913:{\displaystyle {\boldsymbol {r}}_{i}} 10728:{\displaystyle {\boldsymbol {p}}_{i}} 10699:{\displaystyle {\boldsymbol {r}}_{i}} 10397:{\displaystyle {\boldsymbol {p}}_{i}} 10127:{\displaystyle {\boldsymbol {x}}_{i}} 9895:{\displaystyle {\boldsymbol {p}}_{i}} 8561:{\displaystyle {\boldsymbol {H}}_{i}} 8532:{\displaystyle {\boldsymbol {H}}_{i}} 8478:{\displaystyle {\boldsymbol {v}}_{i}} 7944:{\displaystyle {\boldsymbol {x}}_{0}} 6954:{\displaystyle {\boldsymbol {v}}_{i}} 6385:{\displaystyle {\boldsymbol {r}}_{0}} 3223:{\displaystyle {\boldsymbol {p}}_{0}} 1917:{\displaystyle {\boldsymbol {p}}_{i}} 858:{\displaystyle {\boldsymbol {x}}_{0}} 796:{\displaystyle {\boldsymbol {p}}_{1}} 694:{\displaystyle {\boldsymbol {x}}_{0}} 480:{\displaystyle {\boldsymbol {p}}_{0}} 451:{\displaystyle {\boldsymbol {x}}_{0}} 13417: 9694:It is now important to observe that 4894:By construction, it would mean that 3956:for notational cleanness, obtaining 2170:. The condition of tangency is then: 13635:Optimization algorithms and methods 12819:Similarly, due to the conjugacy of 1594:pick the directions to be a set of 865:, and compute the initial residual 13: 13303: 13264: 13208: 13138: 13079: 13043: 12950: 12874: 12773: 12740: 12690: 12612: 12562: 12529: 12448: 12378: 12141: 12065: 12001: 11934: 11915: 11871: 11813: 11703: 11613: 11428: 10838: 10788: 8207: 7709: 7631: 6823: 6526: 6523: 6520: 6517: 6482: 6295: 6258: 6153: 6122: 5720: 5649: 5607: 5274: 5071: 5003: 4853: 4842: 4695: 4653: 4148: 4112: 3891: 3778: 3730: 3539: 3503: 3351: 3315: 3133: 3053: 2924: 2840: 2788: 2706: 2654: 2602: 2390: 2348: 2236: 2108: 2046: 2016: 1000: 967: 836:Start by picking an initial guess 702:tangent to the contour ellipsoid. 636: 586: 320: 290: 227: 197: 14: 13651: 8503:{\displaystyle {\boldsymbol {A}}} 8162:{\displaystyle {\boldsymbol {A}}} 8140:{\displaystyle {\boldsymbol {A}}} 4947: 2001:Given an ellipsoid with equation 1885:{\displaystyle {\boldsymbol {c}}} 85:{\displaystyle {\boldsymbol {A}}} 8873:with convenient recurrences for 6317: 6302: 6285: 6265: 6242: 6197: 6165: 6159: 6143: 6129: 6112: 6087:Plugging lemmas 1-3 in, we have 5931: 5928: 5903: 5882: 5536: 5501: 5484: 5469: 5452: 5412: 5391: 5376: 5341: 5320: 5305: 5254: 5237: 5221:{\displaystyle \mathbf {r} _{j}} 5208: 5173: 5152: 5137: 5121:{\displaystyle \mathbf {x} _{j}} 5108: 5051: 5034: 4983: 4966: 4924: 4903: 4764: 4576: 4558: 4555: 4530: 4509: 4455: 4430: 4409: 4388: 4385: 4366: 4352: 4333: 4266: 4251: 4234: 4231: 4222: 4208: 4012: 4009: 4000: 3986: 1998:falls exactly on the ellipsoid. 1892:is the center of the ellipsoid. 13346:This completes the derivation. 4736: 4573: 4506: 4470: 4406: 4314: 2347: 1666:-dimensional ellipsoids, where 429:, where we start at some point 13356: 13180: 13144: 12945: 12898: 12685: 12632: 12443: 12399: 11721: 11687: 11631: 11597: 11569: 11529: 11446: 11412: 11197: 11155: 10025: 9979: 9669: 9629: 9447: 9407: 9327: 9287: 8033: 7993: 6850: 6807: 6510: 6487: 4869: 4848: 4492: 4477: 3912: 3897: 2341: 2320: 2300: 2247: 2231: 2177: 1645:Two conjugate diameters of an 1364: 1324: 618: 592: 537: 497: 425:The simplest method is greedy 259: 183: 175: 1: 13408:Shewchuk, Jonathan Richard. " 13349: 10920:is essentially a multiple of 4828:{\displaystyle \alpha _{k}=0} 1638:is the number of dimensions. 1596:mutually conjugate directions 1448:{\displaystyle \alpha _{i}=0} 13362:Conjugate Direction Methods 12323:Due to the orthogonality of 6963:Gram-Schmidt orthogonalizing 1649:. Each edge of the bounding 28:for numerically solving the 7: 12233:with respect to the scaled 12199:{\displaystyle \alpha _{i}} 11793:, it suffices to show that 7079:followed by normalization. 3828:The most natural choice of 823:{\displaystyle \alpha _{1}} 10: 13656: 13507:System of linear equations 12226:{\displaystyle \beta _{i}} 9922:{\displaystyle \zeta _{i}} 6359:The general Arnoldi method 6344: 3863:is the gradient. That is, 1756:. In other words, for any 133:conjugate direction method 13576: 13558:Cache-oblivious algorithm 13540: 13499: 13478: 8121:The direct Lanczos method 6341:Arnoldi/Lanczos iteration 5873:By construction, we have 5367:is a linear transform of 1422:It is possibly true that 22:conjugate gradient method 13630:Numerical linear algebra 13609:General purpose software 13472:Numerical linear algebra 11764:To see the conjugacy of 6392:and gradually builds an 2145:for some other constant 1657:to one of the diameters. 18:numerical linear algebra 12848:, it is necessary that 12352:, it is necessary that 10754:{\displaystyle i\neq j} 8171:upper Hessenberg matrix 3106:{\displaystyle i\neq j} 3021:{\displaystyle \ddots } 2992:{\displaystyle \vdots } 2969:{\displaystyle \cdots } 2885:{\displaystyle \cdots } 2751:{\displaystyle \cdots } 2567:{\displaystyle \cdots } 2446:{\displaystyle i\neq j} 774:, pick a new direction 487:somehow, then minimize 139:, and variation of the 13426:(2nd ed.). SIAM. 13337: 12981: 12842: 12810: 12476: 12346: 12314: 12285: 12256: 12227: 12200: 12167: 11838: 11787: 11755: 11070: 11069:{\displaystyle i>0} 11044: 10975: 10949: 10914: 10882: 10755: 10729: 10700: 10668: 10398: 10358: 10128: 10096: 9923: 9896: 9864: 9685: 9507: 9201: 9127: 8921: 8894: 8864: 8562: 8533: 8504: 8479: 8447: 8232: 8163: 8141: 8111: 8040: 7945: 7916: 7858: 7653: 7151: 7073: 6996: 6955: 6926: 6925:{\displaystyle i>1} 6897: 6806: 6680: 6603: 6461: 6386: 6331: 6182: 6077: 5945: 5861: 5689: 5590: 5515: 5432: 5361: 5290: 5222: 5193: 5122: 5087: 5019: 4938: 4882: 4829: 4793: 4636: 4188: 4095: 4026: 3950: 3919: 3857: 3818: 3713: 3626: 3579: 3486: 3423: 3391: 3256: 3224: 3187: 3161: 3107: 3081: 3022: 2993: 2970: 2949: 2886: 2865: 2813: 2752: 2731: 2679: 2627: 2568: 2515: 2447: 2421: 2364: 2164: 2139: 2087: 2067: 1992: 1945: 1918: 1886: 1864: 1817: 1770: 1746: 1658: 1632: 1612: 1587: 1514: 1449: 1416: 1245: 1177: 914: 859: 824: 797: 768: 695: 666: 544: 481: 452: 416: 381: 361: 341: 268: 247: 125: 86: 61: 13604:Specialized libraries 13517:Matrix multiplication 13512:Matrix decompositions 13338: 12982: 12843: 12811: 12477: 12347: 12315: 12286: 12257: 12228: 12201: 12168: 11839: 11788: 11756: 11071: 11045: 10976: 10950: 10915: 10883: 10756: 10730: 10701: 10669: 10399: 10359: 10129: 10097: 9924: 9897: 9865: 9686: 9508: 9202: 9128: 8922: 8920:{\displaystyle d_{i}} 8895: 8893:{\displaystyle c_{i}} 8865: 8563: 8534: 8505: 8480: 8448: 8233: 8164: 8142: 8112: 8041: 7946: 7917: 7859: 7654: 7152: 7074: 6997: 6956: 6927: 6898: 6780: 6681: 6604: 6462: 6387: 6345:Further information: 6332: 6183: 6078: 5946: 5862: 5695:, now apply lemma 1. 5690: 5564: 5516: 5433: 5362: 5291: 5223: 5194: 5123: 5088: 5020: 4939: 4883: 4830: 4794: 4616: 4189: 4069: 4027: 3951: 3920: 3858: 3819: 3687: 3627: 3580: 3466: 3424: 3392: 3257: 3225: 3188: 3162: 3108: 3082: 3023: 2994: 2971: 2950: 2887: 2866: 2814: 2753: 2732: 2680: 2628: 2569: 2516: 2448: 2422: 2365: 2165: 2140: 2088: 2068: 1993: 1946: 1944:{\displaystyle t_{i}} 1919: 1887: 1865: 1818: 1771: 1747: 1644: 1633: 1613: 1588: 1515: 1450: 1417: 1246: 1178: 915: 860: 825: 798: 769: 696: 667: 545: 482: 453: 417: 382: 362: 342: 267: 248: 126: 87: 62: 13402:10.6028/jres.049.044 12994: 12852: 12823: 12489: 12356: 12327: 12295: 12266: 12237: 12210: 12183: 11851: 11797: 11768: 11083: 11054: 10985: 10959: 10924: 10895: 10768: 10739: 10710: 10681: 10411: 10379: 10141: 10109: 9936: 9906: 9877: 9701: 9523: 9214: 9140: 8934: 8904: 8877: 8583: 8543: 8514: 8492: 8460: 8245: 8176: 8151: 8129: 8050: 8046:and the new iterate 7955: 7926: 7871: 7669: 7167: 7089: 7006: 6968: 6936: 6910: 6906:In other words, for 6693: 6616: 6477: 6400: 6367: 6192: 6091: 5955: 5877: 5704: 5531: 5447: 5371: 5300: 5232: 5203: 5132: 5103: 5029: 4961: 4898: 4839: 4806: 4198: 4036: 3960: 3949:{\displaystyle -1/2} 3929: 3867: 3832: 3636: 3632:, then modify it to 3595: 3433: 3429:, then modify it to 3404: 3266: 3262:, then modify it to 3237: 3205: 3195:Gram–Schmidt process 3171: 3117: 3091: 3037: 3012: 2983: 2960: 2908: 2876: 2824: 2772: 2742: 2690: 2638: 2586: 2558: 2529:Gram–Schmidt process 2523:Gaussian elimination 2460: 2431: 2374: 2174: 2149: 2097: 2077: 2005: 1955: 1928: 1899: 1874: 1827: 1780: 1760: 1674: 1622: 1602: 1532: 1524:Conjugate directions 1459: 1426: 1255: 1190: 927: 869: 840: 807: 778: 709: 676: 554: 491: 462: 433: 394: 371: 351: 279: 169: 103: 99:, without computing 74: 38: 13491:Numerical stability 13308: 13269: 13213: 13143: 13084: 13048: 12879: 12778: 12745: 12617: 12567: 12534: 12383: 12146: 12114: 12070: 12038: 12006: 11974: 11939: 11920: 11876: 11818: 11708: 11618: 11433: 10974:{\displaystyle i=0} 10843: 10793: 9628: 9580: 9406: 9386: 9286: 8212: 7992: 7714: 7636: 6828: 6299: 6262: 6157: 6126: 6083:Now apply lemma 1. 6023: 5980: 5803: 5725: 5654: 5612: 5498: 5466: 5251: 5048: 4980: 4782: as the result 4700: 4658: 4382: 4349: 4153: 4117: 3783: 3735: 3544: 3508: 3356: 3320: 3186:{\displaystyle i=j} 3138: 3058: 2929: 2845: 2793: 2711: 2659: 2607: 2537: 2395: 2340: 1005: 972: 641: 591: 458:, pick a direction 158:Conjugate direction 13333: 13331: 13290: 13245: 13195: 13119: 13066: 13024: 12977: 12855: 12838: 12806: 12804: 12760: 12727: 12599: 12549: 12516: 12472: 12359: 12342: 12310: 12281: 12252: 12223: 12196: 12163: 12161: 12125: 12095: 12049: 12019: 11985: 11955: 11921: 11899: 11858: 11834: 11800: 11783: 11751: 11749: 11690: 11600: 11415: 11066: 11040: 10971: 10945: 10910: 10878: 10876: 10825: 10775: 10751: 10725: 10696: 10664: 10662: 10394: 10354: 10352: 10124: 10092: 10090: 9919: 9892: 9860: 9858: 9845: 9769: 9681: 9679: 9609: 9561: 9503: 9501: 9387: 9367: 9267: 9197: 9123: 9121: 9114: 8917: 8890: 8860: 8854: 8722: 8558: 8529: 8500: 8475: 8443: 8432: 8228: 8194: 8159: 8137: 8107: 8036: 7973: 7941: 7912: 7854: 7849: 7696: 7649: 7647: 7639: 7618: 7563: 7248: 7147: 7069: 6992: 6951: 6922: 6893: 6888: 6810: 6676: 6599: 6457: 6382: 6327: 6283: 6240: 6178: 6141: 6110: 6073: 6001: 5958: 5941: 5857: 5852: 5781: 5707: 5685: 5636: 5594: 5511: 5482: 5450: 5428: 5357: 5286: 5235: 5218: 5189: 5118: 5083: 5032: 5015: 4964: 4934: 4878: 4825: 4802:If at some point, 4789: 4787: 4682: 4640: 4364: 4331: 4184: 4135: 4099: 4022: 3946: 3915: 3853: 3814: 3765: 3717: 3622: 3575: 3526: 3490: 3419: 3387: 3338: 3302: 3252: 3220: 3183: 3157: 3120: 3103: 3077: 3040: 3018: 2989: 2966: 2945: 2911: 2882: 2861: 2827: 2809: 2775: 2748: 2727: 2693: 2675: 2641: 2623: 2589: 2564: 2536: 2511: 2443: 2417: 2377: 2360: 2326: 2163:{\displaystyle C'} 2160: 2135: 2083: 2073:for some constant 2063: 1988: 1941: 1914: 1882: 1860: 1813: 1766: 1742: 1659: 1628: 1608: 1583: 1528:If the directions 1510: 1445: 1412: 1241: 1173: 1171: 987: 954: 910: 855: 820: 793: 764: 691: 662: 623: 573: 540: 477: 448: 412: 377: 357: 337: 275:with the equation 269: 243: 121: 82: 57: 13617: 13616: 13433:978-0-89871-534-7 13381:(December 1952). 13327: 13322: 13230: 13101: 12800: 12795: 12712: 12584: 12291:and conjugacy of 11745: 11305: 10872: 10819: 10706:and conjugacy of 10658: 10581: 10495: 10348: 10086: 10031: 9977: 9854: 9778: 9675: 9584: 9110: 9096: 9052: 9038: 8992: 8441: 7845: 7825: 7811: 7791: 7749: 7735: 7273: 7257: 7138: 6884: 6870: 6750: 6736: 6351:Lanczos iteration 6347:Arnoldi iteration 6313: 6176: 6071: 5671: 5527:By construction, 4783: 4760: 4717: 4499: 4474: 4399: 4298: 4170: 3800: 3561: 3373: 3031: 3030: 2086:{\displaystyle C} 1769:{\displaystyle i} 1631:{\displaystyle n} 1611:{\displaystyle n} 1098: 1027: 1022: 660: 380:{\displaystyle C} 360:{\displaystyle C} 241: 97:positive-definite 13647: 13640:Gradient methods 13527:Matrix splitting 13465: 13458: 13451: 13442: 13441: 13437: 13425: 13405: 13387: 13366: 13360: 13342: 13340: 13339: 13334: 13332: 13328: 13325: 13323: 13321: 13320: 13319: 13314: 13307: 13306: 13300: 13295: 13288: 13287: 13286: 13275: 13268: 13267: 13261: 13250: 13243: 13235: 13231: 13229: 13228: 13227: 13222: 13212: 13211: 13205: 13200: 13194: 13193: 13183: 13179: 13178: 13167: 13158: 13157: 13152: 13142: 13141: 13135: 13124: 13117: 13106: 13102: 13100: 13099: 13098: 13093: 13083: 13082: 13076: 13071: 13064: 13063: 13062: 13057: 13047: 13046: 13040: 13029: 13022: 13010: 13009: 12986: 12984: 12983: 12978: 12970: 12969: 12964: 12955: 12954: 12953: 12943: 12942: 12937: 12931: 12930: 12918: 12917: 12906: 12894: 12893: 12888: 12878: 12877: 12871: 12860: 12847: 12845: 12844: 12839: 12837: 12836: 12831: 12815: 12813: 12812: 12807: 12805: 12801: 12798: 12796: 12794: 12793: 12792: 12787: 12777: 12776: 12770: 12765: 12758: 12757: 12756: 12751: 12744: 12743: 12737: 12732: 12725: 12717: 12713: 12711: 12710: 12709: 12704: 12695: 12694: 12693: 12683: 12682: 12671: 12665: 12664: 12646: 12645: 12640: 12630: 12629: 12628: 12623: 12616: 12615: 12609: 12604: 12597: 12589: 12585: 12583: 12582: 12581: 12576: 12566: 12565: 12559: 12554: 12547: 12546: 12545: 12540: 12533: 12532: 12526: 12521: 12514: 12505: 12504: 12481: 12479: 12478: 12473: 12465: 12464: 12459: 12453: 12452: 12451: 12441: 12440: 12435: 12426: 12425: 12413: 12412: 12407: 12395: 12394: 12389: 12382: 12381: 12375: 12364: 12351: 12349: 12348: 12343: 12341: 12340: 12335: 12319: 12317: 12316: 12311: 12309: 12308: 12303: 12290: 12288: 12287: 12282: 12280: 12279: 12274: 12261: 12259: 12258: 12253: 12251: 12250: 12245: 12232: 12230: 12229: 12224: 12222: 12221: 12205: 12203: 12202: 12197: 12195: 12194: 12172: 12170: 12169: 12164: 12162: 12158: 12157: 12152: 12145: 12144: 12135: 12130: 12118: 12113: 12105: 12100: 12094: 12093: 12088: 12082: 12081: 12076: 12069: 12068: 12059: 12054: 12042: 12037: 12029: 12024: 12018: 12017: 12012: 12005: 12004: 11995: 11990: 11978: 11973: 11965: 11960: 11954: 11953: 11948: 11938: 11937: 11931: 11926: 11919: 11918: 11909: 11904: 11891: 11890: 11885: 11875: 11874: 11868: 11863: 11843: 11841: 11840: 11835: 11833: 11832: 11827: 11817: 11816: 11810: 11805: 11792: 11790: 11789: 11784: 11782: 11781: 11776: 11760: 11758: 11757: 11752: 11750: 11746: 11743: 11741: 11740: 11729: 11720: 11719: 11714: 11707: 11706: 11700: 11695: 11686: 11685: 11655: 11651: 11650: 11639: 11630: 11629: 11624: 11617: 11616: 11610: 11605: 11596: 11595: 11568: 11567: 11562: 11556: 11555: 11546: 11545: 11540: 11528: 11527: 11522: 11513: 11512: 11507: 11501: 11500: 11491: 11490: 11485: 11470: 11466: 11465: 11454: 11445: 11444: 11439: 11432: 11431: 11425: 11420: 11411: 11410: 11386: 11385: 11380: 11374: 11373: 11368: 11362: 11361: 11356: 11347: 11346: 11341: 11329: 11325: 11324: 11319: 11313: 11312: 11307: 11306: 11298: 11294: 11293: 11282: 11273: 11272: 11267: 11255: 11251: 11250: 11245: 11239: 11238: 11233: 11221: 11220: 11215: 11203: 11196: 11195: 11190: 11184: 11183: 11178: 11169: 11168: 11163: 11154: 11146: 11135: 11131: 11130: 11125: 11113: 11101: 11100: 11095: 11075: 11073: 11072: 11067: 11049: 11047: 11046: 11041: 11039: 11038: 11033: 11027: 11026: 11017: 11016: 11011: 10999: 10998: 10993: 10980: 10978: 10977: 10972: 10954: 10952: 10951: 10946: 10944: 10943: 10932: 10919: 10917: 10916: 10911: 10909: 10908: 10903: 10887: 10885: 10884: 10879: 10877: 10873: 10870: 10858: 10857: 10852: 10842: 10841: 10835: 10830: 10820: 10817: 10805: 10804: 10799: 10792: 10791: 10785: 10780: 10760: 10758: 10757: 10752: 10734: 10732: 10731: 10726: 10724: 10723: 10718: 10705: 10703: 10702: 10697: 10695: 10694: 10689: 10673: 10671: 10670: 10665: 10663: 10659: 10656: 10654: 10653: 10642: 10636: 10635: 10617: 10616: 10611: 10598: 10597: 10592: 10582: 10579: 10577: 10576: 10565: 10556: 10555: 10537: 10536: 10525: 10512: 10511: 10506: 10496: 10493: 10491: 10490: 10479: 10473: 10472: 10454: 10453: 10442: 10429: 10428: 10423: 10403: 10401: 10400: 10395: 10393: 10392: 10387: 10363: 10361: 10360: 10355: 10353: 10349: 10346: 10344: 10343: 10338: 10332: 10331: 10319: 10318: 10307: 10295: 10291: 10290: 10285: 10279: 10278: 10266: 10265: 10254: 10248: 10247: 10236: 10227: 10226: 10221: 10209: 10205: 10204: 10199: 10193: 10192: 10187: 10178: 10177: 10172: 10159: 10158: 10153: 10133: 10131: 10130: 10125: 10123: 10122: 10117: 10101: 10099: 10098: 10093: 10091: 10087: 10084: 10082: 10081: 10066: 10065: 10046: 10045: 10032: 10029: 10024: 10023: 10012: 10006: 10005: 9993: 9992: 9987: 9978: 9976: 9975: 9963: 9954: 9953: 9948: 9928: 9926: 9925: 9920: 9918: 9917: 9901: 9899: 9898: 9893: 9891: 9890: 9885: 9869: 9867: 9866: 9861: 9859: 9855: 9852: 9850: 9849: 9842: 9841: 9828: 9827: 9816: 9795: 9794: 9789: 9779: 9776: 9774: 9773: 9766: 9765: 9760: 9752: 9751: 9740: 9719: 9718: 9713: 9690: 9688: 9687: 9682: 9680: 9676: 9673: 9668: 9667: 9662: 9656: 9655: 9646: 9645: 9640: 9627: 9619: 9614: 9601: 9600: 9595: 9585: 9582: 9579: 9571: 9566: 9560: 9559: 9554: 9541: 9540: 9535: 9512: 9510: 9509: 9504: 9502: 9498: 9497: 9492: 9486: 9485: 9480: 9471: 9470: 9465: 9453: 9446: 9445: 9440: 9434: 9433: 9424: 9423: 9418: 9405: 9397: 9392: 9385: 9377: 9372: 9366: 9365: 9360: 9351: 9350: 9345: 9333: 9326: 9325: 9320: 9314: 9313: 9304: 9303: 9298: 9285: 9277: 9272: 9266: 9265: 9260: 9251: 9250: 9245: 9232: 9231: 9226: 9206: 9204: 9203: 9198: 9196: 9195: 9190: 9184: 9183: 9178: 9169: 9168: 9163: 9154: 9153: 9148: 9132: 9130: 9129: 9124: 9122: 9118: 9117: 9111: 9108: 9097: 9094: 9090: 9089: 9080: 9079: 9067: 9066: 9053: 9050: 9039: 9036: 9032: 9031: 9007: 9006: 8993: 8990: 8988: 8987: 8972: 8967: 8966: 8950: 8949: 8926: 8924: 8923: 8918: 8916: 8915: 8899: 8897: 8896: 8891: 8889: 8888: 8869: 8867: 8866: 8861: 8859: 8858: 8851: 8850: 8840: 8839: 8838: 8837: 8833: 8832: 8821: 8820: 8804: 8803: 8802: 8789: 8788: 8784: 8783: 8772: 8771: 8761: 8757: 8756: 8745: 8744: 8727: 8726: 8714: 8713: 8703: 8702: 8701: 8692: 8691: 8675: 8674: 8661: 8652: 8651: 8624: 8623: 8618: 8612: 8611: 8606: 8597: 8596: 8591: 8574:partial pivoting 8567: 8565: 8564: 8559: 8557: 8556: 8551: 8538: 8536: 8535: 8530: 8528: 8527: 8522: 8509: 8507: 8506: 8501: 8499: 8484: 8482: 8481: 8476: 8474: 8473: 8468: 8452: 8450: 8449: 8444: 8442: 8439: 8437: 8436: 8429: 8428: 8417: 8416: 8406: 8405: 8404: 8400: 8399: 8388: 8387: 8370: 8369: 8353: 8352: 8334: 8330: 8329: 8318: 8317: 8306: 8305: 8292: 8291: 8280: 8279: 8259: 8258: 8253: 8237: 8235: 8234: 8229: 8227: 8226: 8221: 8211: 8210: 8204: 8199: 8190: 8189: 8184: 8168: 8166: 8165: 8160: 8158: 8146: 8144: 8143: 8138: 8136: 8116: 8114: 8113: 8108: 8106: 8105: 8100: 8094: 8093: 8088: 8079: 8078: 8073: 8064: 8063: 8058: 8045: 8043: 8042: 8037: 8032: 8031: 8026: 8020: 8019: 8010: 8009: 8004: 7991: 7983: 7978: 7969: 7968: 7963: 7950: 7948: 7947: 7942: 7940: 7939: 7934: 7921: 7919: 7918: 7913: 7911: 7910: 7905: 7893: 7885: 7884: 7879: 7863: 7861: 7860: 7855: 7853: 7852: 7846: 7843: 7826: 7823: 7812: 7809: 7792: 7789: 7785: 7784: 7775: 7774: 7763: 7750: 7747: 7736: 7733: 7729: 7728: 7723: 7713: 7712: 7706: 7701: 7684: 7683: 7658: 7656: 7655: 7650: 7648: 7644: 7643: 7635: 7634: 7628: 7623: 7617: 7616: 7591: 7590: 7585: 7568: 7567: 7560: 7559: 7537: 7536: 7535: 7534: 7530: 7529: 7512: 7511: 7489: 7488: 7487: 7469: 7468: 7464: 7463: 7441: 7440: 7429: 7428: 7418: 7414: 7413: 7391: 7390: 7379: 7378: 7367: 7366: 7353: 7352: 7330: 7329: 7318: 7317: 7306: 7305: 7281: 7280: 7275: 7274: 7266: 7258: 7255: 7253: 7252: 7245: 7244: 7239: 7226: 7225: 7220: 7212: 7211: 7206: 7185: 7184: 7179: 7156: 7154: 7153: 7148: 7146: 7145: 7140: 7139: 7131: 7127: 7126: 7115: 7106: 7105: 7100: 7078: 7076: 7075: 7070: 7065: 7064: 7053: 7038: 7037: 7032: 7023: 7022: 7017: 7001: 6999: 6998: 6993: 6991: 6990: 6979: 6960: 6958: 6957: 6952: 6950: 6949: 6944: 6931: 6929: 6928: 6923: 6902: 6900: 6899: 6894: 6892: 6891: 6885: 6882: 6871: 6868: 6864: 6863: 6858: 6849: 6848: 6837: 6827: 6826: 6820: 6815: 6805: 6794: 6776: 6775: 6764: 6751: 6748: 6737: 6734: 6730: 6729: 6724: 6707: 6706: 6701: 6685: 6683: 6682: 6677: 6675: 6674: 6665: 6664: 6659: 6650: 6645: 6644: 6639: 6630: 6629: 6624: 6608: 6606: 6605: 6600: 6589: 6588: 6583: 6577: 6576: 6571: 6562: 6561: 6556: 6544: 6543: 6538: 6529: 6509: 6508: 6503: 6494: 6486: 6485: 6466: 6464: 6463: 6458: 6447: 6446: 6441: 6432: 6431: 6426: 6417: 6416: 6411: 6391: 6389: 6388: 6383: 6381: 6380: 6375: 6336: 6334: 6333: 6328: 6326: 6325: 6320: 6314: 6312: 6311: 6310: 6305: 6298: 6293: 6288: 6281: 6280: 6279: 6268: 6261: 6256: 6245: 6238: 6233: 6232: 6221: 6212: 6211: 6200: 6187: 6185: 6184: 6179: 6177: 6175: 6174: 6173: 6168: 6162: 6156: 6151: 6146: 6139: 6138: 6137: 6132: 6125: 6120: 6115: 6108: 6103: 6102: 6082: 6080: 6079: 6074: 6072: 6070: 6069: 6060: 6059: 6058: 6047: 6038: 6037: 6032: 6025: 6022: 6017: 6006: 5997: 5996: 5991: 5985: 5979: 5974: 5963: 5950: 5948: 5947: 5942: 5940: 5939: 5934: 5925: 5924: 5912: 5911: 5906: 5897: 5896: 5885: 5866: 5864: 5863: 5858: 5856: 5855: 5836: 5835: 5826: 5821: 5820: 5809: 5802: 5797: 5786: 5746: 5745: 5734: 5724: 5723: 5717: 5712: 5694: 5692: 5691: 5686: 5684: 5683: 5678: 5672: 5670: 5669: 5668: 5663: 5653: 5652: 5646: 5641: 5634: 5633: 5632: 5621: 5611: 5610: 5604: 5599: 5592: 5589: 5578: 5560: 5559: 5554: 5545: 5544: 5539: 5520: 5518: 5517: 5512: 5510: 5509: 5504: 5497: 5492: 5487: 5478: 5477: 5472: 5465: 5460: 5455: 5437: 5435: 5434: 5429: 5427: 5426: 5415: 5400: 5399: 5394: 5385: 5384: 5379: 5366: 5364: 5363: 5358: 5356: 5355: 5344: 5329: 5328: 5323: 5314: 5313: 5308: 5295: 5293: 5292: 5287: 5263: 5262: 5257: 5250: 5245: 5240: 5227: 5225: 5224: 5219: 5217: 5216: 5211: 5198: 5196: 5195: 5190: 5188: 5187: 5176: 5161: 5160: 5155: 5146: 5145: 5140: 5127: 5125: 5124: 5119: 5117: 5116: 5111: 5092: 5090: 5089: 5084: 5060: 5059: 5054: 5047: 5042: 5037: 5024: 5022: 5021: 5016: 4992: 4991: 4986: 4979: 4974: 4969: 4943: 4941: 4940: 4935: 4933: 4932: 4927: 4918: 4917: 4906: 4887: 4885: 4884: 4879: 4868: 4867: 4856: 4834: 4832: 4831: 4826: 4818: 4817: 4798: 4796: 4795: 4790: 4788: 4784: 4781: 4779: 4778: 4767: 4761: 4758: 4755: 4734: 4730: 4729: 4724: 4718: 4716: 4715: 4714: 4709: 4699: 4698: 4692: 4687: 4680: 4679: 4678: 4667: 4657: 4656: 4650: 4645: 4638: 4635: 4630: 4612: 4611: 4600: 4591: 4590: 4579: 4571: 4567: 4566: 4561: 4552: 4551: 4539: 4538: 4533: 4524: 4523: 4512: 4504: 4500: 4497: 4495: 4490: 4489: 4480: 4475: 4472: 4468: 4464: 4463: 4458: 4452: 4451: 4439: 4438: 4433: 4424: 4423: 4412: 4404: 4400: 4398: 4397: 4396: 4391: 4381: 4380: 4374: 4369: 4362: 4361: 4360: 4355: 4348: 4347: 4341: 4336: 4329: 4324: 4323: 4312: 4299: 4296: 4293: 4279: 4275: 4274: 4269: 4260: 4259: 4254: 4247: 4243: 4242: 4237: 4225: 4217: 4216: 4211: 4204: 4193: 4191: 4190: 4185: 4183: 4182: 4177: 4171: 4169: 4168: 4167: 4162: 4152: 4151: 4145: 4140: 4133: 4132: 4131: 4126: 4116: 4115: 4109: 4104: 4097: 4094: 4083: 4065: 4064: 4059: 4050: 4049: 4044: 4031: 4029: 4028: 4023: 4021: 4020: 4015: 4003: 3995: 3994: 3989: 3980: 3979: 3968: 3955: 3953: 3952: 3947: 3942: 3924: 3922: 3921: 3916: 3911: 3910: 3905: 3887: 3886: 3875: 3862: 3860: 3859: 3854: 3852: 3851: 3840: 3823: 3821: 3820: 3815: 3813: 3812: 3807: 3801: 3799: 3798: 3797: 3792: 3782: 3781: 3775: 3770: 3763: 3762: 3761: 3744: 3734: 3733: 3727: 3722: 3715: 3712: 3701: 3683: 3682: 3665: 3656: 3655: 3644: 3631: 3629: 3628: 3623: 3621: 3620: 3603: 3591:Arbitrarily set 3584: 3582: 3581: 3576: 3574: 3573: 3568: 3562: 3560: 3559: 3558: 3553: 3543: 3542: 3536: 3531: 3524: 3523: 3522: 3517: 3507: 3506: 3500: 3495: 3488: 3485: 3480: 3462: 3461: 3456: 3447: 3446: 3441: 3428: 3426: 3425: 3420: 3418: 3417: 3412: 3400:Arbitrarily set 3396: 3394: 3393: 3388: 3386: 3385: 3380: 3374: 3372: 3371: 3370: 3365: 3355: 3354: 3348: 3343: 3336: 3335: 3334: 3329: 3319: 3318: 3312: 3307: 3300: 3295: 3294: 3289: 3280: 3279: 3274: 3261: 3259: 3258: 3253: 3251: 3250: 3245: 3233:Arbitrarily set 3229: 3227: 3226: 3221: 3219: 3218: 3213: 3201:Arbitrarily set 3192: 3190: 3189: 3184: 3166: 3164: 3163: 3158: 3150: 3149: 3144: 3137: 3136: 3130: 3125: 3112: 3110: 3109: 3104: 3086: 3084: 3083: 3078: 3070: 3069: 3064: 3057: 3056: 3050: 3045: 3027: 3025: 3024: 3019: 2998: 2996: 2995: 2990: 2975: 2973: 2972: 2967: 2954: 2952: 2951: 2946: 2944: 2943: 2938: 2928: 2927: 2921: 2916: 2891: 2889: 2888: 2883: 2870: 2868: 2867: 2862: 2860: 2859: 2854: 2844: 2843: 2837: 2832: 2818: 2816: 2815: 2810: 2808: 2807: 2802: 2792: 2791: 2785: 2780: 2757: 2755: 2754: 2749: 2736: 2734: 2733: 2728: 2726: 2725: 2720: 2710: 2709: 2703: 2698: 2684: 2682: 2681: 2676: 2674: 2673: 2668: 2658: 2657: 2651: 2646: 2632: 2630: 2629: 2624: 2622: 2621: 2616: 2606: 2605: 2599: 2594: 2573: 2571: 2570: 2565: 2538: 2535: 2520: 2518: 2517: 2512: 2504: 2503: 2498: 2489: 2488: 2483: 2474: 2473: 2468: 2452: 2450: 2449: 2444: 2426: 2424: 2423: 2418: 2410: 2409: 2404: 2394: 2393: 2387: 2382: 2369: 2367: 2366: 2361: 2339: 2334: 2313: 2299: 2298: 2286: 2285: 2280: 2271: 2270: 2265: 2259: 2258: 2246: 2241: 2240: 2239: 2229: 2228: 2216: 2215: 2210: 2201: 2200: 2195: 2189: 2188: 2169: 2167: 2166: 2161: 2159: 2144: 2142: 2141: 2136: 2134: 2123: 2118: 2113: 2112: 2111: 2105: 2092: 2090: 2089: 2084: 2072: 2070: 2069: 2064: 2056: 2051: 2050: 2049: 2043: 2031: 2026: 2021: 2020: 2019: 2013: 1997: 1995: 1994: 1989: 1987: 1986: 1981: 1975: 1974: 1962: 1950: 1948: 1947: 1942: 1940: 1939: 1923: 1921: 1920: 1915: 1913: 1912: 1907: 1891: 1889: 1888: 1883: 1881: 1869: 1867: 1866: 1861: 1844: 1843: 1838: 1822: 1820: 1819: 1814: 1812: 1811: 1806: 1800: 1799: 1787: 1775: 1773: 1772: 1767: 1751: 1749: 1748: 1743: 1741: 1740: 1729: 1723: 1722: 1698: 1697: 1692: 1686: 1685: 1637: 1635: 1634: 1629: 1617: 1615: 1614: 1609: 1592: 1590: 1589: 1584: 1576: 1575: 1570: 1561: 1560: 1555: 1546: 1545: 1540: 1519: 1517: 1516: 1511: 1503: 1502: 1497: 1488: 1487: 1482: 1473: 1472: 1467: 1454: 1452: 1451: 1446: 1438: 1437: 1421: 1419: 1418: 1413: 1411: 1410: 1405: 1399: 1394: 1393: 1381: 1380: 1375: 1363: 1362: 1357: 1351: 1350: 1338: 1337: 1332: 1323: 1315: 1307: 1306: 1295: 1283: 1275: 1274: 1263: 1250: 1248: 1247: 1242: 1234: 1233: 1228: 1219: 1218: 1213: 1204: 1203: 1198: 1182: 1180: 1179: 1174: 1172: 1168: 1167: 1162: 1153: 1152: 1140: 1139: 1134: 1121: 1120: 1109: 1099: 1096: 1094: 1093: 1088: 1082: 1081: 1069: 1068: 1063: 1050: 1049: 1038: 1028: 1025: 1023: 1021: 1020: 1019: 1014: 1004: 1003: 997: 992: 985: 984: 983: 978: 971: 970: 964: 959: 952: 943: 942: 920:, then iterate: 919: 917: 916: 911: 909: 908: 903: 891: 883: 882: 877: 864: 862: 861: 856: 854: 853: 848: 829: 827: 826: 821: 819: 818: 802: 800: 799: 794: 792: 791: 786: 773: 771: 770: 765: 763: 762: 757: 751: 750: 738: 737: 732: 723: 722: 717: 700: 698: 697: 692: 690: 689: 684: 671: 669: 668: 663: 661: 659: 658: 657: 652: 646: 640: 639: 633: 628: 621: 617: 616: 611: 599: 590: 589: 583: 578: 571: 566: 565: 549: 547: 546: 541: 536: 535: 526: 525: 520: 511: 510: 505: 486: 484: 483: 478: 476: 475: 470: 457: 455: 454: 449: 447: 446: 441: 421: 419: 418: 413: 411: 410: 402: 386: 384: 383: 378: 366: 364: 363: 358: 346: 344: 343: 338: 330: 325: 324: 323: 317: 305: 300: 295: 294: 293: 287: 252: 250: 249: 244: 242: 239: 237: 232: 231: 230: 224: 212: 207: 202: 201: 200: 194: 182: 130: 128: 127: 122: 120: 119: 111: 91: 89: 88: 83: 81: 66: 64: 63: 58: 56: 48: 26:iterative method 13655: 13654: 13650: 13649: 13648: 13646: 13645: 13644: 13620: 13619: 13618: 13613: 13572: 13568:Multiprocessing 13536: 13532:Sparse problems 13495: 13474: 13469: 13434: 13385: 13375:Hestenes, M. R. 13370: 13369: 13361: 13357: 13352: 13330: 13329: 13324: 13315: 13310: 13309: 13302: 13301: 13296: 13291: 13289: 13276: 13271: 13270: 13263: 13262: 13251: 13246: 13244: 13242: 13233: 13232: 13223: 13215: 13214: 13207: 13206: 13201: 13196: 13189: 13185: 13184: 13168: 13163: 13162: 13153: 13148: 13147: 13137: 13136: 13125: 13120: 13118: 13116: 13104: 13103: 13094: 13086: 13085: 13078: 13077: 13072: 13067: 13065: 13058: 13050: 13049: 13042: 13041: 13030: 13025: 13023: 13021: 13011: 13005: 13001: 12997: 12995: 12992: 12991: 12987:. As a result, 12965: 12957: 12956: 12949: 12948: 12944: 12938: 12933: 12932: 12926: 12922: 12907: 12902: 12901: 12889: 12881: 12880: 12873: 12872: 12861: 12856: 12853: 12850: 12849: 12832: 12827: 12826: 12824: 12821: 12820: 12803: 12802: 12797: 12788: 12780: 12779: 12772: 12771: 12766: 12761: 12759: 12752: 12747: 12746: 12739: 12738: 12733: 12728: 12726: 12724: 12715: 12714: 12705: 12697: 12696: 12689: 12688: 12684: 12672: 12667: 12666: 12654: 12650: 12641: 12636: 12635: 12631: 12624: 12619: 12618: 12611: 12610: 12605: 12600: 12598: 12596: 12587: 12586: 12577: 12569: 12568: 12561: 12560: 12555: 12550: 12548: 12541: 12536: 12535: 12528: 12527: 12522: 12517: 12515: 12513: 12506: 12500: 12496: 12492: 12490: 12487: 12486: 12482:. As a result, 12460: 12455: 12454: 12447: 12446: 12442: 12436: 12428: 12427: 12421: 12417: 12408: 12403: 12402: 12390: 12385: 12384: 12377: 12376: 12365: 12360: 12357: 12354: 12353: 12336: 12331: 12330: 12328: 12325: 12324: 12304: 12299: 12298: 12296: 12293: 12292: 12275: 12270: 12269: 12267: 12264: 12263: 12246: 12241: 12240: 12238: 12235: 12234: 12217: 12213: 12211: 12208: 12207: 12190: 12186: 12184: 12181: 12180: 12160: 12159: 12153: 12148: 12147: 12140: 12136: 12131: 12126: 12116: 12115: 12106: 12101: 12096: 12089: 12084: 12083: 12077: 12072: 12071: 12064: 12060: 12055: 12050: 12040: 12039: 12030: 12025: 12020: 12013: 12008: 12007: 12000: 11996: 11991: 11986: 11976: 11975: 11966: 11961: 11956: 11949: 11941: 11940: 11933: 11932: 11927: 11922: 11914: 11910: 11905: 11900: 11892: 11886: 11878: 11877: 11870: 11869: 11864: 11859: 11854: 11852: 11849: 11848: 11828: 11820: 11819: 11812: 11811: 11806: 11801: 11798: 11795: 11794: 11777: 11772: 11771: 11769: 11766: 11765: 11748: 11747: 11742: 11730: 11725: 11724: 11715: 11710: 11709: 11702: 11701: 11696: 11691: 11669: 11665: 11653: 11652: 11640: 11635: 11634: 11625: 11620: 11619: 11612: 11611: 11606: 11601: 11579: 11575: 11563: 11558: 11557: 11551: 11547: 11541: 11536: 11535: 11523: 11518: 11517: 11508: 11503: 11502: 11496: 11492: 11486: 11481: 11480: 11468: 11467: 11455: 11450: 11449: 11440: 11435: 11434: 11427: 11426: 11421: 11416: 11394: 11390: 11381: 11376: 11375: 11369: 11364: 11363: 11357: 11352: 11351: 11342: 11337: 11336: 11327: 11326: 11320: 11315: 11314: 11308: 11297: 11296: 11295: 11283: 11278: 11277: 11268: 11263: 11262: 11253: 11252: 11246: 11241: 11240: 11234: 11226: 11225: 11216: 11211: 11210: 11201: 11200: 11191: 11186: 11185: 11179: 11174: 11173: 11164: 11159: 11158: 11150: 11142: 11133: 11132: 11126: 11118: 11117: 11109: 11102: 11096: 11091: 11090: 11086: 11084: 11081: 11080: 11055: 11052: 11051: 11034: 11029: 11028: 11022: 11018: 11012: 11007: 11006: 10994: 10989: 10988: 10986: 10983: 10982: 10960: 10957: 10956: 10933: 10928: 10927: 10925: 10922: 10921: 10904: 10899: 10898: 10896: 10893: 10892: 10875: 10874: 10869: 10859: 10853: 10845: 10844: 10837: 10836: 10831: 10826: 10822: 10821: 10816: 10806: 10800: 10795: 10794: 10787: 10786: 10781: 10776: 10771: 10769: 10766: 10765: 10740: 10737: 10736: 10719: 10714: 10713: 10711: 10708: 10707: 10690: 10685: 10684: 10682: 10679: 10678: 10661: 10660: 10655: 10643: 10638: 10637: 10625: 10621: 10612: 10607: 10606: 10599: 10593: 10588: 10587: 10584: 10583: 10578: 10566: 10558: 10557: 10545: 10541: 10526: 10521: 10520: 10513: 10507: 10502: 10501: 10498: 10497: 10492: 10480: 10475: 10474: 10462: 10458: 10443: 10438: 10437: 10430: 10424: 10419: 10418: 10414: 10412: 10409: 10408: 10388: 10383: 10382: 10380: 10377: 10376: 10373: 10351: 10350: 10345: 10339: 10334: 10333: 10327: 10323: 10308: 10303: 10302: 10293: 10292: 10286: 10281: 10280: 10274: 10270: 10255: 10250: 10249: 10237: 10232: 10231: 10222: 10217: 10216: 10207: 10206: 10200: 10195: 10194: 10188: 10183: 10182: 10173: 10168: 10167: 10160: 10154: 10149: 10148: 10144: 10142: 10139: 10138: 10118: 10113: 10112: 10110: 10107: 10106: 10089: 10088: 10083: 10071: 10067: 10061: 10057: 10047: 10041: 10037: 10034: 10033: 10028: 10013: 10008: 10007: 10001: 9997: 9988: 9983: 9982: 9971: 9967: 9962: 9955: 9949: 9944: 9943: 9939: 9937: 9934: 9933: 9913: 9909: 9907: 9904: 9903: 9886: 9881: 9880: 9878: 9875: 9874: 9857: 9856: 9851: 9844: 9843: 9837: 9833: 9830: 9829: 9817: 9812: 9811: 9804: 9803: 9796: 9790: 9785: 9784: 9781: 9780: 9775: 9768: 9767: 9761: 9756: 9755: 9753: 9741: 9736: 9735: 9728: 9727: 9720: 9714: 9709: 9708: 9704: 9702: 9699: 9698: 9678: 9677: 9672: 9663: 9658: 9657: 9651: 9647: 9641: 9636: 9635: 9620: 9615: 9610: 9602: 9596: 9591: 9590: 9587: 9586: 9581: 9572: 9567: 9562: 9555: 9550: 9549: 9542: 9536: 9531: 9530: 9526: 9524: 9521: 9520: 9500: 9499: 9493: 9488: 9487: 9481: 9476: 9475: 9466: 9461: 9460: 9451: 9450: 9441: 9436: 9435: 9429: 9425: 9419: 9414: 9413: 9398: 9393: 9388: 9378: 9373: 9368: 9361: 9356: 9355: 9346: 9341: 9340: 9331: 9330: 9321: 9316: 9315: 9309: 9305: 9299: 9294: 9293: 9278: 9273: 9268: 9261: 9256: 9255: 9246: 9241: 9240: 9233: 9227: 9222: 9221: 9217: 9215: 9212: 9211: 9191: 9186: 9185: 9179: 9174: 9173: 9164: 9159: 9158: 9149: 9144: 9143: 9141: 9138: 9137: 9120: 9119: 9113: 9112: 9107: 9093: 9091: 9085: 9081: 9075: 9071: 9062: 9058: 9055: 9054: 9049: 9035: 9033: 9027: 9023: 9016: 9015: 9008: 9002: 8998: 8995: 8994: 8989: 8977: 8973: 8968: 8962: 8958: 8951: 8945: 8941: 8937: 8935: 8932: 8931: 8911: 8907: 8905: 8902: 8901: 8884: 8880: 8878: 8875: 8874: 8853: 8852: 8846: 8842: 8835: 8834: 8828: 8824: 8822: 8810: 8806: 8800: 8799: 8794: 8786: 8785: 8779: 8775: 8773: 8767: 8763: 8759: 8758: 8752: 8748: 8746: 8740: 8736: 8729: 8728: 8721: 8720: 8715: 8709: 8705: 8699: 8698: 8693: 8681: 8677: 8672: 8671: 8666: 8659: 8658: 8653: 8647: 8643: 8640: 8639: 8629: 8628: 8619: 8614: 8613: 8607: 8602: 8601: 8592: 8587: 8586: 8584: 8581: 8580: 8552: 8547: 8546: 8544: 8541: 8540: 8523: 8518: 8517: 8515: 8512: 8511: 8495: 8493: 8490: 8489: 8469: 8464: 8463: 8461: 8458: 8457: 8438: 8431: 8430: 8424: 8420: 8418: 8412: 8408: 8402: 8401: 8395: 8391: 8389: 8377: 8373: 8371: 8359: 8355: 8350: 8349: 8344: 8339: 8332: 8331: 8325: 8321: 8319: 8313: 8309: 8307: 8301: 8297: 8294: 8293: 8287: 8283: 8281: 8275: 8271: 8264: 8263: 8254: 8249: 8248: 8246: 8243: 8242: 8222: 8214: 8213: 8206: 8205: 8200: 8195: 8185: 8180: 8179: 8177: 8174: 8173: 8154: 8152: 8149: 8148: 8132: 8130: 8127: 8126: 8123: 8101: 8096: 8095: 8089: 8084: 8083: 8074: 8069: 8068: 8059: 8054: 8053: 8051: 8048: 8047: 8027: 8022: 8021: 8015: 8011: 8005: 8000: 7999: 7984: 7979: 7974: 7964: 7959: 7958: 7956: 7953: 7952: 7935: 7930: 7929: 7927: 7924: 7923: 7906: 7898: 7897: 7889: 7880: 7875: 7874: 7872: 7869: 7868: 7848: 7847: 7842: 7822: 7820: 7814: 7813: 7808: 7788: 7786: 7780: 7776: 7764: 7759: 7758: 7752: 7751: 7746: 7732: 7730: 7724: 7716: 7715: 7708: 7707: 7702: 7697: 7689: 7688: 7676: 7672: 7670: 7667: 7666: 7646: 7645: 7638: 7637: 7630: 7629: 7624: 7619: 7600: 7596: 7593: 7592: 7586: 7581: 7580: 7573: 7572: 7562: 7561: 7543: 7539: 7532: 7531: 7519: 7515: 7513: 7495: 7491: 7485: 7484: 7479: 7474: 7466: 7465: 7453: 7449: 7447: 7442: 7436: 7432: 7430: 7424: 7420: 7416: 7415: 7403: 7399: 7397: 7392: 7386: 7382: 7380: 7374: 7370: 7368: 7362: 7358: 7355: 7354: 7342: 7338: 7336: 7331: 7325: 7321: 7319: 7313: 7309: 7307: 7301: 7297: 7290: 7289: 7282: 7276: 7265: 7264: 7263: 7260: 7259: 7254: 7247: 7246: 7240: 7235: 7234: 7232: 7227: 7221: 7216: 7215: 7213: 7207: 7202: 7201: 7194: 7193: 7186: 7180: 7175: 7174: 7170: 7168: 7165: 7164: 7141: 7130: 7129: 7128: 7116: 7111: 7110: 7101: 7093: 7092: 7090: 7087: 7086: 7054: 7049: 7048: 7033: 7028: 7027: 7018: 7013: 7012: 7007: 7004: 7003: 6980: 6972: 6971: 6969: 6966: 6965: 6945: 6940: 6939: 6937: 6934: 6933: 6911: 6908: 6907: 6887: 6886: 6881: 6867: 6865: 6859: 6854: 6853: 6838: 6830: 6829: 6822: 6821: 6816: 6811: 6795: 6784: 6765: 6757: 6756: 6753: 6752: 6747: 6733: 6731: 6725: 6720: 6719: 6712: 6711: 6702: 6697: 6696: 6694: 6691: 6690: 6670: 6666: 6660: 6655: 6654: 6646: 6640: 6635: 6634: 6625: 6620: 6619: 6617: 6614: 6613: 6584: 6579: 6578: 6572: 6567: 6566: 6557: 6549: 6548: 6539: 6534: 6533: 6516: 6504: 6499: 6498: 6490: 6481: 6480: 6478: 6475: 6474: 6469:Krylov subspace 6442: 6437: 6436: 6427: 6422: 6421: 6412: 6407: 6406: 6401: 6398: 6397: 6376: 6371: 6370: 6368: 6365: 6364: 6361: 6353: 6343: 6321: 6316: 6315: 6306: 6301: 6300: 6294: 6289: 6284: 6282: 6269: 6264: 6263: 6257: 6246: 6241: 6239: 6237: 6222: 6217: 6216: 6201: 6196: 6195: 6193: 6190: 6189: 6169: 6164: 6163: 6158: 6152: 6147: 6142: 6140: 6133: 6128: 6127: 6121: 6116: 6111: 6109: 6107: 6098: 6094: 6092: 6089: 6088: 6086: 6065: 6061: 6048: 6043: 6042: 6033: 6028: 6027: 6026: 6024: 6018: 6007: 6002: 5992: 5987: 5986: 5981: 5975: 5964: 5959: 5956: 5953: 5952: 5935: 5927: 5926: 5920: 5916: 5907: 5902: 5901: 5886: 5881: 5880: 5878: 5875: 5874: 5851: 5850: 5831: 5827: 5822: 5810: 5805: 5804: 5798: 5787: 5782: 5775: 5774: 5751: 5750: 5735: 5727: 5726: 5719: 5718: 5713: 5708: 5705: 5702: 5701: 5679: 5674: 5673: 5664: 5656: 5655: 5648: 5647: 5642: 5637: 5635: 5622: 5614: 5613: 5606: 5605: 5600: 5595: 5593: 5591: 5579: 5568: 5555: 5550: 5549: 5540: 5535: 5534: 5532: 5529: 5528: 5505: 5500: 5499: 5493: 5488: 5483: 5473: 5468: 5467: 5461: 5456: 5451: 5448: 5445: 5444: 5416: 5411: 5410: 5395: 5390: 5389: 5380: 5375: 5374: 5372: 5369: 5368: 5345: 5340: 5339: 5324: 5319: 5318: 5309: 5304: 5303: 5301: 5298: 5297: 5258: 5253: 5252: 5246: 5241: 5236: 5233: 5230: 5229: 5212: 5207: 5206: 5204: 5201: 5200: 5177: 5172: 5171: 5156: 5151: 5150: 5141: 5136: 5135: 5133: 5130: 5129: 5112: 5107: 5106: 5104: 5101: 5100: 5055: 5050: 5049: 5043: 5038: 5033: 5030: 5027: 5026: 4987: 4982: 4981: 4975: 4970: 4965: 4962: 4959: 4958: 4950: 4928: 4923: 4922: 4907: 4902: 4901: 4899: 4896: 4895: 4857: 4852: 4851: 4840: 4837: 4836: 4813: 4809: 4807: 4804: 4803: 4786: 4785: 4780: 4768: 4763: 4762: 4757: 4753: 4752: 4732: 4731: 4725: 4720: 4719: 4710: 4702: 4701: 4694: 4693: 4688: 4683: 4681: 4668: 4660: 4659: 4652: 4651: 4646: 4641: 4639: 4637: 4631: 4620: 4601: 4596: 4595: 4580: 4575: 4574: 4569: 4568: 4562: 4554: 4553: 4547: 4543: 4534: 4529: 4528: 4513: 4508: 4507: 4502: 4501: 4496: 4491: 4485: 4481: 4476: 4471: 4466: 4465: 4459: 4454: 4453: 4447: 4443: 4434: 4429: 4428: 4413: 4408: 4407: 4402: 4401: 4392: 4384: 4383: 4376: 4375: 4370: 4365: 4363: 4356: 4351: 4350: 4343: 4342: 4337: 4332: 4330: 4328: 4319: 4315: 4310: 4309: 4295: 4291: 4290: 4277: 4276: 4270: 4265: 4264: 4255: 4250: 4249: 4245: 4244: 4238: 4230: 4229: 4221: 4212: 4207: 4206: 4201: 4199: 4196: 4195: 4178: 4173: 4172: 4163: 4155: 4154: 4147: 4146: 4141: 4136: 4134: 4127: 4119: 4118: 4111: 4110: 4105: 4100: 4098: 4096: 4084: 4073: 4060: 4055: 4054: 4045: 4040: 4039: 4037: 4034: 4033: 4016: 4008: 4007: 3999: 3990: 3985: 3984: 3969: 3964: 3963: 3961: 3958: 3957: 3938: 3930: 3927: 3926: 3906: 3901: 3900: 3876: 3871: 3870: 3868: 3865: 3864: 3841: 3836: 3835: 3833: 3830: 3829: 3808: 3803: 3802: 3793: 3785: 3784: 3777: 3776: 3771: 3766: 3764: 3745: 3737: 3736: 3729: 3728: 3723: 3718: 3716: 3714: 3702: 3691: 3666: 3661: 3660: 3645: 3640: 3639: 3637: 3634: 3633: 3604: 3599: 3598: 3596: 3593: 3592: 3569: 3564: 3563: 3554: 3546: 3545: 3538: 3537: 3532: 3527: 3525: 3518: 3510: 3509: 3502: 3501: 3496: 3491: 3489: 3487: 3481: 3470: 3457: 3452: 3451: 3442: 3437: 3436: 3434: 3431: 3430: 3413: 3408: 3407: 3405: 3402: 3401: 3381: 3376: 3375: 3366: 3358: 3357: 3350: 3349: 3344: 3339: 3337: 3330: 3322: 3321: 3314: 3313: 3308: 3303: 3301: 3299: 3290: 3285: 3284: 3275: 3270: 3269: 3267: 3264: 3263: 3246: 3241: 3240: 3238: 3235: 3234: 3214: 3209: 3208: 3206: 3203: 3202: 3172: 3169: 3168: 3145: 3140: 3139: 3132: 3131: 3126: 3121: 3118: 3115: 3114: 3092: 3089: 3088: 3065: 3060: 3059: 3052: 3051: 3046: 3041: 3038: 3035: 3034: 3013: 3010: 3009: 2984: 2981: 2980: 2961: 2958: 2957: 2939: 2931: 2930: 2923: 2922: 2917: 2912: 2909: 2906: 2905: 2877: 2874: 2873: 2855: 2847: 2846: 2839: 2838: 2833: 2828: 2825: 2822: 2821: 2803: 2795: 2794: 2787: 2786: 2781: 2776: 2773: 2770: 2769: 2743: 2740: 2739: 2721: 2713: 2712: 2705: 2704: 2699: 2694: 2691: 2688: 2687: 2669: 2661: 2660: 2653: 2652: 2647: 2642: 2639: 2636: 2635: 2617: 2609: 2608: 2601: 2600: 2595: 2590: 2587: 2584: 2583: 2559: 2556: 2555: 2531: 2499: 2494: 2493: 2484: 2479: 2478: 2469: 2464: 2463: 2461: 2458: 2457: 2432: 2429: 2428: 2405: 2397: 2396: 2389: 2388: 2383: 2378: 2375: 2372: 2371: 2335: 2330: 2306: 2294: 2290: 2281: 2276: 2275: 2266: 2261: 2260: 2254: 2250: 2242: 2235: 2234: 2230: 2224: 2220: 2211: 2206: 2205: 2196: 2191: 2190: 2184: 2180: 2175: 2172: 2171: 2152: 2150: 2147: 2146: 2127: 2119: 2114: 2107: 2106: 2101: 2100: 2098: 2095: 2094: 2078: 2075: 2074: 2052: 2045: 2044: 2039: 2038: 2027: 2022: 2015: 2014: 2009: 2008: 2006: 2003: 2002: 1982: 1977: 1976: 1970: 1966: 1958: 1956: 1953: 1952: 1935: 1931: 1929: 1926: 1925: 1908: 1903: 1902: 1900: 1897: 1896: 1877: 1875: 1872: 1871: 1839: 1834: 1833: 1828: 1825: 1824: 1807: 1802: 1801: 1795: 1791: 1783: 1781: 1778: 1777: 1761: 1758: 1757: 1730: 1725: 1724: 1712: 1708: 1693: 1688: 1687: 1681: 1677: 1675: 1672: 1671: 1623: 1620: 1619: 1603: 1600: 1599: 1571: 1566: 1565: 1556: 1551: 1550: 1541: 1536: 1535: 1533: 1530: 1529: 1526: 1498: 1493: 1492: 1483: 1478: 1477: 1468: 1463: 1462: 1460: 1457: 1456: 1433: 1429: 1427: 1424: 1423: 1406: 1401: 1400: 1395: 1389: 1385: 1376: 1371: 1370: 1358: 1353: 1352: 1346: 1342: 1333: 1328: 1327: 1319: 1311: 1296: 1288: 1287: 1279: 1264: 1259: 1258: 1256: 1253: 1252: 1229: 1224: 1223: 1214: 1209: 1208: 1199: 1194: 1193: 1191: 1188: 1187: 1170: 1169: 1163: 1155: 1154: 1148: 1144: 1135: 1130: 1129: 1122: 1110: 1105: 1104: 1101: 1100: 1095: 1089: 1084: 1083: 1077: 1073: 1064: 1059: 1058: 1051: 1039: 1034: 1033: 1030: 1029: 1024: 1015: 1007: 1006: 999: 998: 993: 988: 986: 979: 974: 973: 966: 965: 960: 955: 953: 951: 944: 938: 934: 930: 928: 925: 924: 904: 896: 895: 887: 878: 873: 872: 870: 867: 866: 849: 844: 843: 841: 838: 837: 814: 810: 808: 805: 804: 787: 782: 781: 779: 776: 775: 758: 753: 752: 746: 742: 733: 728: 727: 718: 713: 712: 710: 707: 706: 685: 680: 679: 677: 674: 673: 653: 648: 647: 642: 635: 634: 629: 624: 622: 612: 604: 603: 595: 585: 584: 579: 574: 572: 570: 561: 557: 555: 552: 551: 531: 527: 521: 516: 515: 506: 501: 500: 492: 489: 488: 471: 466: 465: 463: 460: 459: 442: 437: 436: 434: 431: 430: 403: 398: 397: 395: 392: 391: 372: 369: 368: 352: 349: 348: 326: 319: 318: 313: 312: 301: 296: 289: 288: 283: 282: 280: 277: 276: 262: 238: 233: 226: 225: 220: 219: 208: 203: 196: 195: 190: 189: 178: 170: 167: 166: 160: 112: 107: 106: 104: 101: 100: 77: 75: 72: 71: 52: 41: 39: 36: 35: 12: 11: 5: 13653: 13643: 13642: 13637: 13632: 13615: 13614: 13612: 13611: 13606: 13601: 13596: 13591: 13586: 13580: 13578: 13574: 13573: 13571: 13570: 13565: 13560: 13555: 13550: 13544: 13542: 13538: 13537: 13535: 13534: 13529: 13524: 13514: 13509: 13503: 13501: 13497: 13496: 13494: 13493: 13488: 13486:Floating point 13482: 13480: 13476: 13475: 13468: 13467: 13460: 13453: 13445: 13439: 13438: 13432: 13415: 13406: 13368: 13367: 13354: 13353: 13351: 13348: 13344: 13343: 13318: 13313: 13305: 13299: 13294: 13285: 13282: 13279: 13274: 13266: 13260: 13257: 13254: 13249: 13241: 13238: 13236: 13234: 13226: 13221: 13218: 13210: 13204: 13199: 13192: 13188: 13182: 13177: 13174: 13171: 13166: 13161: 13156: 13151: 13146: 13140: 13134: 13131: 13128: 13123: 13115: 13112: 13109: 13107: 13105: 13097: 13092: 13089: 13081: 13075: 13070: 13061: 13056: 13053: 13045: 13039: 13036: 13033: 13028: 13020: 13017: 13014: 13012: 13008: 13004: 13000: 12999: 12976: 12973: 12968: 12963: 12960: 12952: 12947: 12941: 12936: 12929: 12925: 12921: 12916: 12913: 12910: 12905: 12900: 12897: 12892: 12887: 12884: 12876: 12870: 12867: 12864: 12859: 12835: 12830: 12817: 12816: 12791: 12786: 12783: 12775: 12769: 12764: 12755: 12750: 12742: 12736: 12731: 12723: 12720: 12718: 12716: 12708: 12703: 12700: 12692: 12687: 12681: 12678: 12675: 12670: 12663: 12660: 12657: 12653: 12649: 12644: 12639: 12634: 12627: 12622: 12614: 12608: 12603: 12595: 12592: 12590: 12588: 12580: 12575: 12572: 12564: 12558: 12553: 12544: 12539: 12531: 12525: 12520: 12512: 12509: 12507: 12503: 12499: 12495: 12494: 12471: 12468: 12463: 12458: 12450: 12445: 12439: 12434: 12431: 12424: 12420: 12416: 12411: 12406: 12401: 12398: 12393: 12388: 12380: 12374: 12371: 12368: 12363: 12339: 12334: 12307: 12302: 12278: 12273: 12249: 12244: 12220: 12216: 12193: 12189: 12174: 12173: 12156: 12151: 12143: 12139: 12134: 12129: 12124: 12121: 12119: 12117: 12112: 12109: 12104: 12099: 12092: 12087: 12080: 12075: 12067: 12063: 12058: 12053: 12048: 12045: 12043: 12041: 12036: 12033: 12028: 12023: 12016: 12011: 12003: 11999: 11994: 11989: 11984: 11981: 11979: 11977: 11972: 11969: 11964: 11959: 11952: 11947: 11944: 11936: 11930: 11925: 11917: 11913: 11908: 11903: 11898: 11895: 11893: 11889: 11884: 11881: 11873: 11867: 11862: 11857: 11856: 11831: 11826: 11823: 11815: 11809: 11804: 11780: 11775: 11762: 11761: 11739: 11736: 11733: 11728: 11723: 11718: 11713: 11705: 11699: 11694: 11689: 11684: 11681: 11678: 11675: 11672: 11668: 11664: 11661: 11658: 11656: 11654: 11649: 11646: 11643: 11638: 11633: 11628: 11623: 11615: 11609: 11604: 11599: 11594: 11591: 11588: 11585: 11582: 11578: 11574: 11571: 11566: 11561: 11554: 11550: 11544: 11539: 11534: 11531: 11526: 11521: 11516: 11511: 11506: 11499: 11495: 11489: 11484: 11479: 11476: 11473: 11471: 11469: 11464: 11461: 11458: 11453: 11448: 11443: 11438: 11430: 11424: 11419: 11414: 11409: 11406: 11403: 11400: 11397: 11393: 11389: 11384: 11379: 11372: 11367: 11360: 11355: 11350: 11345: 11340: 11335: 11332: 11330: 11328: 11323: 11318: 11311: 11304: 11301: 11292: 11289: 11286: 11281: 11276: 11271: 11266: 11261: 11258: 11256: 11254: 11249: 11244: 11237: 11232: 11229: 11224: 11219: 11214: 11209: 11206: 11204: 11202: 11199: 11194: 11189: 11182: 11177: 11172: 11167: 11162: 11157: 11153: 11149: 11145: 11141: 11138: 11136: 11134: 11129: 11124: 11121: 11116: 11112: 11108: 11105: 11103: 11099: 11094: 11089: 11088: 11065: 11062: 11059: 11037: 11032: 11025: 11021: 11015: 11010: 11005: 11002: 10997: 10992: 10970: 10967: 10964: 10942: 10939: 10936: 10931: 10907: 10902: 10889: 10888: 10868: 10865: 10862: 10860: 10856: 10851: 10848: 10840: 10834: 10829: 10824: 10823: 10815: 10812: 10809: 10807: 10803: 10798: 10790: 10784: 10779: 10774: 10773: 10750: 10747: 10744: 10722: 10717: 10693: 10688: 10675: 10674: 10652: 10649: 10646: 10641: 10634: 10631: 10628: 10624: 10620: 10615: 10610: 10605: 10602: 10600: 10596: 10591: 10586: 10585: 10575: 10572: 10569: 10564: 10561: 10554: 10551: 10548: 10544: 10540: 10535: 10532: 10529: 10524: 10519: 10516: 10514: 10510: 10505: 10500: 10499: 10489: 10486: 10483: 10478: 10471: 10468: 10465: 10461: 10457: 10452: 10449: 10446: 10441: 10436: 10433: 10431: 10427: 10422: 10417: 10416: 10391: 10386: 10372: 10369: 10365: 10364: 10342: 10337: 10330: 10326: 10322: 10317: 10314: 10311: 10306: 10301: 10298: 10296: 10294: 10289: 10284: 10277: 10273: 10269: 10264: 10261: 10258: 10253: 10246: 10243: 10240: 10235: 10230: 10225: 10220: 10215: 10212: 10210: 10208: 10203: 10198: 10191: 10186: 10181: 10176: 10171: 10166: 10163: 10161: 10157: 10152: 10147: 10146: 10121: 10116: 10103: 10102: 10080: 10077: 10074: 10070: 10064: 10060: 10056: 10053: 10050: 10048: 10044: 10040: 10036: 10035: 10027: 10022: 10019: 10016: 10011: 10004: 10000: 9996: 9991: 9986: 9981: 9974: 9970: 9966: 9961: 9958: 9956: 9952: 9947: 9942: 9941: 9916: 9912: 9889: 9884: 9871: 9870: 9848: 9840: 9836: 9832: 9831: 9826: 9823: 9820: 9815: 9810: 9809: 9807: 9802: 9799: 9797: 9793: 9788: 9783: 9782: 9772: 9764: 9759: 9754: 9750: 9747: 9744: 9739: 9734: 9733: 9731: 9726: 9723: 9721: 9717: 9712: 9707: 9706: 9692: 9691: 9671: 9666: 9661: 9654: 9650: 9644: 9639: 9634: 9631: 9626: 9623: 9618: 9613: 9608: 9605: 9603: 9599: 9594: 9589: 9588: 9578: 9575: 9570: 9565: 9558: 9553: 9548: 9545: 9543: 9539: 9534: 9529: 9528: 9514: 9513: 9496: 9491: 9484: 9479: 9474: 9469: 9464: 9459: 9456: 9454: 9452: 9449: 9444: 9439: 9432: 9428: 9422: 9417: 9412: 9409: 9404: 9401: 9396: 9391: 9384: 9381: 9376: 9371: 9364: 9359: 9354: 9349: 9344: 9339: 9336: 9334: 9332: 9329: 9324: 9319: 9312: 9308: 9302: 9297: 9292: 9289: 9284: 9281: 9276: 9271: 9264: 9259: 9254: 9249: 9244: 9239: 9236: 9234: 9230: 9225: 9220: 9219: 9194: 9189: 9182: 9177: 9172: 9167: 9162: 9157: 9152: 9147: 9134: 9133: 9116: 9106: 9103: 9100: 9092: 9088: 9084: 9078: 9074: 9070: 9065: 9061: 9057: 9056: 9048: 9045: 9042: 9034: 9030: 9026: 9022: 9021: 9019: 9014: 9011: 9009: 9005: 9001: 8997: 8996: 8986: 8983: 8980: 8976: 8971: 8965: 8961: 8957: 8954: 8952: 8948: 8944: 8940: 8939: 8914: 8910: 8887: 8883: 8871: 8870: 8857: 8849: 8845: 8841: 8836: 8831: 8827: 8823: 8819: 8816: 8813: 8809: 8805: 8801: 8798: 8795: 8793: 8790: 8787: 8782: 8778: 8774: 8770: 8766: 8762: 8760: 8755: 8751: 8747: 8743: 8739: 8735: 8734: 8732: 8725: 8719: 8716: 8712: 8708: 8704: 8700: 8697: 8694: 8690: 8687: 8684: 8680: 8676: 8673: 8670: 8667: 8665: 8662: 8660: 8657: 8654: 8650: 8646: 8642: 8641: 8638: 8635: 8634: 8632: 8627: 8622: 8617: 8610: 8605: 8600: 8595: 8590: 8555: 8550: 8526: 8521: 8498: 8472: 8467: 8454: 8453: 8435: 8427: 8423: 8419: 8415: 8411: 8407: 8403: 8398: 8394: 8390: 8386: 8383: 8380: 8376: 8372: 8368: 8365: 8362: 8358: 8354: 8351: 8348: 8345: 8343: 8340: 8338: 8335: 8333: 8328: 8324: 8320: 8316: 8312: 8308: 8304: 8300: 8296: 8295: 8290: 8286: 8282: 8278: 8274: 8270: 8269: 8267: 8262: 8257: 8252: 8225: 8220: 8217: 8209: 8203: 8198: 8193: 8188: 8183: 8157: 8135: 8122: 8119: 8104: 8099: 8092: 8087: 8082: 8077: 8072: 8067: 8062: 8057: 8035: 8030: 8025: 8018: 8014: 8008: 8003: 7998: 7995: 7990: 7987: 7982: 7977: 7972: 7967: 7962: 7938: 7933: 7909: 7904: 7901: 7896: 7892: 7888: 7883: 7878: 7865: 7864: 7851: 7841: 7838: 7835: 7832: 7829: 7821: 7819: 7816: 7815: 7807: 7804: 7801: 7798: 7795: 7787: 7783: 7779: 7773: 7770: 7767: 7762: 7757: 7754: 7753: 7745: 7742: 7739: 7731: 7727: 7722: 7719: 7711: 7705: 7700: 7695: 7694: 7692: 7687: 7682: 7679: 7675: 7660: 7659: 7642: 7633: 7627: 7622: 7615: 7612: 7609: 7606: 7603: 7599: 7595: 7594: 7589: 7584: 7579: 7578: 7576: 7571: 7566: 7558: 7555: 7552: 7549: 7546: 7542: 7538: 7533: 7528: 7525: 7522: 7518: 7514: 7510: 7507: 7504: 7501: 7498: 7494: 7490: 7486: 7483: 7480: 7478: 7475: 7473: 7470: 7467: 7462: 7459: 7456: 7452: 7448: 7446: 7443: 7439: 7435: 7431: 7427: 7423: 7419: 7417: 7412: 7409: 7406: 7402: 7398: 7396: 7393: 7389: 7385: 7381: 7377: 7373: 7369: 7365: 7361: 7357: 7356: 7351: 7348: 7345: 7341: 7337: 7335: 7332: 7328: 7324: 7320: 7316: 7312: 7308: 7304: 7300: 7296: 7295: 7293: 7288: 7285: 7283: 7279: 7272: 7269: 7262: 7261: 7251: 7243: 7238: 7233: 7231: 7228: 7224: 7219: 7214: 7210: 7205: 7200: 7199: 7197: 7192: 7189: 7187: 7183: 7178: 7173: 7172: 7158: 7157: 7144: 7137: 7134: 7125: 7122: 7119: 7114: 7109: 7104: 7099: 7096: 7068: 7063: 7060: 7057: 7052: 7047: 7044: 7041: 7036: 7031: 7026: 7021: 7016: 7011: 6989: 6986: 6983: 6978: 6975: 6948: 6943: 6921: 6918: 6915: 6904: 6903: 6890: 6880: 6877: 6874: 6866: 6862: 6857: 6852: 6847: 6844: 6841: 6836: 6833: 6825: 6819: 6814: 6809: 6804: 6801: 6798: 6793: 6790: 6787: 6783: 6779: 6774: 6771: 6768: 6763: 6760: 6755: 6754: 6746: 6743: 6740: 6732: 6728: 6723: 6718: 6717: 6715: 6710: 6705: 6700: 6673: 6669: 6663: 6658: 6653: 6649: 6643: 6638: 6633: 6628: 6623: 6610: 6609: 6598: 6595: 6592: 6587: 6582: 6575: 6570: 6565: 6560: 6555: 6552: 6547: 6542: 6537: 6532: 6528: 6525: 6522: 6519: 6515: 6512: 6507: 6502: 6497: 6493: 6489: 6484: 6456: 6453: 6450: 6445: 6440: 6435: 6430: 6425: 6420: 6415: 6410: 6405: 6379: 6374: 6360: 6357: 6342: 6339: 6324: 6319: 6309: 6304: 6297: 6292: 6287: 6278: 6275: 6272: 6267: 6260: 6255: 6252: 6249: 6244: 6236: 6231: 6228: 6225: 6220: 6215: 6210: 6207: 6204: 6199: 6172: 6167: 6161: 6155: 6150: 6145: 6136: 6131: 6124: 6119: 6114: 6106: 6101: 6097: 6068: 6064: 6057: 6054: 6051: 6046: 6041: 6036: 6031: 6021: 6016: 6013: 6010: 6005: 6000: 5995: 5990: 5984: 5978: 5973: 5970: 5967: 5962: 5938: 5933: 5930: 5923: 5919: 5915: 5910: 5905: 5900: 5895: 5892: 5889: 5884: 5854: 5849: 5846: 5843: 5839: 5834: 5830: 5825: 5819: 5816: 5813: 5808: 5801: 5796: 5793: 5790: 5785: 5780: 5777: 5776: 5773: 5770: 5767: 5763: 5760: 5757: 5756: 5754: 5749: 5744: 5741: 5738: 5733: 5730: 5722: 5716: 5711: 5682: 5677: 5667: 5662: 5659: 5651: 5645: 5640: 5631: 5628: 5625: 5620: 5617: 5609: 5603: 5598: 5588: 5585: 5582: 5577: 5574: 5571: 5567: 5563: 5558: 5553: 5548: 5543: 5538: 5508: 5503: 5496: 5491: 5486: 5481: 5476: 5471: 5464: 5459: 5454: 5425: 5422: 5419: 5414: 5409: 5406: 5403: 5398: 5393: 5388: 5383: 5378: 5354: 5351: 5348: 5343: 5338: 5335: 5332: 5327: 5322: 5317: 5312: 5307: 5285: 5282: 5279: 5276: 5272: 5269: 5266: 5261: 5256: 5249: 5244: 5239: 5215: 5210: 5186: 5183: 5180: 5175: 5170: 5167: 5164: 5159: 5154: 5149: 5144: 5139: 5115: 5110: 5082: 5079: 5076: 5073: 5069: 5066: 5063: 5058: 5053: 5046: 5041: 5036: 5014: 5011: 5008: 5005: 5001: 4998: 4995: 4990: 4985: 4978: 4973: 4968: 4949: 4948:Simplification 4946: 4931: 4926: 4921: 4916: 4913: 4910: 4905: 4877: 4874: 4871: 4866: 4863: 4860: 4855: 4850: 4847: 4844: 4824: 4821: 4816: 4812: 4777: 4774: 4771: 4766: 4756: 4754: 4751: 4748: 4745: 4742: 4739: 4735: 4733: 4728: 4723: 4713: 4708: 4705: 4697: 4691: 4686: 4677: 4674: 4671: 4666: 4663: 4655: 4649: 4644: 4634: 4629: 4626: 4623: 4619: 4615: 4610: 4607: 4604: 4599: 4594: 4589: 4586: 4583: 4578: 4572: 4570: 4565: 4560: 4557: 4550: 4546: 4542: 4537: 4532: 4527: 4522: 4519: 4516: 4511: 4505: 4503: 4494: 4488: 4484: 4479: 4469: 4467: 4462: 4457: 4450: 4446: 4442: 4437: 4432: 4427: 4422: 4419: 4416: 4411: 4405: 4403: 4395: 4390: 4387: 4379: 4373: 4368: 4359: 4354: 4346: 4340: 4335: 4327: 4322: 4318: 4313: 4311: 4308: 4305: 4302: 4297:do while 4294: 4292: 4289: 4286: 4283: 4280: 4278: 4273: 4268: 4263: 4258: 4253: 4248: 4246: 4241: 4236: 4233: 4228: 4224: 4220: 4215: 4210: 4205: 4203: 4181: 4176: 4166: 4161: 4158: 4150: 4144: 4139: 4130: 4125: 4122: 4114: 4108: 4103: 4093: 4090: 4087: 4082: 4079: 4076: 4072: 4068: 4063: 4058: 4053: 4048: 4043: 4032:Thus, we have 4019: 4014: 4011: 4006: 4002: 3998: 3993: 3988: 3983: 3978: 3975: 3972: 3967: 3945: 3941: 3937: 3934: 3914: 3909: 3904: 3899: 3896: 3893: 3890: 3885: 3882: 3879: 3874: 3850: 3847: 3844: 3839: 3826: 3825: 3811: 3806: 3796: 3791: 3788: 3780: 3774: 3769: 3760: 3757: 3754: 3751: 3748: 3743: 3740: 3732: 3726: 3721: 3711: 3708: 3705: 3700: 3697: 3694: 3690: 3686: 3681: 3678: 3675: 3672: 3669: 3664: 3659: 3654: 3651: 3648: 3643: 3619: 3616: 3613: 3610: 3607: 3602: 3589: 3586: 3572: 3567: 3557: 3552: 3549: 3541: 3535: 3530: 3521: 3516: 3513: 3505: 3499: 3494: 3484: 3479: 3476: 3473: 3469: 3465: 3460: 3455: 3450: 3445: 3440: 3416: 3411: 3398: 3384: 3379: 3369: 3364: 3361: 3353: 3347: 3342: 3333: 3328: 3325: 3317: 3311: 3306: 3298: 3293: 3288: 3283: 3278: 3273: 3249: 3244: 3231: 3217: 3212: 3182: 3179: 3176: 3156: 3153: 3148: 3143: 3135: 3129: 3124: 3102: 3099: 3096: 3076: 3073: 3068: 3063: 3055: 3049: 3044: 3029: 3028: 3017: 3007: 3005: 3003: 3001: 2999: 2988: 2977: 2976: 2965: 2955: 2942: 2937: 2934: 2926: 2920: 2915: 2903: 2901: 2899: 2897: 2893: 2892: 2881: 2871: 2858: 2853: 2850: 2842: 2836: 2831: 2819: 2806: 2801: 2798: 2790: 2784: 2779: 2767: 2765: 2763: 2759: 2758: 2747: 2737: 2724: 2719: 2716: 2708: 2702: 2697: 2685: 2672: 2667: 2664: 2656: 2650: 2645: 2633: 2620: 2615: 2612: 2604: 2598: 2593: 2581: 2579: 2575: 2574: 2563: 2553: 2550: 2547: 2544: 2541: 2530: 2527: 2510: 2507: 2502: 2497: 2492: 2487: 2482: 2477: 2472: 2467: 2442: 2439: 2436: 2416: 2413: 2408: 2403: 2400: 2392: 2386: 2381: 2359: 2356: 2353: 2350: 2346: 2343: 2338: 2333: 2329: 2325: 2322: 2319: 2316: 2312: 2309: 2305: 2302: 2297: 2293: 2289: 2284: 2279: 2274: 2269: 2264: 2257: 2253: 2249: 2245: 2238: 2233: 2227: 2223: 2219: 2214: 2209: 2204: 2199: 2194: 2187: 2183: 2179: 2158: 2155: 2133: 2130: 2126: 2122: 2117: 2110: 2104: 2082: 2062: 2059: 2055: 2048: 2042: 2037: 2034: 2030: 2025: 2018: 2012: 1985: 1980: 1973: 1969: 1965: 1961: 1938: 1934: 1911: 1906: 1880: 1859: 1856: 1853: 1850: 1847: 1842: 1837: 1832: 1810: 1805: 1798: 1794: 1790: 1786: 1765: 1754:parallelepiped 1739: 1736: 1733: 1728: 1721: 1718: 1715: 1711: 1707: 1704: 1701: 1696: 1691: 1684: 1680: 1627: 1607: 1582: 1579: 1574: 1569: 1564: 1559: 1554: 1549: 1544: 1539: 1525: 1522: 1509: 1506: 1501: 1496: 1491: 1486: 1481: 1476: 1471: 1466: 1444: 1441: 1436: 1432: 1409: 1404: 1398: 1392: 1388: 1384: 1379: 1374: 1369: 1366: 1361: 1356: 1349: 1345: 1341: 1336: 1331: 1326: 1322: 1318: 1314: 1310: 1305: 1302: 1299: 1294: 1291: 1286: 1282: 1278: 1273: 1270: 1267: 1262: 1240: 1237: 1232: 1227: 1222: 1217: 1212: 1207: 1202: 1197: 1184: 1183: 1166: 1161: 1158: 1151: 1147: 1143: 1138: 1133: 1128: 1125: 1123: 1119: 1116: 1113: 1108: 1103: 1102: 1092: 1087: 1080: 1076: 1072: 1067: 1062: 1057: 1054: 1052: 1048: 1045: 1042: 1037: 1032: 1031: 1018: 1013: 1010: 1002: 996: 991: 982: 977: 969: 963: 958: 950: 947: 945: 941: 937: 933: 932: 907: 902: 899: 894: 890: 886: 881: 876: 852: 847: 817: 813: 790: 785: 761: 756: 749: 745: 741: 736: 731: 726: 721: 716: 688: 683: 656: 651: 645: 638: 632: 627: 620: 615: 610: 607: 602: 598: 594: 588: 582: 577: 569: 564: 560: 539: 534: 530: 524: 519: 514: 509: 504: 499: 496: 474: 469: 445: 440: 409: 406: 401: 376: 356: 336: 333: 329: 322: 316: 311: 308: 304: 299: 292: 286: 261: 258: 254: 253: 236: 229: 223: 218: 215: 211: 206: 199: 193: 188: 185: 181: 177: 174: 159: 156: 147:iteration for 118: 115: 110: 80: 68: 67: 55: 51: 47: 44: 9: 6: 4: 3: 2: 13652: 13641: 13638: 13636: 13633: 13631: 13628: 13627: 13625: 13610: 13607: 13605: 13602: 13600: 13597: 13595: 13592: 13590: 13587: 13585: 13582: 13581: 13579: 13575: 13569: 13566: 13564: 13561: 13559: 13556: 13554: 13551: 13549: 13546: 13545: 13543: 13539: 13533: 13530: 13528: 13525: 13522: 13518: 13515: 13513: 13510: 13508: 13505: 13504: 13502: 13498: 13492: 13489: 13487: 13484: 13483: 13481: 13477: 13473: 13466: 13461: 13459: 13454: 13452: 13447: 13446: 13443: 13435: 13429: 13424: 13423: 13416: 13413: 13412: 13407: 13403: 13399: 13395: 13391: 13384: 13380: 13376: 13372: 13371: 13365: 13359: 13355: 13347: 13316: 13297: 13283: 13280: 13277: 13258: 13255: 13252: 13239: 13237: 13224: 13202: 13190: 13186: 13175: 13172: 13169: 13159: 13154: 13132: 13129: 13126: 13113: 13110: 13108: 13095: 13073: 13059: 13037: 13034: 13031: 13018: 13015: 13013: 13006: 13002: 12990: 12989: 12988: 12974: 12971: 12966: 12939: 12927: 12923: 12919: 12914: 12911: 12908: 12895: 12890: 12868: 12865: 12862: 12833: 12789: 12767: 12753: 12734: 12721: 12719: 12706: 12679: 12676: 12673: 12661: 12658: 12655: 12651: 12647: 12642: 12625: 12606: 12593: 12591: 12578: 12556: 12542: 12523: 12510: 12508: 12501: 12497: 12485: 12484: 12483: 12469: 12466: 12461: 12437: 12422: 12418: 12414: 12409: 12396: 12391: 12372: 12369: 12366: 12337: 12321: 12305: 12276: 12247: 12218: 12214: 12191: 12187: 12177: 12154: 12137: 12132: 12122: 12120: 12110: 12107: 12102: 12090: 12078: 12061: 12056: 12046: 12044: 12034: 12031: 12026: 12014: 11997: 11992: 11982: 11980: 11970: 11967: 11962: 11950: 11928: 11911: 11906: 11896: 11894: 11887: 11865: 11847: 11846: 11845: 11844:is diagonal: 11829: 11807: 11778: 11737: 11734: 11731: 11716: 11697: 11682: 11679: 11676: 11673: 11670: 11666: 11662: 11659: 11657: 11647: 11644: 11641: 11626: 11607: 11592: 11589: 11586: 11583: 11580: 11576: 11572: 11564: 11552: 11542: 11524: 11514: 11509: 11497: 11487: 11474: 11472: 11462: 11459: 11456: 11441: 11422: 11407: 11404: 11401: 11398: 11395: 11391: 11387: 11382: 11370: 11358: 11348: 11343: 11333: 11331: 11321: 11309: 11290: 11287: 11284: 11274: 11269: 11259: 11257: 11247: 11235: 11222: 11217: 11207: 11205: 11192: 11180: 11170: 11165: 11147: 11139: 11137: 11127: 11114: 11106: 11104: 11097: 11079: 11078: 11077: 11063: 11060: 11057: 11035: 11023: 11013: 11000: 10995: 10968: 10965: 10962: 10940: 10937: 10934: 10905: 10866: 10863: 10861: 10854: 10832: 10813: 10810: 10808: 10801: 10782: 10764: 10763: 10762: 10748: 10745: 10742: 10720: 10691: 10650: 10647: 10644: 10632: 10629: 10626: 10622: 10618: 10613: 10603: 10601: 10594: 10573: 10570: 10567: 10552: 10549: 10546: 10542: 10538: 10533: 10530: 10527: 10517: 10515: 10508: 10487: 10484: 10481: 10469: 10466: 10463: 10459: 10455: 10450: 10447: 10444: 10434: 10432: 10425: 10407: 10406: 10405: 10389: 10368: 10340: 10328: 10324: 10320: 10315: 10312: 10309: 10299: 10297: 10287: 10275: 10271: 10267: 10262: 10259: 10256: 10244: 10241: 10238: 10228: 10223: 10213: 10211: 10201: 10189: 10179: 10174: 10164: 10162: 10155: 10137: 10136: 10135: 10119: 10078: 10075: 10072: 10068: 10062: 10058: 10054: 10051: 10049: 10042: 10038: 10020: 10017: 10014: 10002: 9998: 9994: 9989: 9972: 9968: 9964: 9959: 9957: 9950: 9932: 9931: 9930: 9914: 9910: 9887: 9846: 9838: 9834: 9824: 9821: 9818: 9805: 9800: 9798: 9791: 9770: 9762: 9748: 9745: 9742: 9729: 9724: 9722: 9715: 9697: 9696: 9695: 9664: 9652: 9642: 9624: 9621: 9616: 9606: 9604: 9597: 9576: 9573: 9568: 9556: 9546: 9544: 9537: 9519: 9518: 9517: 9494: 9482: 9472: 9467: 9457: 9455: 9442: 9430: 9420: 9402: 9399: 9394: 9382: 9379: 9374: 9362: 9352: 9347: 9337: 9335: 9322: 9310: 9300: 9282: 9279: 9274: 9262: 9252: 9247: 9237: 9235: 9228: 9210: 9209: 9208: 9192: 9180: 9170: 9165: 9155: 9150: 9104: 9101: 9098: 9086: 9082: 9076: 9072: 9068: 9063: 9059: 9046: 9043: 9040: 9028: 9024: 9017: 9012: 9010: 9003: 8999: 8984: 8981: 8978: 8974: 8969: 8963: 8959: 8955: 8953: 8946: 8942: 8930: 8929: 8928: 8912: 8908: 8885: 8881: 8855: 8847: 8843: 8829: 8825: 8817: 8814: 8811: 8807: 8796: 8791: 8780: 8776: 8768: 8764: 8753: 8749: 8741: 8737: 8730: 8723: 8717: 8710: 8706: 8695: 8688: 8685: 8682: 8678: 8668: 8663: 8655: 8648: 8644: 8636: 8630: 8625: 8620: 8608: 8598: 8593: 8579: 8578: 8577: 8575: 8571: 8570:LU factorized 8553: 8524: 8486: 8470: 8433: 8425: 8421: 8413: 8409: 8396: 8392: 8384: 8381: 8378: 8374: 8366: 8363: 8360: 8356: 8346: 8341: 8336: 8326: 8322: 8314: 8310: 8302: 8298: 8288: 8284: 8276: 8272: 8265: 8260: 8255: 8241: 8240: 8239: 8223: 8201: 8191: 8186: 8172: 8118: 8102: 8090: 8080: 8075: 8065: 8060: 8028: 8016: 8006: 7988: 7985: 7980: 7970: 7965: 7936: 7907: 7894: 7886: 7881: 7839: 7836: 7833: 7830: 7827: 7817: 7805: 7802: 7799: 7796: 7793: 7781: 7771: 7768: 7765: 7743: 7740: 7737: 7725: 7703: 7690: 7685: 7680: 7677: 7673: 7665: 7664: 7663: 7640: 7625: 7613: 7610: 7607: 7604: 7601: 7597: 7587: 7574: 7569: 7564: 7556: 7553: 7550: 7547: 7544: 7540: 7526: 7523: 7520: 7516: 7508: 7505: 7502: 7499: 7496: 7492: 7481: 7476: 7471: 7460: 7457: 7454: 7450: 7444: 7437: 7433: 7425: 7421: 7410: 7407: 7404: 7400: 7394: 7387: 7383: 7375: 7371: 7363: 7359: 7349: 7346: 7343: 7339: 7333: 7326: 7322: 7314: 7310: 7302: 7298: 7291: 7286: 7284: 7277: 7249: 7241: 7229: 7222: 7208: 7195: 7190: 7188: 7181: 7163: 7162: 7161: 7142: 7123: 7120: 7117: 7107: 7102: 7085: 7084: 7083: 7080: 7061: 7058: 7055: 7045: 7042: 7039: 7034: 7024: 7019: 6987: 6984: 6981: 6964: 6946: 6919: 6916: 6913: 6878: 6875: 6872: 6860: 6845: 6842: 6839: 6817: 6802: 6799: 6796: 6791: 6788: 6785: 6781: 6777: 6772: 6769: 6766: 6744: 6741: 6738: 6726: 6713: 6708: 6703: 6689: 6688: 6687: 6671: 6661: 6647: 6641: 6631: 6626: 6593: 6590: 6585: 6573: 6563: 6558: 6545: 6540: 6513: 6505: 6495: 6473: 6472: 6471: 6470: 6451: 6448: 6443: 6433: 6428: 6418: 6413: 6395: 6377: 6356: 6352: 6348: 6338: 6322: 6307: 6290: 6276: 6273: 6270: 6253: 6250: 6247: 6234: 6229: 6226: 6223: 6213: 6208: 6205: 6202: 6170: 6148: 6134: 6117: 6104: 6099: 6095: 6084: 6066: 6062: 6055: 6052: 6049: 6039: 6034: 6019: 6014: 6011: 6008: 5998: 5993: 5976: 5971: 5968: 5965: 5936: 5921: 5917: 5913: 5908: 5898: 5893: 5890: 5887: 5872: 5868: 5847: 5844: 5841: 5837: 5832: 5828: 5823: 5817: 5814: 5811: 5799: 5794: 5791: 5788: 5778: 5771: 5768: 5765: 5761: 5758: 5752: 5747: 5742: 5739: 5736: 5714: 5700: 5696: 5680: 5665: 5643: 5629: 5626: 5623: 5601: 5586: 5583: 5580: 5575: 5572: 5569: 5565: 5561: 5556: 5546: 5541: 5526: 5522: 5506: 5494: 5489: 5479: 5474: 5462: 5457: 5443: 5439: 5423: 5420: 5417: 5407: 5404: 5401: 5396: 5386: 5381: 5352: 5349: 5346: 5336: 5333: 5330: 5325: 5315: 5310: 5283: 5280: 5277: 5270: 5267: 5264: 5259: 5247: 5242: 5213: 5184: 5181: 5178: 5168: 5165: 5162: 5157: 5147: 5142: 5113: 5098: 5094: 5080: 5077: 5074: 5067: 5064: 5061: 5056: 5044: 5039: 5012: 5009: 5006: 4999: 4996: 4993: 4988: 4976: 4971: 4957: 4953: 4945: 4929: 4919: 4914: 4911: 4908: 4893: 4889: 4875: 4872: 4864: 4861: 4858: 4845: 4822: 4819: 4814: 4810: 4801: 4775: 4772: 4769: 4749: 4746: 4743: 4740: 4737: 4726: 4711: 4689: 4675: 4672: 4669: 4647: 4632: 4627: 4624: 4621: 4617: 4613: 4608: 4605: 4602: 4592: 4587: 4584: 4581: 4563: 4548: 4544: 4540: 4535: 4525: 4520: 4517: 4514: 4486: 4482: 4460: 4448: 4444: 4440: 4435: 4425: 4420: 4417: 4414: 4393: 4371: 4357: 4338: 4325: 4320: 4316: 4306: 4303: 4300: 4287: 4284: 4281: 4271: 4261: 4256: 4239: 4226: 4218: 4213: 4179: 4164: 4142: 4128: 4106: 4091: 4088: 4085: 4080: 4077: 4074: 4070: 4066: 4061: 4051: 4046: 4017: 4004: 3996: 3991: 3981: 3976: 3973: 3970: 3943: 3939: 3935: 3932: 3907: 3894: 3888: 3883: 3880: 3877: 3848: 3845: 3842: 3809: 3794: 3772: 3758: 3755: 3752: 3749: 3746: 3724: 3709: 3706: 3703: 3698: 3695: 3692: 3688: 3684: 3679: 3676: 3673: 3670: 3667: 3657: 3652: 3649: 3646: 3617: 3614: 3611: 3608: 3605: 3590: 3587: 3570: 3555: 3533: 3519: 3497: 3482: 3477: 3474: 3471: 3467: 3463: 3458: 3448: 3443: 3414: 3399: 3382: 3367: 3345: 3331: 3309: 3296: 3291: 3281: 3276: 3247: 3232: 3215: 3200: 3199: 3198: 3196: 3180: 3177: 3174: 3154: 3151: 3146: 3127: 3100: 3097: 3094: 3074: 3071: 3066: 3047: 3015: 3008: 3006: 3004: 3002: 3000: 2986: 2979: 2978: 2963: 2956: 2940: 2918: 2904: 2902: 2900: 2898: 2895: 2894: 2879: 2872: 2856: 2834: 2820: 2804: 2782: 2768: 2766: 2764: 2761: 2760: 2745: 2738: 2722: 2700: 2686: 2670: 2648: 2634: 2618: 2596: 2582: 2580: 2577: 2576: 2561: 2554: 2551: 2548: 2545: 2542: 2540: 2539: 2534: 2526: 2524: 2508: 2505: 2500: 2490: 2485: 2475: 2470: 2454: 2440: 2437: 2434: 2414: 2411: 2406: 2384: 2357: 2354: 2351: 2344: 2336: 2331: 2327: 2323: 2317: 2314: 2310: 2307: 2303: 2295: 2291: 2287: 2282: 2272: 2267: 2255: 2251: 2225: 2221: 2217: 2212: 2202: 2197: 2185: 2181: 2156: 2153: 2131: 2128: 2124: 2080: 2060: 2057: 2035: 2032: 1999: 1983: 1971: 1967: 1963: 1936: 1932: 1909: 1893: 1854: 1851: 1848: 1845: 1840: 1808: 1796: 1792: 1788: 1763: 1755: 1737: 1734: 1731: 1719: 1716: 1713: 1709: 1705: 1702: 1699: 1694: 1682: 1678: 1669: 1665: 1656: 1652: 1651:parallelogram 1648: 1643: 1639: 1625: 1618:steps, where 1605: 1597: 1580: 1577: 1572: 1562: 1557: 1547: 1542: 1521: 1507: 1504: 1499: 1489: 1484: 1474: 1469: 1442: 1439: 1434: 1430: 1407: 1390: 1386: 1382: 1377: 1367: 1359: 1347: 1343: 1339: 1334: 1316: 1308: 1303: 1300: 1297: 1284: 1276: 1271: 1268: 1265: 1238: 1235: 1230: 1220: 1215: 1205: 1200: 1164: 1149: 1145: 1141: 1136: 1126: 1124: 1117: 1114: 1111: 1090: 1078: 1074: 1070: 1065: 1055: 1053: 1046: 1043: 1040: 1016: 994: 980: 961: 948: 946: 939: 935: 923: 922: 921: 905: 892: 884: 879: 850: 834: 831: 815: 811: 788: 759: 747: 743: 739: 734: 724: 719: 703: 686: 654: 630: 613: 600: 580: 567: 562: 558: 532: 528: 522: 512: 507: 494: 472: 443: 428: 423: 407: 404: 388: 374: 354: 334: 331: 309: 306: 274: 266: 257: 216: 213: 186: 172: 165: 164: 163: 155: 152: 150: 146: 142: 138: 134: 116: 113: 98: 95: 49: 34: 33: 32: 31: 30:linear system 27: 23: 19: 13479:Key concepts 13421: 13409: 13393: 13389: 13358: 13345: 12818: 12322: 12178: 12175: 11763: 10890: 10735:, i.e., for 10676: 10375:If we allow 10374: 10366: 10104: 9872: 9693: 9515: 9135: 8872: 8487: 8455: 8124: 7866: 7661: 7159: 7081: 6961:is found by 6905: 6612:by defining 6611: 6362: 6354: 6085: 5870: 5869: 5698: 5697: 5524: 5523: 5441: 5440: 5096: 5095: 4955: 4954: 4951: 4891: 4890: 4800:Proposition. 4799: 4759:return 3827: 3032: 2532: 2455: 2000: 1924:by a scalar 1894: 1667: 1663: 1660: 1595: 1527: 1185: 835: 832: 704: 424: 389: 347:for varying 270: 255: 161: 153: 137:optimization 69: 15: 13379:Stiefel, E. 6394:orthonormal 5199:. Further, 427:line search 260:Line search 13624:Categories 13521:algorithms 13396:(6): 409. 13350:References 10955:since for 1951:, so that 1670:semi-axes 803:, compute 273:ellipsoids 151:problems. 149:eigenvalue 13548:CPU cache 13414:." (1994) 13187:α 13160:− 13114:− 13019:− 13003:β 12924:β 12677:− 12659:− 12652:β 12648:− 12498:α 12419:α 12415:− 12215:β 12188:α 12138:− 12108:− 12062:− 12032:− 11998:− 11968:− 11912:− 11663:− 11573:− 11549:‖ 11533:‖ 11515:− 11494:‖ 11478:‖ 11388:− 11349:− 11303:~ 11275:− 11223:− 11148:− 11115:− 11020:‖ 11004:‖ 10746:≠ 10648:− 10630:− 10623:β 10571:− 10550:− 10543:α 10539:− 10531:− 10485:− 10467:− 10460:α 10448:− 10325:ζ 10313:− 10272:ζ 10260:− 10242:− 10076:− 10069:ζ 10055:− 10039:ζ 10018:− 9995:− 9929:as well: 9911:ζ 9835:ζ 9822:− 9746:− 9649:‖ 9633:‖ 9622:− 9574:− 9427:‖ 9411:‖ 9400:− 9380:− 9307:‖ 9291:‖ 9280:− 9069:− 8982:− 8815:− 8797:⋱ 8792:⋱ 8686:− 8669:⋱ 8664:⋱ 8539:. Hence, 8382:− 8364:− 8347:⋱ 8342:⋱ 8337:⋱ 8013:‖ 7997:‖ 7986:− 7895:− 7778:‖ 7756:‖ 7741:≤ 7506:− 7482:⋮ 7477:⋱ 7472:⋱ 7445:⋯ 7395:⋯ 7334:⋯ 7271:~ 7230:⋯ 7136:~ 7059:− 7043:… 6985:− 6843:− 6800:− 6782:∑ 6778:− 6770:− 6668:‖ 6652:‖ 6594:… 6452:… 6296:⊤ 6259:⊤ 6154:⊤ 6123:⊤ 6096:α 6063:α 6040:− 5918:α 5914:− 5829:α 5779:− 5627:− 5584:− 5566:∑ 5562:− 5421:− 5405:… 5350:− 5334:… 5275:∀ 5182:− 5166:… 5072:∀ 5004:∀ 4843:∇ 4811:α 4618:∑ 4614:− 4545:α 4541:− 4483:α 4445:α 4317:α 4227:− 4089:− 4071:∑ 4067:− 4005:− 3933:− 3892:∇ 3750:− 3707:− 3689:∑ 3685:− 3671:− 3650:− 3609:− 3468:∑ 3464:− 3297:− 3098:≠ 3016:⋱ 2987:⋮ 2964:⋯ 2880:⋯ 2746:⋯ 2562:⋯ 2509:… 2438:≠ 2370:that is, 2355:≠ 2349:∀ 2033:− 1852:≠ 1735:− 1717:− 1703:… 1581:… 1508:… 1431:α 1387:α 1383:− 1344:α 1317:− 1285:− 1239:… 1146:α 1142:− 1075:α 936:α 893:− 812:α 744:α 601:− 559:α 529:α 405:− 307:− 214:− 114:− 94:symmetric 13577:Software 13541:Hardware 13500:Problems 9136:Rewrite 9095:if 9037:if 8572:without 7824:if 7790:if 7734:if 7002:against 6869:if 6735:if 5699:Lemma 3. 5442:Lemma 2. 4956:Lemma 1. 4473:if 3167:for any 3087:for any 2427:for any 2311:′ 2157:′ 2132:′ 1870:, where 1655:parallel 8568:can be 6467:of the 1647:ellipse 830:, etc. 145:Lanczos 141:Arnoldi 13599:LAPACK 13589:MATLAB 13430: 11050:, for 8488:Since 8169:, the 7160:where 6686:where 6396:basis 5951:, thus 5871:Proof. 5525:Proof. 5097:Proof. 4892:Proof. 3113:, and 1186:where 70:where 24:is an 20:, the 13584:ATLAS 13386:(PDF) 9516:with 8576:into 7662:with 367:. As 13563:SIMD 13428:ISBN 12206:and 11061:> 9902:and 9102:> 8900:and 7831:> 6917:> 6876:> 6349:and 6188:and 5769:< 5281:< 5078:< 5025:and 5010:< 4304:< 135:for 13553:TLB 13398:doi 9207:as 3588:... 1653:is 92:is 16:In 13626:: 13394:49 13392:. 13388:. 13377:; 12320:. 11076:, 10981:, 10761:, 10134:: 8927:: 8117:. 7438:33 7426:32 7388:23 7376:22 7364:21 7327:13 7315:12 7303:11 6932:, 6214::= 5867:. 5547::= 5521:. 5438:. 5093:. 4888:. 4741::= 4593::= 4526::= 4426::= 4326::= 4285::= 4262::= 4219::= 3520:20 3459:20 3415:20 3332:10 3292:10 3248:10 2896:2 2762:1 2578:0 2552:3 2549:2 2546:1 2543:0 2525:. 2453:. 13523:) 13519:( 13464:e 13457:t 13450:v 13436:. 13404:. 13400:: 13326:. 13317:i 13312:r 13304:T 13298:i 13293:r 13284:1 13281:+ 13278:i 13273:r 13265:T 13259:1 13256:+ 13253:i 13248:r 13240:= 13225:i 13220:p 13217:A 13209:T 13203:i 13198:p 13191:i 13181:) 13176:1 13173:+ 13170:i 13165:r 13155:i 13150:r 13145:( 13139:T 13133:1 13130:+ 13127:i 13122:r 13111:= 13096:i 13091:p 13088:A 13080:T 13074:i 13069:p 13060:i 13055:p 13052:A 13044:T 13038:1 13035:+ 13032:i 13027:r 13016:= 13007:i 12975:0 12972:= 12967:i 12962:p 12959:A 12951:T 12946:) 12940:i 12935:p 12928:i 12920:+ 12915:1 12912:+ 12909:i 12904:r 12899:( 12896:= 12891:i 12886:p 12883:A 12875:T 12869:1 12866:+ 12863:i 12858:p 12834:i 12829:p 12799:. 12790:i 12785:p 12782:A 12774:T 12768:i 12763:p 12754:i 12749:r 12741:T 12735:i 12730:r 12722:= 12707:i 12702:p 12699:A 12691:T 12686:) 12680:1 12674:i 12669:p 12662:1 12656:i 12643:i 12638:p 12633:( 12626:i 12621:r 12613:T 12607:i 12602:r 12594:= 12579:i 12574:p 12571:A 12563:T 12557:i 12552:r 12543:i 12538:r 12530:T 12524:i 12519:r 12511:= 12502:i 12470:0 12467:= 12462:i 12457:r 12449:T 12444:) 12438:i 12433:p 12430:A 12423:i 12410:i 12405:r 12400:( 12397:= 12392:i 12387:r 12379:T 12373:1 12370:+ 12367:i 12362:r 12338:i 12333:r 12306:i 12301:p 12277:i 12272:r 12248:i 12243:p 12219:i 12192:i 12155:i 12150:L 12142:T 12133:i 12128:U 12123:= 12111:1 12103:i 12098:U 12091:i 12086:U 12079:i 12074:L 12066:T 12057:i 12052:U 12047:= 12035:1 12027:i 12022:U 12015:i 12010:H 12002:T 11993:i 11988:U 11983:= 11971:1 11963:i 11958:U 11951:i 11946:V 11943:A 11935:T 11929:i 11924:V 11916:T 11907:i 11902:U 11897:= 11888:i 11883:P 11880:A 11872:T 11866:i 11861:P 11830:i 11825:P 11822:A 11814:T 11808:i 11803:P 11779:i 11774:p 11744:. 11738:1 11735:+ 11732:i 11727:v 11722:) 11717:i 11712:y 11704:T 11698:i 11693:e 11688:( 11683:i 11680:, 11677:1 11674:+ 11671:i 11667:h 11660:= 11648:1 11645:+ 11642:i 11637:v 11632:) 11627:i 11622:y 11614:T 11608:i 11603:e 11598:( 11593:i 11590:, 11587:1 11584:+ 11581:i 11577:h 11570:) 11565:1 11560:e 11553:2 11543:0 11538:r 11530:( 11525:i 11520:V 11510:1 11505:v 11498:2 11488:0 11483:r 11475:= 11463:1 11460:+ 11457:i 11452:v 11447:) 11442:i 11437:y 11429:T 11423:i 11418:e 11413:( 11408:i 11405:, 11402:1 11399:+ 11396:i 11392:h 11383:i 11378:y 11371:i 11366:H 11359:i 11354:V 11344:0 11339:r 11334:= 11322:i 11317:y 11310:i 11300:H 11291:1 11288:+ 11285:i 11280:V 11270:0 11265:r 11260:= 11248:i 11243:y 11236:i 11231:V 11228:A 11218:0 11213:r 11208:= 11198:) 11193:i 11188:y 11181:i 11176:V 11171:+ 11166:0 11161:x 11156:( 11152:A 11144:b 11140:= 11128:i 11123:x 11120:A 11111:b 11107:= 11098:i 11093:r 11064:0 11058:i 11036:1 11031:v 11024:2 11014:0 11009:r 11001:= 10996:0 10991:r 10969:0 10966:= 10963:i 10941:1 10938:+ 10935:i 10930:v 10906:i 10901:r 10871:. 10867:0 10864:= 10855:j 10850:p 10847:A 10839:T 10833:i 10828:p 10818:, 10814:0 10811:= 10802:j 10797:r 10789:T 10783:i 10778:r 10749:j 10743:i 10721:i 10716:p 10692:i 10687:r 10657:. 10651:1 10645:i 10640:p 10633:1 10627:i 10619:+ 10614:i 10609:r 10604:= 10595:i 10590:p 10580:, 10574:1 10568:i 10563:p 10560:A 10553:1 10547:i 10534:1 10528:i 10523:r 10518:= 10509:i 10504:r 10494:, 10488:1 10482:i 10477:p 10470:1 10464:i 10456:+ 10451:1 10445:i 10440:x 10435:= 10426:i 10421:x 10390:i 10385:p 10347:. 10341:i 10336:p 10329:i 10321:+ 10316:1 10310:i 10305:x 10300:= 10288:i 10283:p 10276:i 10268:+ 10263:1 10257:i 10252:z 10245:1 10239:i 10234:P 10229:+ 10224:0 10219:x 10214:= 10202:i 10197:z 10190:i 10185:P 10180:+ 10175:0 10170:x 10165:= 10156:i 10151:x 10120:i 10115:x 10085:. 10079:1 10073:i 10063:i 10059:c 10052:= 10043:i 10030:, 10026:) 10021:1 10015:i 10010:p 10003:i 9999:b 9990:i 9985:v 9980:( 9973:i 9969:d 9965:1 9960:= 9951:i 9946:p 9915:i 9888:i 9883:p 9853:. 9847:] 9839:i 9825:1 9819:i 9814:z 9806:[ 9801:= 9792:i 9787:z 9777:, 9771:] 9763:i 9758:p 9749:1 9743:i 9738:P 9730:[ 9725:= 9716:i 9711:P 9674:. 9670:) 9665:1 9660:e 9653:2 9643:0 9638:r 9630:( 9625:1 9617:i 9612:L 9607:= 9598:i 9593:z 9583:, 9577:1 9569:i 9564:U 9557:i 9552:V 9547:= 9538:i 9533:P 9495:i 9490:z 9483:i 9478:P 9473:+ 9468:0 9463:x 9458:= 9448:) 9443:1 9438:e 9431:2 9421:0 9416:r 9408:( 9403:1 9395:i 9390:L 9383:1 9375:i 9370:U 9363:i 9358:V 9353:+ 9348:0 9343:x 9338:= 9328:) 9323:1 9318:e 9311:2 9301:0 9296:r 9288:( 9283:1 9275:i 9270:H 9263:i 9258:V 9253:+ 9248:0 9243:x 9238:= 9229:i 9224:x 9193:i 9188:y 9181:i 9176:V 9171:+ 9166:0 9161:x 9156:= 9151:i 9146:x 9109:. 9105:1 9099:i 9087:i 9083:b 9077:i 9073:c 9064:i 9060:a 9051:, 9047:1 9044:= 9041:i 9029:1 9025:a 9018:{ 9013:= 9004:i 9000:d 8991:, 8985:1 8979:i 8975:d 8970:/ 8964:i 8960:b 8956:= 8947:i 8943:c 8913:i 8909:d 8886:i 8882:c 8856:] 8848:i 8844:d 8830:i 8826:b 8818:1 8812:i 8808:d 8781:3 8777:b 8769:2 8765:d 8754:2 8750:b 8742:1 8738:d 8731:[ 8724:] 8718:1 8711:i 8707:c 8696:1 8689:1 8683:i 8679:c 8656:1 8649:2 8645:c 8637:1 8631:[ 8626:= 8621:i 8616:U 8609:i 8604:L 8599:= 8594:i 8589:H 8554:i 8549:H 8525:i 8520:H 8497:A 8471:i 8466:v 8440:. 8434:] 8426:i 8422:a 8414:i 8410:b 8397:i 8393:b 8385:1 8379:i 8375:a 8367:1 8361:i 8357:b 8327:3 8323:b 8315:2 8311:a 8303:2 8299:b 8289:2 8285:b 8277:1 8273:a 8266:[ 8261:= 8256:i 8251:H 8224:i 8219:V 8216:A 8208:T 8202:i 8197:V 8192:= 8187:i 8182:H 8156:A 8134:A 8103:i 8098:y 8091:i 8086:V 8081:+ 8076:0 8071:x 8066:= 8061:i 8056:x 8034:) 8029:1 8024:e 8017:2 8007:0 8002:r 7994:( 7989:1 7981:i 7976:H 7971:= 7966:i 7961:y 7937:0 7932:x 7908:0 7903:x 7900:A 7891:b 7887:= 7882:0 7877:r 7844:. 7840:1 7837:+ 7834:i 7828:j 7818:0 7810:, 7806:1 7803:+ 7800:i 7797:= 7794:j 7782:2 7772:1 7769:+ 7766:i 7761:w 7748:, 7744:i 7738:j 7726:i 7721:v 7718:A 7710:T 7704:j 7699:v 7691:{ 7686:= 7681:i 7678:j 7674:h 7641:] 7632:T 7626:i 7621:e 7614:i 7611:, 7608:1 7605:+ 7602:i 7598:h 7588:i 7583:H 7575:[ 7570:= 7565:] 7557:i 7554:, 7551:1 7548:+ 7545:i 7541:h 7527:i 7524:, 7521:i 7517:h 7509:1 7503:i 7500:, 7497:i 7493:h 7461:i 7458:, 7455:3 7451:h 7434:h 7422:h 7411:i 7408:, 7405:2 7401:h 7384:h 7372:h 7360:h 7350:i 7347:, 7344:1 7340:h 7323:h 7311:h 7299:h 7292:[ 7287:= 7278:i 7268:H 7256:, 7250:] 7242:i 7237:v 7223:2 7218:v 7209:1 7204:v 7196:[ 7191:= 7182:i 7177:V 7143:i 7133:H 7124:1 7121:+ 7118:i 7113:V 7108:= 7103:i 7098:V 7095:A 7067:} 7062:1 7056:i 7051:v 7046:, 7040:, 7035:2 7030:v 7025:, 7020:1 7015:v 7010:{ 6988:1 6982:i 6977:v 6974:A 6947:i 6942:v 6920:1 6914:i 6883:. 6879:1 6873:i 6861:j 6856:v 6851:) 6846:1 6840:i 6835:v 6832:A 6824:T 6818:j 6813:v 6808:( 6803:1 6797:i 6792:1 6789:= 6786:j 6773:1 6767:i 6762:v 6759:A 6749:, 6745:1 6742:= 6739:i 6727:0 6722:r 6714:{ 6709:= 6704:i 6699:v 6672:2 6662:i 6657:w 6648:/ 6642:i 6637:w 6632:= 6627:i 6622:v 6597:} 6591:, 6586:0 6581:r 6574:2 6569:A 6564:, 6559:0 6554:r 6551:A 6546:, 6541:0 6536:r 6531:{ 6527:n 6524:a 6521:p 6518:s 6514:= 6511:) 6506:0 6501:r 6496:, 6492:A 6488:( 6483:K 6455:} 6449:, 6444:3 6439:v 6434:, 6429:2 6424:v 6419:, 6414:1 6409:v 6404:{ 6378:0 6373:r 6323:k 6318:p 6308:k 6303:r 6291:k 6286:r 6277:1 6274:+ 6271:k 6266:r 6254:1 6251:+ 6248:k 6243:r 6235:+ 6230:1 6227:+ 6224:k 6219:r 6209:1 6206:+ 6203:k 6198:p 6171:k 6166:p 6160:A 6149:k 6144:p 6135:k 6130:r 6118:k 6113:r 6105:= 6100:k 6067:i 6056:1 6053:+ 6050:i 6045:r 6035:i 6030:r 6020:T 6015:1 6012:+ 6009:k 6004:r 5999:= 5994:i 5989:p 5983:A 5977:T 5972:1 5969:+ 5966:k 5961:r 5937:i 5932:p 5929:A 5922:k 5909:i 5904:r 5899:= 5894:1 5891:+ 5888:i 5883:r 5848:k 5845:= 5842:i 5838:, 5833:k 5824:/ 5818:1 5815:+ 5812:k 5807:r 5800:T 5795:1 5792:+ 5789:k 5784:r 5772:k 5766:i 5762:, 5759:0 5753:{ 5748:= 5743:1 5740:+ 5737:k 5732:r 5729:A 5721:T 5715:i 5710:p 5681:i 5676:p 5666:i 5661:p 5658:A 5650:T 5644:i 5639:p 5630:1 5624:k 5619:r 5616:A 5608:T 5602:i 5597:p 5587:1 5581:k 5576:0 5573:= 5570:i 5557:k 5552:r 5542:k 5537:p 5507:k 5502:r 5495:T 5490:k 5485:r 5480:= 5475:k 5470:r 5463:T 5458:k 5453:p 5424:1 5418:j 5413:p 5408:, 5402:, 5397:1 5392:p 5387:, 5382:0 5377:p 5353:1 5347:j 5342:r 5337:, 5331:, 5326:1 5321:r 5316:, 5311:0 5306:r 5284:j 5278:i 5271:, 5268:0 5265:= 5260:j 5255:r 5248:T 5243:i 5238:p 5214:j 5209:r 5185:1 5179:j 5174:p 5169:, 5163:, 5158:1 5153:p 5148:, 5143:0 5138:p 5114:j 5109:x 5081:j 5075:i 5068:, 5065:0 5062:= 5057:j 5052:r 5045:T 5040:i 5035:r 5013:j 5007:i 5000:, 4997:0 4994:= 4989:j 4984:r 4977:T 4972:i 4967:p 4930:k 4925:x 4920:= 4915:1 4912:+ 4909:k 4904:x 4876:0 4873:= 4870:) 4865:1 4862:+ 4859:k 4854:x 4849:( 4846:f 4823:0 4820:= 4815:k 4776:1 4773:+ 4770:k 4765:x 4750:1 4747:+ 4744:k 4738:k 4727:i 4722:p 4712:i 4707:p 4704:A 4696:T 4690:i 4685:p 4676:1 4673:+ 4670:k 4665:r 4662:A 4654:T 4648:i 4643:p 4633:k 4628:0 4625:= 4622:i 4609:1 4606:+ 4603:k 4598:r 4588:1 4585:+ 4582:k 4577:p 4564:k 4559:p 4556:A 4549:k 4536:k 4531:r 4521:1 4518:+ 4515:k 4510:r 4493:| 4487:k 4478:| 4461:k 4456:p 4449:k 4441:+ 4436:k 4431:x 4421:1 4418:+ 4415:k 4410:x 4394:k 4389:p 4386:A 4378:T 4372:k 4367:p 4358:k 4353:r 4345:T 4339:k 4334:p 4321:k 4307:n 4301:k 4288:0 4282:k 4272:0 4267:r 4257:0 4252:p 4240:0 4235:x 4232:A 4223:b 4214:0 4209:r 4180:i 4175:p 4165:i 4160:p 4157:A 4149:T 4143:i 4138:p 4129:k 4124:r 4121:A 4113:T 4107:i 4102:p 4092:1 4086:k 4081:0 4078:= 4075:i 4062:k 4057:r 4052:= 4047:k 4042:p 4018:k 4013:x 4010:A 4001:b 3997:= 3992:k 3987:r 3982:= 3977:0 3974:, 3971:k 3966:p 3944:2 3940:/ 3936:1 3913:) 3908:k 3903:x 3898:( 3895:f 3889:= 3884:0 3881:, 3878:k 3873:p 3849:0 3846:, 3843:k 3838:p 3824:. 3810:i 3805:p 3795:i 3790:p 3787:A 3779:T 3773:i 3768:p 3759:0 3756:, 3753:1 3747:n 3742:p 3739:A 3731:T 3725:i 3720:p 3710:2 3704:n 3699:0 3696:= 3693:i 3680:0 3677:, 3674:1 3668:n 3663:p 3658:= 3653:1 3647:n 3642:p 3618:0 3615:, 3612:1 3606:n 3601:p 3585:. 3571:i 3566:p 3556:i 3551:p 3548:A 3540:T 3534:i 3529:p 3515:p 3512:A 3504:T 3498:i 3493:p 3483:1 3478:0 3475:= 3472:i 3454:p 3449:= 3444:2 3439:p 3410:p 3397:. 3383:0 3378:p 3368:0 3363:p 3360:A 3352:T 3346:0 3341:p 3327:p 3324:A 3316:T 3310:0 3305:p 3287:p 3282:= 3277:1 3272:p 3243:p 3230:. 3216:0 3211:p 3181:j 3178:= 3175:i 3155:1 3152:= 3147:j 3142:p 3134:T 3128:i 3123:p 3101:j 3095:i 3075:0 3072:= 3067:j 3062:p 3054:T 3048:i 3043:p 2941:3 2936:p 2933:A 2925:T 2919:2 2914:p 2857:3 2852:p 2849:A 2841:T 2835:1 2830:p 2805:2 2800:p 2797:A 2789:T 2783:1 2778:p 2723:3 2718:p 2715:A 2707:T 2701:0 2696:p 2671:2 2666:p 2663:A 2655:T 2649:0 2644:p 2619:1 2614:p 2611:A 2603:T 2597:0 2592:p 2506:, 2501:2 2496:p 2491:, 2486:1 2481:p 2476:, 2471:0 2466:p 2441:j 2435:i 2415:0 2412:= 2407:j 2402:p 2399:A 2391:T 2385:i 2380:p 2358:j 2352:i 2345:, 2342:) 2337:2 2332:j 2328:t 2324:d 2321:( 2318:O 2315:+ 2308:C 2304:= 2301:) 2296:j 2292:t 2288:d 2283:j 2278:p 2273:+ 2268:i 2263:p 2256:i 2252:t 2248:( 2244:A 2237:T 2232:) 2226:j 2222:t 2218:d 2213:j 2208:p 2203:+ 2198:i 2193:p 2186:i 2182:t 2178:( 2154:C 2129:C 2125:= 2121:x 2116:A 2109:T 2103:x 2081:C 2061:C 2058:= 2054:x 2047:T 2041:b 2036:2 2029:x 2024:A 2017:T 2011:x 1984:i 1979:p 1972:i 1968:t 1964:+ 1960:c 1937:i 1933:t 1910:i 1905:p 1879:c 1858:} 1855:i 1849:j 1846:: 1841:j 1836:p 1831:{ 1809:i 1804:p 1797:i 1793:t 1789:+ 1785:c 1764:i 1738:1 1732:n 1727:p 1720:1 1714:n 1710:t 1706:, 1700:, 1695:0 1690:p 1683:0 1679:t 1668:n 1664:n 1626:n 1606:n 1578:, 1573:2 1568:p 1563:, 1558:1 1553:p 1548:, 1543:0 1538:p 1505:, 1500:2 1495:p 1490:, 1485:1 1480:p 1475:, 1470:0 1465:p 1443:0 1440:= 1435:i 1408:i 1403:p 1397:A 1391:i 1378:i 1373:r 1368:= 1365:) 1360:i 1355:p 1348:i 1340:+ 1335:i 1330:x 1325:( 1321:A 1313:b 1309:= 1304:1 1301:+ 1298:i 1293:x 1290:A 1281:b 1277:= 1272:1 1269:+ 1266:i 1261:r 1236:, 1231:2 1226:p 1221:, 1216:1 1211:p 1206:, 1201:0 1196:p 1165:i 1160:p 1157:A 1150:i 1137:i 1132:r 1127:= 1118:1 1115:+ 1112:i 1107:r 1097:, 1091:i 1086:p 1079:i 1071:+ 1066:i 1061:x 1056:= 1047:1 1044:+ 1041:i 1036:x 1026:, 1017:i 1012:p 1009:A 1001:T 995:i 990:p 981:i 976:r 968:T 962:i 957:p 949:= 940:i 906:0 901:x 898:A 889:b 885:= 880:0 875:r 851:0 846:x 816:1 789:1 784:p 760:0 755:p 748:0 740:+ 735:0 730:x 725:= 720:1 715:x 687:0 682:x 655:0 650:p 644:A 637:T 631:0 626:p 619:) 614:0 609:x 606:A 597:b 593:( 587:T 581:0 576:p 568:= 563:0 538:) 533:0 523:0 518:p 513:+ 508:0 503:x 498:( 495:f 473:0 468:p 444:0 439:x 408:1 400:A 375:C 355:C 335:C 332:= 328:x 321:T 315:b 310:2 303:x 298:A 291:T 285:x 240:. 235:x 228:T 222:b 217:2 210:x 205:A 198:T 192:x 187:= 184:) 180:x 176:( 173:f 143:/ 117:1 109:A 79:A 54:b 50:= 46:x 43:A

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.

Knowledge

Derivation of the conjugate gradient method

Index