равенство V- - V- =0). Это изображено на следующем графике.

Обратимся к вопросу (Ь). Необходимо выбрать такое qi, чтобы Uj + zijj qiUi имели минимальную длину. С геометрической точки зрения следует начать с Uj и прибавить некоторый вектор в (i - 1)-мерной гиперплоскости, равный сумме кратных {Ui \ i ф i). Снова лучшим решением является такой выбор, при котором Uj является перпендикулярным к гиперплоскости, т. e.Uj-Uf.=Q для всех к ф j:

Uj-Uk + 2qi{Ui-Uk)=0, l<k<t, кф]. (26)

(В упр. 12 приводится строгое доказательство того, что решение (Ь) должно удовлетворять этим f - 1 уравнениям.)

Ответив на вопросы (а) и (Ь), мы оказались в двойном затруднении: можно ли выбрать qi соответственно (24) так, чтобы V/ • V/ было минимальным, или согласно (26) так, чтобы Uj • f/j было минимальным? Каждая из этих альтернатив приводит к уменьшению части (22), поэтому сразу не ясно, какому выбору отдать предпочтение. К счастью, существует очень простое решение этой дилеммы: условия (24) и (26) те же самые! (См. упр. 7.) Следовательно, ответы на вопросы (а) и (Ь) совпадают. Получается, что длину обоих векторов Ui и Vj можно уменьшить одновременно. На самом деле мы только что снова открыли процесс ортоганализации Грама-Шмидта (Gram-Schmidt) [см. Crelle 94 (1883), 41-73].

Нашу радость омрачает понимание того, что вопросы (а) и (Ь) рассматривались только для действительных значений qi. Для решения поставленной задачи следует ограничиться целыми значениями, в связи с чем провести V/ точно перпендикулярно Vj нельзя. Лучшее, что можно сделать в (а), - это положить q наиболее близким целым к Vi-Vj / Vj - Vj (см. (25)). Оказывается, что это не всегда лучшее решение вопроса (Ь); на самом деле f/j иногда может быть длиннее Uj. Однако граница (21) никогда не растет, поэтому мы можем запомнить наименьшее значение /(2/I1 !У*); найденное до сих пОр. Этот выбор qi, основанный исключительно на вопросе (а), является совершенно удовлетворительным.

Если преобразование (23) повторно применить таким образом, чтобы ни один из векторов Vi не стал длиннее и по крайней мере один стал короче, мы никогда не попадем в петлю, т. е. мы никогда не будем рассматривать ту же квадратичную форму после ряда нетривиальных преобразований подобного вида. В конце концов, мы застрянем: ни одно из преобразований (23) для 1 < j < f не будет в состоянии укоротить любой из векторов Vi, ..., Vt- В этой точке можно возвращаться к исчерпывающему исследованию, используя границы леммы А, которые будут вполне малы в большинстве случаев. Изредка этих границ (21) недостаточно, и другой вид преобразования обычно дает алгоритм выхода из положения, в котором мы застряли, и уменьшения границы (см. упр. 18). Тем не менее доказано, что преобра-

зование (23) в самого себя вполне отвечает требованиям спектрального критерия; к тому же доказано, что оно поразительно мощное, когда вычисления осуществляются так, как в алгоритме, обсуждаемом ниже.

*D. Как выполнить спектральный критерий. В этом разделе будет приведена эффективная вычислительная процедура. Госпер (Gosper) и Дитер (Dieter) заметили, что можно использовать результаты для более низкой размерности, чтобы значительно быстрее получить спектральный критерий в высокой размерности. Это усовершенствование включено в следующий алгоритм вместе с упрощением Гаусса (Gauss) для двумерного случая (упр. 5).

Алгоритм S {Спектральный критерий). Этот алгоритм определяет значение щ = min-\/a;j -I-----xf xi + ах2 -I-----t- a*~xt = 0 (no модулю m) (27)

для 2 <t <T, заданных а,тиТ, где 0<а<тиаит - взаимно простые числа. (Минимум взят по всем ненулевым целочисленным векторам {xi,... ,xt), а число щ является f-мерной точностью генератора случайных чисел, как обсуждалось выше.) Вся арифметика в пределах алгоритма дана в целых числах, размеры которых редко либо никогда не превышают т, исключая шаг S7. К тому же почти все целые переменные будут меньше т по абсолютной величине на протяжении вычислений.

Когда щ вычисляется для t >3, алгоритм работает с двумя t х f-матрицами U и V, векторы-строки которых обозначены через Ui - (мл,..., иц) и Vj = (га, •, Vn) для 1 < г < f. Эти векторы удовлетворяют условиям

Mil + ам<2 Н----+ o!~Uit = О (по модулю т), 1 < i < (28)

Ui-Vi = mbii, l<i,j<t. (29)

(Таким образом, Vj из предыдущих обсуждений умножаются на т, чтобы их компоненты были целыми числами.) Существует три дополнительных вектора: X = (ц,.У = (yifMt) и Л = («i,...,«t). В алгоритме г будет обозначать о~ mod m, а 5 - наименьшую верхнюю грань v, которая была найдена ранее.

51. [Инициализация.] Присвоить t 2, h а, h <- т, р <- I, р <- О, г а, S 1 + а. (Первые шаги алгоритма - это специальный метод, примененный к случаю t = 2, который очень похож на алгоритм Евклида. Получим

h - ар = h - ар - О (по модулю т) и hp - hp - ±т (30)

на протяжении этого этапа вычислений.)

52. [Шаг Евклида.] Присвоить q [h/h\,u h-qh, v <- p-qp. Если u+v < s, присвоить s u + , h <- h, h <- и, p <- p, p <- V и повторить шаг S2.

53. [Вычисление Vi-] Присвоить ui-u-h,v<-v-p, a, если u + v < s, присвоить s <- + v, h и, p i- V. Затем выход -/s = v. (Справедливость этих вычислений для двумерного случая доказана в упр. 5. Подготовим матрицы U и V, удовлетворяющие соответственно (28) и (29), для вычислений в больших размерностях.) Присвоить

f р h\

i Р] г р)

С/ ( М , V

\-р -Н

где знак "минус" выбирается для V, только если р > 0.

54. [Опережение t.] Если t = Т, алгоритм завершается. (Иначе нужно увеличить i на 1. В этой точке U и V являются матрицами размера t х t, удовлетворяющими (28) и (29), и их необходимо увеличить, присоединяя подходящие новые столбцы и строки.) Присвоить t<-t+lHr<- (аг) mod т. Присвоить Ut новую строку (-г,О,О,... ,0,1) из t элементов и присвоить uu О для 1 < г < f. Присвоить Vt новую строку (0,0,0,... ,0,т). Окончательно для 1 < г < f присвоить q f- округленное(г;{1 г/т), Vu <- Ьцг - qm и Ut <- Ut + qUi. (Здесь "округленное (ж)" определено как ближайшее целое к х, например [х + 1/2J. Мы, по существу, присваиваем Vu <- Ьцг и непосредственно применяем преобразование (23) с j - t, потому что числа \уцг\ настолько велики, что их нужно сразу уменьшить.) Окончательно присвоить s <- min{s,UfUt), к <- t и j 1. (На следующем шаге j обозначает индекс текущей строки для преобразования (23), а А; - последний такой индекс, когда преобразование укоротит по крайней мере один из векторов Vj.)

55. [Преобразовать.] Для 1 < i < i выполнить следующие операции: если i ф j vl 2\Vi-Vj\ > Vj Vj, TO присвоить q <r- округление(Т4 - Vj / Vj - Vj), Vi Vi - qVj, Uj f- Uj +qUi, s min(5, Uj Uj) и к <- j. (Пропускаем преобразование, когда 2Vi-V точно равно Vj-Vj; в упр. 19 показано, что эта предосторожность удерживает алгоритм от зацикливания.

56. [Опережение j.] Если j = t, присвоить j <- 1; иначе присвоить j j + 1. Если j Ф к, вернуться к шагу S5. (Если j = к, проходим t - 1 последовательных циклов без преобразований, так как процесс преобразования "застрял".)

57. [Подготовка поиска.] (Сейчас абсолютный минимум будет установлен путем исчерпывающего поиска по всем {xi,... ,xt), удовлетворяющим условию (21) леммы А.) Присвоить X f- У f- (О,..., 0), присвоить к <- t и присвоить

\/[{Vj-Vj)s/m} для 1 < i < t (31)

(Проверим все X = {xi,...,xt) с < Zj для 1 < j < i. Обычно \zj\ < 1, но Л. Киллингбек (L. С. Killingbeck) заметил в 1999 году, что большие значения появляются около 0.00001 раз для всех множителей, когда т - 2 Во время перебора вектор Y всегда будет равен xiUi + + xtUt, поскольку f{xi,...,xt) = У-У. Так как f{-xi,...,-xt) = f{xi,...,Xt), будем проверять только векторы, первая ненулевая компонента которых положительна. Метод, по существу, состоит в том, что при подсчетах (zi,.. .,хг) рассматривается как цифры в изменяющейся системе счисления со смешанным основанием (2zi -f-1, ...,2zt + 1); см. раздел 4.1.)

58. [Опережение Xk] Если Xk - z, перейти к шагу S10. Иначе - увеличить Xk на 1 и присвоить У У + Uk-

59. [Опережение к.] Присвоить к <- к + 1. Затем, если к <t, присвоить Xk <--zk,

У <- У-2zkUk и повторить шаг S9. Но, если к > t, присвоить s min(s, У-У).

S10. [Уменьшение к.] Присвоить к к - 1. Если А; > 1, возвратиться к шагу S8. Иначе - выход щ = \/s; перебор заканчивается, и возврат к шагу S4.

Практически алгоритм S применяется, скажем, для Г = 5 или 6. Обычно он работает достаточно хорошо, когда Г = 7 или 8, но может быть ужасно медленным