3.3.4 THE (My web site) SPECTRAL TEST 99 S3. [Compute vs.]
3.3.4 THE SPECTRAL TEST 99 S3. [Compute vs.] Set u c u -h, v t v -p; and if u2 + v2 < s, set s +- u2 + v2, h +- u, p + v. Then output fi = v2. (The validity of this calculation for the two-dimensional case is proved in exercise 5. Now we will set up the U and V matrices satisfying (28) and (29), in preparation for calculations in higher dimensions.) Set where the -sign is chosen for V if and only if p > 0. S4. [Advance t.] If t = T, the algorithm terminates. (Otherwise we want to increase t by 1. At this point U and V are t X t matrices satisfying (28) and (29) and we must enlarge them by adding an appropriate new row and column.) Set t t t + 1 and r e (or) modm. Set Ut to the new row (–r, 0, 0, . . . ,O, 1) of t elements, and set uit t-0 for 1 5 i < t. Set V, to the new row (O,O, 0,. . . ,O, m). Finally, for 1 5 i < t, set g c round(v,l r/m), vzt + vile -gm, and Ut t Ut + qUi. (Here round(z) denotes the nearest integer to z, e.g., 1~ + l/2]. We are essentially setting vit + viir and immediately applying transformation (23) with j = t, since the numbers ]vilr] are so large they ought to be reduced at once.) Finally set s c min(s, U,. Ut), k t t, and j + 1. (In the following steps, j denotes the current row index for transformation (23), and Ic denotes the last such index where the transformation shortened at least one of the Vi.) S5. [Transform.] For 1 5 i 5 t, do the following operations: If i # j and 2lVi . Vjl > Vy . Vy, set q + round(Vi . Vj / I+ . Vj), Vi +-Vi -qV7, Uy + Vi + qUi, and k + j. (The fact that we omit this transformation, when 21Vi . Vjl exactly equals V, . V,, prevents the algorithm from looping endlessly; see exercise 19.) S6. [Examine new bound.] If k = j (i.e., if the transformation in S5 has just done something useful), set s +- min(s, Uj . Uj). S7. [Advance j.] If j = t, set j c 1; otherwise set j c j + 1. Now if j # k, return to step S5. (If j = k, we have gone through t -1 consecutive cycles of no transformation, so the transformation process is stuck.) S8. [Prepare for search.] (Now the absolute minimum will be determined, using an exhaustive search over all (Q, . . . , Q) satisfying condition (21) of Lemma A.) Set X t Y t (0, . . . ,O), set k t t, and set (We will examine all X = (51, . . . ,zt) with ]zrj] 2 zj for 1 5 j 5 t. In hundreds of applications of this algorithm, no zJ has yet turned out to be greater than 1, nor has the exhaustive search in the following steps ever reduced s; however, such phenomena are probably possible in weird cases,