Subroutine XYaitr is responsible for all the work associated with building the needed factorization. It implements Algorithm 2 of Chapter 4 using the classical Gram-Schmidt procedure with possible re-orthogonalization by the DGKS scheme. At each step j, a residual vector is computed that is numerically orthogonal to the columns of If a step of re-orthogonalization is performed in order to produce an updated residual If the angle between the successive residual vectors and is greater than then the orthogonalization has been successful and is replaced by and the last column of is updated. Otherwise, another re-orthogonalization step is required. This is repeated at most one more time. If a third re-orthogonalization is necessary, then the original lies in the numerical span of the columns of .
In the event that a third re-orthogonalization is necessary, special action must be taken. If this occurs, then it means that the component of the original that is orthogonal to the is indistiguishable from roundoff error. Numerically, the columns of form a basis for an invariant subspace of and consequently the corresponding subdiagonal element is set to zero. In order to continue building the Arnoldi factorization to the desired length, an arbitrary nonzero vector must be generated that is orthogonal to the existing columns of This is accomplished by generating a random vector and orthogonalizing it against the columns of to get the new basis vector .