Вычислительные алгоритмы в геометрии чисел тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

На правах рукописи

Гассан Сергей Владимирович

Вычислительные алгоритмы в геометрии чисел

01.01.07 — вычислительная математика

005007562

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

1 2ЯНВ2(м2

Владивосток 2011

005007562

Работа выполнена в Институте прикладной математики ДВО РАН

Научный руководитель: доктор физико-математических наук,

член-корреспондент РАН Быковский Виктор Алексеевич

Официальные оппоненты: доктор физико-математических наук,

профессор Добровольский Николай Михайлович

Защита состоится 25.01.2012 в 15.00 на заседании диссертационного совета К 212.294.02 в Тихоокеанском государственном университете по адресу: 680035, г. Хабаровск, ул. Тихоокеанская, 136, ауд. 315л.

С диссертацией можно ознакомиться в библиотеке Тихоокеанского государственного университета.

кандидат физико-математических наук Илларионов Андрей Анатольевич

Ведущая организация: Механико-математический факультет

МГУ имени М.В. Ломоносова, г. Москва

, Автореферат разослан

и

" декабря 2011 г.

.Ученый секретарь диссертационного совета, к.ф.-м.н.

Э.М. Вихтенко

Общая характеристика работы Актуальность темы

Обобщением теории непрерывных дробей на многомерный случай занимались многие математики, начиная с Л. Эйлера. Одно из самых удачных было предложено в конце девятнадцотого века Г. Минковским и Г.Ф. Вороным, независимо друг от друга. Оно основано на фундаментальном понятии "локальный минимум" решетки. Построение и анализ алгоритмов для вычисления локальных минимумов, а также изучение их взаимного расположения — одна из важнейших задач в геометрии чисел и целочисленном линейном программировании.

Впервые подобные вопросы были исследованы в работе Валена, опубликованной в 1893 году, для двумерных решеток. Кроме того, в работах В. Быковского эти исследования нашли приложения в теории квадратурных формул, построенных с помощью сеток Коробова. Выяснилось, что у решеток, с помощью которых строятся сетки Коробова, локальные минимумы определяют величину погрешности квадратурных формул на классах функций с доминирующей производной. Тем самым, алгоритмические аспекты вышеупомянутых задач геометрии чисел играют важную роль при построении конкретных оптимальных сеток Коробова, обеспечивающих наилучшую точность при вычислении многомерных интегралов.

Цель работы

Целью работы является разработка эффективного алгоритма для вычисления множества локальных минимумов решеток и исследование их взаимного расположения.

Методика исследования

При выполнении диссертации использовались теория выпуклого анализа, методы геометрии чисел, диофантовых приближений, аналитической и вычислительной теории чисел.

Научная новизна

• В рамках исследования взаимного расположения локальных минимумов трехмерных решеток получен явный вид трехмерных областей Валена первого и второго типов, что уточняет теорему Валена.

• На основе предложенной В.А. Быковским теоретической схемы разработан алгоритм для вычисления локальных минимумов целочисленных решеток.

• Разработан алгоритм для вычисления параметра Бахвалова и оптимальных коэффициентов параллелепипедальных сеток Коробова с помощью локальных минимумов.

• Построена модификация алгоритма вычисления локальных минимумов, позволяющая вычислять параметр Бахвалова приближенно и существенно ускорить вычисление оптимальных коэффициентов.

Личный вклад автора

Области Валена получены автором самостоятельно. На основе предложенной В.А. Быковским теоретической схемы автор самостоятельно разработал и оптимизировал алгоритмы для вычисления локальных минимумов целочисленных решеток, параметра Бахвалова и оптимальных коэффициентов параллелепипедальных сеток Коробова. Программная реализация построенных алгоритмов и вычислительные эксперименты также выполнены автором.

Достоверность

полученных результатов обеспечивается корректностью применения методов исследования, строгостью проведения" доказательств предлагаемых утверждений, а также сопоставлением полученных в результате вычислительных экспериментов значений погрешностей квадратурных формул со значениями, полученными ранее другими исследователями.

Теоретическая и практическая ценность

Результаты работы, полученные при исследовании взаимного расположения локальных минимумов трехмерных решеток, носят теоретический характер и могут.быть использованы в геометрии чисел, теории диофантовых приближений и целочисленном линейном программировании.

Разработанные алгоритмы для вычисления локальных минимумов и оптимальных коэффициентов могут быть непосредственно использованы на практике для нахождения Оптимальных параллелепипедальных сеток.

Апробация работы

Результаты диссертации докладывались и обсуждались на трех Дальневосточных математических школах-семинарах имени Е.В. Золотова (Владивосток, 2004; Хабаровск, 2005; Владивосток, 2010), на научной конференции "Суперкомпьютеры: вычислительные и информационные технологии" (Хабаровск, 2010), на международной научной конференции "F^irst Russia and Pacific Conference on Computer Technology and Applications" (Vladivostok, 2010), на научно-технической конференции "Математическое, вычислительное и информационное обеспечение технологических процессов и систем" (Комсомольск-на-Амуре, 2010), на семинаре ХО ИПМ ДВО РАН (Хабаровск, 2009).

Публикации

Основные результаты"диссертации опубликованы в работах, указанных в конце автореферата.

Структура и объем работы

Диссертация изложена на 71 странице и состоит из введения, трех глав (с разбиением на параграфы) и списка литературы из 32 наименований. Работа включает 10 рисунков и 2 таблицы.

Содержание работы

Во введении излагается история и мотивировки вопросов, изучаемых в диссертации, а также вводятся некоторые основные определения.

Пусть {7^,... ,7^} -■• s линейно независимых точек из R", рассматриваемые как столбцы невырожденной матрицы G = (7М ... 7W) = (7!'') с . Множество всех целочисленных линейных комбинаций

Г = Г (О) -- {7 --= (7l,..., 7.) = ггцуЫ + ... + | тъ ..., ms е zj

назовем s-мерной решеткой в Is с базисом (7^,..., 7^s)). В случае если U)

все числа 7i являются целыми, то решетка называется целочисленной. Величину D — D(Г) - |det(G)| назовем определителем решетки Г.

Обозначим через £(MS) множество всех решеток в R3, а.через £*(R£) его подмножество, состоящее из всех решеток "общего положения", у которых для любого ненулевого узла7 = (71,...,ъ) все координаты % отличны от нуля. Другими словами, на координатных гиперплоскостях нет ненулевых узлов Г.

Назовем две матрицы G и G' эквивалентными, если одна получается из другой путем композиции некоторых преобразований вида: 1) изменение знака у столбца или строки; 2) перестановка двух столбцов или строк.

Ненулевой узел 7 = (71, -. -, 7i) назовем локальным минимумом решетки Г, если не существует ненулевого узла 77 = (771,..., r]s) из Г, для которого

Ы < Ы для всех i = 1,..., s, и при этом хотя бы одно из этих s неравенств строгое.

Назовем матрицу G = .(7W ... и определяемый ею базис

■ • ■ 17^} минимальными, если не существует ненулевого узла г/ из Г, для которого

М<Шах{|7Я.-'.,Ы0|} (i = l,...,a).

Понятно, что для решеток "общего положения" Г е £*(RS) каждый узел минимального базиса для Г является локальным минимумом решетки. Из определения непосредственно следует, что эквивалентные матрицы (и соответствующие им базисы) минимальны только одновременно.

В первой главе "Трехмерные области Валена" изучается взаимное расположение векторов минимальных базисов трехмерных решеток.

Согласно работе Минковского [*], невырожденная матрица G, определяющая базис решетки Г "общего положения", минимальна тогда и только тогда когда она эквивалентна одной из матриц вида

/х! -У1 z\ \ (хх -г/1 -zA

Mr = х2 2/2 -¿2 , Ми = \х2 У2 -Z2 (1)

Ул ¿3 / \X;i Уз ¿3 J

1 Minkowski H. Generalization de la theorie des fraction continues / H. Minkowski // Ann. Sei. École Norm. Sup. - 1896. - Vol. 13, .V2. - P. 41-60.

ковского

mm

с неотрицательными Х{, уг, г, £ К. у которых: 0) тах{:гь гх} ^ уи тах{у2, г2} ^ х2, тах{х3, у3} ^ ад

(II) для матрицы М/ (первый тип) выполняется по крайней мере одно из неравенств: х\ ^ жх, уг ^ ^г;

(III) для матрицы Мц (второй тип) выполняются неравенства: ^ Хз, + 22.

Матрицы вида (1) будем называть матрицами Минковского, соответственно, первого и второго типа. Базис (7^, 7®, 7^) решетки Г будем называть базисом Минковского, если соответствующая ему матрица эквивалентна матрице Минковского.

Согласно теореме Минковского о выпуклом теле, для любого локального минимума 7'= (71,72,73) решетки Г е £(Ж3)

|71727зК Я(Г).

Из работы [2] следует, что для каждой пары узлов (7^,7^) базиса Мин-

Это неравенство называют теоремой Валена для трехмерных решеток.

Пусть узлы <у(1),'у(2),<у(3) составляют базис Минковского решетки Г. В работе [3] для таких узлов было доказано неравенство

шт { } < \в(Т).

Наконец, в [4] последняя оценка была усилена в следующем виде: для узлов 7^\7^>7> составляющих базис Минковского

+ + < од.

В настоящей работе мы уточняем перечисленные выше результаты следующим образом. Рассмотрим трехмерный вектор

„_. МЧЧ'\ [тРт^тГЛ

составленный из деленных на определитель решетки абсолютных величин произведений координат базиса Минковского. Образы отображения

• м (т V г) = ( Х1Х2Х3 ШУгШ

К,У'} V ¿еЬ(М): det(Л/), йеЬ(М))

2Быковский В.А. Теорема Валена для двумерных подходящих дробей / В.А. Быковский // Матема-

тические заметки. — 1999. — Т. 66, №1. — С. 30-37.

'Авдеева М.О. Аналог теоремы Валена для совместных приближений пары чисел / М.О. Авдеева, В.А. Быковский // Математический сборник. — 2003. — Т. 194, .W. — С. 4-14.

■•Авдеева М.О. Уточнение теоремы Валена для базисов Минковского трехмерных решеток / М.О. Авдеева, В А. Быковский // Математические заметки. — 2006. — Т. 79, Л*2. — С. 163-168.

(х 4- у)(х + г) - х = 0 27хугЛ- {у + г -х - I)3 = 0 \ у Рис. 1. Область \\г[

для случаев, когда М пробегает все невырожденные матрицы Минковского первого и второго типов, обозначим через У}(К3) и Р//(К3) и назовем трехмерными областями Валена соответственно первого и второго типа. Обозначим через И^ (рис. 1) область в М3, состоящую из всех точек

(х, у, г) с неотрицательными х, у, г и х + г ^ 1, для которых: х

1) --х при х > тах{г. у/г — г};

х \ г

2) у^%р(х,г) при 0 ^ х, г ^ -; х ^ у/г - г\ г < у/х(1 + 5х) - 2х;

г{1 + х — Зг) 1 __1 + а;

3) у <--- при 0 ^ х, г ^ у/х{\ + 5х) - 2х ^ г ^ ———;

х + г п 4 5

(1+х-г)2 1

4) У ^ --Л- при 0 ^ х, г ^ -; х < ппп{5г - 1,1 - Зг};

о ух X) 2

5) У ^ 2 ~ 2 ПрИ ^ ^ Х' 2 ^ 2' Х ^ Х ^ ~~ Зг - I};

(1 _ х _ г)2

6) ^Ч?-Г~ при

<5(2 - X)

где через у0 = ф(х, г) мы обозначили единственное действительное решение уравнения

/(у) = 27хуг + (у + ^ - х - I)3 = 0.

Обозначим через IV" область в К3, полученную из путем циклического сдвига переменных (х,у.г), так что переменным (х,у,г) (область И7/) соответствуют переменные (г,х,у) (область И7")- Тогда имеет место

Теорема 1. Область Валена 1/}(К3) есть объединение областей \¥[ и \¥".

Обозначим через (рис. 2) область в К3, состоящую из всех точек (г, у, г) с неотрицательными х, у., г, для которых:

х(1 - 2a:)2 + 4»z(l - ix + у -Г z) = 0 Рис. 2. Область Wn

1) :e + 2/+z<1 при y + z>l/2;

2) x ^ ¡p(y, z) при y + z< 1/2,

где через Xo = z) мы обозначили решение уравнения

f(x) = х{1 - 2х)2 + 4yz(l - Зх + у + z) = О, принадлежащее отрезку [4/9, 1/2]. Тогда справедлива Теорема 2. Область Валена Vj-/(K3) совпадает с Wjj.

Во второй главе "Алгоритм вычисления локальных минимумов целочисленных решеток" рассматривается построение алгоритма вычисления множества локальных минимумов целочисленных решеток на основе предложенной в работе В.А. Быковского р] теоретической схеме. Ключевую роль в вычислительной схеме играют приведенные базисы и кратчайшие вектора решеток, алгоритмы вычисления которых обсуждаются в отдельных параграфах. В конце главы предлагается алгоритмическая модель для программной реализации рассмотренных алгоритмов и оценивается асимптотическое время работы.

Пусть С\

т =

Zs произвольное невырожденное линейное преобразование

(Li{m)\ /Ьц b\2

£(ш) = Ь2(т) = b21 Ь'22

\Lt(m)/ \bsl bs 2

где

Li(m) = тпхЪц + ... + msbi:

Быковский В.А. Алгоритм вычисления локальных минимумов решеток / В.А. Быковский /'/ Доклады РАН. - 2004. — Т. 399, Л*5. - С. 587-589-

линейные формы с целочисленными коэффициентами. Оно определяет целочисленную решетку

Г = jt; = £(т) = яцЬ(1) + ... + тМа) I ти ■ ■ ■, т., € zj

в EÄ с базисом ..., Ь^), элементы которого являются столбцами матрицы В = (bij) с bij G Z. Определитель решетки TN- N(Г) = |det(£?)|.

Напомним, что ненулевой узел v — (vi,.....vs) решетки Г в R5 называется

локальным минимумом, если не существует другого ненулевого узла и — {щ,.. ■, us) решетки Г, для которого ^ |i>j| для всех г = 1,.... s и при этом хотя бы одно из этих s неравенств строгое. Введем обозначение

S

ИМИ = Дтаха Ы}. !=1

По теореме Минковского о выпуклом теле, для любого локального минимума v целочисленной решетки Г определителя N выполняется неравенство ИМИ < N. Отсюда непосредственно следует, что множество 9Л(Г) локальных минимумов целочисленной решетки Г конечно. В работе [6] показано, что для количества его элементов выполняется оценка

#971(Г) < C(s) (log5-1 N)

с некоторой положительной константой C(s) и JV > 1.

Пусть Г — целочисленная решетка в Rs определителя N. Обозначим через JCS(N) множество всех наборов неотрицательных целых чисел К = (ki,..., ks), для которых

h + ... + к, ^ s/2 + log2 N

и при этом хотя бы одно ki равно нулю. Каждому набору К из JCS(N) сопоставим положительно определенную квадратичную форму

= (2)

По определению, величина

М(А">( Г) = min Q{K\ т)

теЪ* т/(0,...,0)

есть минимум Определим множество

М(Г) = U {С{т) | т £ Zs; Q{K)(m) ^ 4s • М(*>(Г)} .

keic.(n)

6Быковский B.A. О погрешности теоретико-числовых квадратурных формул / U.A. Быковский // Доклады РАН. - 2003. - Т. 389, .V2. - С. 154-155.

В работе |г>] показано, что имеет место включение 9ЭТ(Г) с .М(Г).

Таким образом, для вычисления множества локальных минимумов ШТ(Г) достаточно для каждого набора К € JCS(N) перебрать все целочисленные решения т = (mi,..., ms) неравенства Q'/f)(m) ^ 4s • М^ЦТ) и выбрать среди векторов v — С(т) те, которые являются локальными минимумами решетки Г.

Так выглядит схема алгоритма вычисления локальных минимумов, предложенная в работе В.А. Быковского р]. Задача настоящей главы заключается в разработке и реализации этого алгоритма.

Для того чтобы все вычисления производить только с целыми числами, мы домножаем выражения вида (2) для квадратичных форм Q^K\m) на множители. Для каждого набора К = (fcb..., ks) G fCs(N) мы определяем положительно определенную квадратичную форму

. Q«\m) = ¿.(2^(m))2 ¿=i

где li = max{&i,,.., ка} — /с*. Все последующие рассуждения остаются без изменений.

Величина М^(Г) достигается на кратчайшем ненулевом векторе некоторой решетки и является квадратом его длины. Вычисление кратчайшего вектора представляет собой довольно нетривиальную задачу и имеет тесную связь с нахождением базисов решетки, составленных из коротких векторов.

Для эффективного перечисления целочисленных решений т = (mi,..., ms) неравенств

Qw(™)<4s-M(*>(r) (3)

мы используем базисы решеток, состоящие из коротких и почти ортогональных векторов. Такие базисы называются приведенными (reduced). Им соответствуют приведенные квадратичные формы. При использовании приведенных базисов все целочисленные решения неравенств (3) покоординатно ограничены константой, не завящей от размера задачи N (зависящей только от размерности пространства s).

В предложенной в работе В.А. Быковского f5] схеме алгоритма предлагается использовать базисы решеток, приведенные по Минковскому. Однако, время работы алгЬритма построения приведенного по Минковскому базиса возрастает экспоненциально с ростом размерности пространства s. Поэтому, мы используем LLL-приведенные базисы, которые можно вычислить за полиномиальное время. В отличие от базиса, приведенного по Минковскому, LLL-приведенный базис не обязательно содержит среди своих векторов кратчайший вектор решетки, однако позволяет аппроксимировать его с точностью до множителя Для вычисления кратчайшего вектора мы используем алгоритм перечисления Fincke-Pohst, который принимает на входе LLL-приведенный базис.

Оасним время работы алгоритма. Для каждого из O(log'4-1 N) наборов К = (hi,..., к\) нам требуется 0(s4(s + logJV)) времени для построения LLL-приведенного базиса и времени для вычисления кратчайшего вектора. Тогда общее время работы алгоритма оценивается выражением

OOog*"1 N) ■ {0(s4(s + log N)) + 2°^ . (4)

В третьей главе "Параметр Вахвалова и оптимальные коэффициенты" рассматривается применение алгоритма вычисления локальных минимумов решетки к нахождению параметров и оптимальных коэффициентов параллелепипедальных сеток Коробова. Для оптимизации вычислений вводится понятие эллиптических минимумов решетки и предлагается алгоритм для их вычисления. Этот алгоритм позволяет существенно ускорить вычисление оптимальных коэффициентов. В конце главы приводятся результаты вычислений оптимальных коэффициентов для размерностей s = 2,3.

Для приближенного вычисления кратных интегралов функций на единичном s-мерном кубе Qs — [О, l]s используются квадратурные формулы

1 N

(5)

С?,

где N € N. Точки ..., х^ называются узлами, их совокупность — сеткой, а величина /?лг(/) — погрешностью квадратурной формулы. Пусть аь ..., а, — целые числа, для которых НОД(аь..., а3, ЛГ) = 1.

Н.М. Коробов [7] предложил использовать параллелепипедальные сетки

••••#}) .....<6'

для подынтегральных функций, непрерывных в единичном 5-мерном кубе и имеющих период 1 по каждой из переменныххъ...,х3. Будем говорить, что функция

00 г

/(*)= £ где с(у)= П(х)е-2^хЫх

принадлежит классу Е", если для ее коэффициентов Фурье

|Ф)|<ШР

где а > 1 - действительное число. Для погрешности квадратурной формулы (5) на классе справедлива оценка

|Дл'(/)1 ^ С У'

V(zZn TV lav

7Коробов Н.М. Приближенное вычисление кратных интегралов с помощью методов теории чисел /' Н..Ч. Коробов // Доклады Академии наук СССР. — 1957. — Т. 115, ЛЖ — С. 1062-1065.

Суммирование здесь ведется но всем ненулевым целочисленным решениям v = (i-'i,..., vs) сравнения

aiVi + ... 4- asvs = 0 (mod N). (7)

Задача состоит .в том чтобы найти вектор а = (аг,..., as), минимизирующий сумму в правой части оценки для |Д,у(/)|. Наибольшие слагаемые в этой сумме соответствуют решениям v сравнения (7) с наименьшими значениями |1Н||. Так возникает идея о нахождении вектора а, который делает величину

аи=0 (mod -V)

как можно больше. Соответствующие значения ..., as называются оптимальными коэффициентами. Параметр q(a) (параметр Бахвалова), определяемый равенством (8), был предложен Н.С. Бахваловым f] и характеризует равномерную распределенность узлов параллелепипедальной сетки.

Назовем ненулевое целочисленное решение v = (?;ь .. ,,vs) сравнения (7) локально минимальным, если не существует другого ненулевого решения v' = (v[,v's), такого что < для всех г = 1,..., s и при этом хотя бы одно из этих s неравенств строгое. Заметим, что при определении параметра Бахвалова q(a) можно учитывать только локально минимальные решения, количество которых не превосходит 0(log8-1 N). Это наблюдение, сделанное В.А. Быковским [5], позволяет свести задачу вычисления параметра Бахвалова к задаче нахождения множества всех локально минимальных решений сравнения (7).

Все целочисленные решения сравнения (7) составляют некоторую целочисленную решетку Г = Г(а) в Rs определителя N. Локально минимальные решения соответствуют локальными минимумами решетки. В связи с этим мы можем рассматривать несколько более общую задачу — о вычислении множества локальных минимумов решетки Г. Параметр Бахвалова

9(a) = ff(T) = A||M||.

Для каждого набора (ki,... ,k3) мы рассматриваем квадратичную форму

Q[K\m) = ¿ (2г-А(т))2 = £ {2l%f = Q^(v). i=l ¿=1

Ее минимум

AfW(T)= mm QW(m) = nnn ¿ (24)' = £ ^

m^(0,...,0) i^(0,...,0) t=1 t=l

8Бахвалов Н.С. О приближенном вычислении кратных интегралов / Н.С. Бахвалов // Вестн. Моск. ун-та. Сер. Матем., мех., астрон., физ., хим. — 1959. — ЛЧ. — С. 3-18.

достигается на кратчайшем векторе "растянутой" решетки Г1ЛГ' с координатами (2''Fi;.... 2l'vs), определяющем узел v исходной решетки Г.

В пространстве переменных (vi,..., и,) - узлов решетки Г неравенство

¿ (2Ч)2 < М^Г) ¿=1

определяет эллипсоид с центром в начале координат, "вытянутый" вдоль некоторых координатных осей. Тот факт, что форма Q^K\v) достигает минимума в узле v, говорит о том что внутри этого эллипсоида нет ненулевых узлов решетки Г. Это означает, что для узла г; (назовем такой узел эллиптическим минимумом решетки Г) выполняются условия из определения локального минимума. Мы можем ограничиться включением вектора!; в список локальных минимумов и не перебирать с помощью алгоритма Fincke-Pohst все решения неравенства

Ql (m)

^ 4s • М(ЛГ)(Г).

В результате, мы избавимся от экпоненциального вклада во времени работы алгоритма (см. оценку (4)), но получим лишь множество эллиптических минимумов 9Я(Г).

Для приближенного параметра Бахвалова

д(Г) = min ИМИ иеал(Г)

справедлива

Теорема 3. Для любой s-мерной целочисленной решетки Г

д(Г) < «(Г) < 8'/29(Г).

С помощью алгоритма приближенного вычисления параметра Бахвалова можно существенно ускорить вычисление оптимальных коэффициентов. Для некоторого множества 5 решеток Г вычисление

Q(S) = тахд(Г)

можно организовать в два шага. Учитывая только эллиптические минимумы, с помощью "быстрого" варианта алгоритма находим значение

Q(S) = тахЭТГ). res 4 '

Затем для небольшого числа "экстремальных" решеток Г е S, на которых достигается максимум Q(S), вычисляем значения д(Г), учитывая все локальные минимумы. Если хотя бы для одной "экстремальной" решетки Г выполняется равенство q(T) = q(Г), то вычисленный на первом шаге максимум Q(S) совпадает с искомым значением Q(S). Числа ai,... ,as, определяющие любую "экстремальную" решетку Г, будут оптимальными коэффициентами.

Предложенная схема вычислений позволяет существенно сократить время вычисления оптимальных' коэффициентов. Перебор всех локальных минимумов мы осуществляем только для небольшого числа ''экстремальных" решеток, в то время как для остальных решеток мы ограничиваемся рассмотрением лишь эллиптических минимумов.

Отметим, что для набора К Е 1CS(N) LLL-приведенный базис соответствующей "растянутой" решетки Г^ не всегда содержит среди своих элементов кратчайший вектор решетки Г^', определяющий эллиптический минимум v исходной решетки Г. Поэтому, используя LLL-приведенные базисы, мы можем упустить некоторые эллиптические минимумы. Однако, это не является существенным. Основная идея рассмотренной схемы состоит в вычислении

тахо(Г). res 4 '

учитывая только вектора некоторого легко вычисляемого подмножества множества локальных минимумов (например, множества эллиптических минимумов) и последующей проверки того что для "экстремальных" решеток значение ç(T) не уменьшается при учете всех локальных минимумов.

В конце третьей главы приводятся результаты вычислений оптимальных коэффициентов для размерностей s = 2,3. Пусть N — 2Г, где г — натуральное число. Наиболее привлекательны с практической точки зрения параллелепи-педальные сетки вида (6) с коэффициентами а,- = l'~l mod N (1 < i < s), где целое I принимает нечетные значения от 1 до 2r_1 — 1.

В этом случае все целочисленные решения v — (v\,.vs) сравнения (7) составляют целочисленную решетку Г2г(1) определителя N с базисом

/N -а2 ••• -аД

Я _ 0 1 •■■ 0

О2<- =

\о" 'о' '..'."Т/

Наша задача состоит в нахождении значения параметра I, для которого величина д{Г2^(1)) достигает наибольшего значения

тахд(Г2г(0).

Для проведения вычислений разработана программная реализация рассмотренных в работе алгоритмов с использованием языка программирования С++. Для работы с большими числами используется библиотека NTL (Number Theory Library). Для лучшей производительности библиотека NTL используется вместе с GMP (GNU Multi-Precision library). Разработана программная реализация для проведения вычислений на многопроцессорных вычислительных комплексах с использованием интерфейса MPI (Message Passing Interface). Вычислительные эксперименты проводились на Linux кластере в Институте прикладной математике ДВО РАН в городе Владивостоке.

Автор выражает искреннюю благодарность своему научному руководителю В.А. Быковскому за всестороннюю поддержку на всех этапах выполнения работы.

Основные результаты диссертации

• Получен явный вид трехмерных областей Валена первого и второго типов. что уточняет теорему Валена.

• При нахождении областей Валена разработана методика, позволяющая легко получить известные ранее оценки для локальных минимумов, составляющих базис Минковского.

• На основе предложенной В.А. Быковским теоретической схемы разработан алгоритм для вычисления локальных минимумов целочисленных решеток.

• Разработан алгоритм для вычисления параметра Бахвалова и оптимальных коэффициентов параллелепипедальных сеток Коробова с помощью локальных минимумов.

• Построена модификация алгоритма вычисления локальных минимумов, позволяющая вычислять параметр Бахвалова приближенно и существенно ускорить вычисление оптимальных коэффициентов.

• Разработана программная реализация построеных алгоритмов.

• Вычислены значения оптимальных коэффициентов параллелепипедальных сеток Коробова для размерностей пространства s = 2,3.

Публикации по теме диссертации

1. Гассан C.B. О параметре оптимальности параллелепипедальных сеток Коробова для кубатурных формул / В.А. Быковский, C.B. Гассан // Журнал вычислительной математики и математической физики. — 2011. — Т. 51. — №8. — С. 13631369.

2. Гассан C.B. Алгоритм вычисления локальных минимумов целочисленных решеток и его приложения / В.А. Быковский, C.B. Гассан // Вестник Тихоокеанского государственного университета. — 2011. — №1(20). — С. 39-48.

3. Гассан C.B. Структура областей Валена для трехмерных решеток / C.B. Гассан // Чсбышевский сборник. - 2005. - T. VI. - Вып. 3(15). -Тула: Изд-во Тул. гос. пед. ун-та им. Л.Н. Толстого, 2005. — С. 51-84.

4. Гассан C.B. Алгоритм вычисления локальных минимумов целочисленных решеток и его приложения / В.А. Быковский, C.B. Гассан // Суперкомпьютеры: вычислительные и информационные технологии: материалы международной научно-практической конференции. — Хабаровск: Изд-во Тихоокеан. гос. ун-та, 2010. - С. 21-29.

5. Гассан C.B. О вычислении дискретных эллиптических минимумов целочисленных решеток / C.B. Гассан // XXXV Дальневосточная мате-

матическая школа-семинар имени академика Е.В. Золотова: сб. докл. (электронный ресурс). — Владивосток: ИАПУ ДВО РАН, 2010. - С. 5662,

6. Гассан С.В. О вычислении локальных минимумов целочисленных решеток / С.В. Гассан // Международный симпозиум "Образование, наука и производство: проблемы, достижения и перспективы": материалы Всероссийской конференции "Школа по фундаментальным основам моделирования обработки материалов" и научно-технической конференции "Математическое, вычислительное и информационное обеспечение технологических процессов и систем": В 5т. Т.4. — Комсомольск-на-Амуре: ГОУВПО "КнАГТУ", 2010. - С. 265-268.

7. Gassan S.V. Parallel implementation of the algorithm for calculating local minima of integral lattices / S.V. Gassan // First Russia and Pacific conference on computer technology and applications: electronic conference proceedings. - Vladivostok: IACP FEB RAS, 2010. - P. 183-187.

Гассан Сергей Владимирович

Вычислительные алгоритмы в геометрии чисел

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Подписано в печать 05.12.2011. Формат 60x84/16. Усл. п. л. 1. Уч.-изд. л. 1.1. Тираж 100 экз.

Отпечатано в ИПМ ДВО РАН. 690041, г. Владивосток, ул. Радио, 7.

Введение

1 Трехмерные области Валена

1.1 Основные определения и утверждения.

1.2 Вычисление области Валена первого типа.

1.3 Вычисление области Валена второго типа.

2 Алгоритм вычисления локальных минимумов целочисленных решеток

2.1 Основные определения и соотношения.

2.2 Теоретическая схема алгоритма.

2.3 Приведенные базисы и квадратичные формы.

2.4 Вычисление кратчайшего вектора решетки.

2.5 Алгоритмическая модель.

3 Параметр Бахвалова и оптимальные коэффициенты

3.1 Предварительные замечания.

3.2 Эллиптические минимумы.

3.3 Приближенный параметр Бахвалова.

3.4 Результаты вычислений.

Напомним, что а = [Ь о; £1,^2, •] (1) есть формальная запись канонического разложения вещественного числа а в непрерывную дробь 1 а = ¿о Н-1

1 +

2+ 1 с целым ¿о = [а] (целая часть а) и натуральными ¿i, ¿2, • • •, U, • • • (неполные частные). Оборвав непрерывную дробь (1) наг—ом шаге, получим подходящую дробь с взаимно простыми целым Р\ и натуральным Q{. Удобно положить Р-\ = 1 и Q-i = 0.

Обозначим через ||cü|| расстояние от числа а до ближайшего целого:

Ы| = min\а — п\ = minila:}, 1 — {а}), пеz 1 1 4 L J/ где {а} — дробная часть числа а. Имеем 0 ^ ||a|| ^ 1/2. Для подходящих дробей Pi/Qi хорошо известна оценка которую можно представить в виде

ФМИ < 1

3)

Вален [28] усилил ее, доказав неравенство

4)

В обоих случаях константы 1 и 1/2 нельзя заменить меньшими. Последнее неравенство обычно называют теоремой Валена для подходящих дробей.

Определение 1. Дробь р/д (р € Ъ, д € М) назовем наилучшим приближением числа а, если

Классическая теорема Лагранжа (см. [17]) утверждает, что последовательность подходящих дробей Д/ф* (г ^ 0 при {а} ^ 1/2 и г ^ 1 при {а} > 1/2) состоит из всех наилучших приближений числа а.

В конце XIX века, независимо друг от друга, Г.Ф. Вороной [12] и Г. Мин-ковский [27] положили это наблюдение в основу концепции локальных минимумов решеток с целью обобщения классического алгоритма непрерывных дробей на многомерный случай.

Определение 2. Пусть {7^,. ,7^} ~~ 5 линейно независимых точек вещественного евклидова пространства рассматриваемые как столбцы невырожденной матрицы (7 = (7^ . 7^) = {1^) с £ К.

Множество всех точек ад\\ = \ад-р\ и если щ\\ < \\щ'\\ для всех натуральных с{ < д.

Г = Г(£) = {7 = (71, • • • ,7-) = ^17(1) + • • ■ + I шь ., т, € г}

• ,т3 назовем полной s-мерной решеткой в Rs (для краткости, в дальнейшем слово "полная" будем опускать) с базисом (7^,. , 7^)

В случае если все числа 7^ являются целыми, то решетка называется целочисленной.

Положительную величину D — D(Г) = |det(C?)| назовем определителем решетки Г.

Равенство T(G) = Г (G') имеет место (см. [18]) тогда и только тогда, когда G' = G-S для некоторой унимодулярной матрицы S (целочисленной с det(S) - ±1).

Обозначим через £(RS) множество всех решеток в Ks, а через £*(RS) его подмножество, состоящее из всех решеток "общего положения", у которых для любого ненулевого узла 7 = (71,., 7S) все координаты 7i отличны от нуля. Другими словами, на координатных гиперплоскостях нет ненулевых узлов Г.

Назовем две матрицы G и G' эквивалентными, если одна получается из другой путем композиции некоторых преобразований вида:

1) изменение знака у столбца или строки;

2) перестановка двух столбцов или строк.

Определение 3. Ненулевой узел 7 = (71,., 7S) назовем локальным минимумом решетки Г, если не существует ненулевого узла rj = (771,., rjs) из Г, для которого

Ы ^ \li\ для всех г = 1,.,5, и при этом хотя бы одно из этих s неравенств строгое.

Замечание 1. Узлы 7 и —7 только одновременно могут являться локальными минимумами решетки.

Замечание 2. Для любого ненулевого узла г] решетки Г найдется локальный минимум 7, для которого ^ |туг| для всех г = 1,., в.

Замечание 3. Любой локальный минимум -у 6 Г примитивен в том смысле, что вектор'у/д не есть узел решетки Г для любого натурального q>l.

Эти свойства непосредственно следуют из определения локального минимума. Из теоремы Минковского о выпуклом теле (см. [18]) следует

Замечание 4. Для любого локального минимума ■у = (71,., 75) решетки Г выполняется неравенство

Ъ.Ъ\<П(Т). (5)

Составим из всех локальных минимумов решетки Г множество Ш?(Г). В двумерном случае рассмотрим решетку

Га = {7 = (ат! - га2, ТП\) = тп^а, 1) + т2(-1,0) | т\, т2 € Z} с Р(Га) = 1. Из уже упоминавшейся теоремы Лагранжа о наилучших приближениях следует, что для 0 < а < 1/2 множество локальных минимумов

ЯЯ(Га) = {±{аЯг - Рг, Яг)\г = о, 1,2,.}.

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

Э«Н < 1- (з)

Определение 4. Назовем матрицу О = (7^ . 7^) и определяемый ею базис (7^,., 7^) минимальными, если не существует ненулевого узла Г] из Г, для которого

Ы<тах{|711)|>.,|7<(0|} (* = !,.,*).

Понятно, что для решеток "общего положения" Г 6 каждый узел минимального базиса для Г является локальным минимумом решетки. Из определения непосредственно следует

Замечание 5. Эквивалентные матрицы (и соответствующие им базисы) минимальны только одновременно.

В двумерном случае Г.Ф. Вороной [12] доказал, что невырожденная матрица С, определяющая решетку Г = Г(С?) "общего положения" из £*(К2), минимальна тогда и только тогда, когда она эквивалентна некоторой матрице М вида м = (Х1

У2 ) с 0 ^ у\ ^ х\, 0 ^ Х2 ^ У2• Так как ёе^С) ^ 0, то всегда х\ > 0 и у2 > 0. В связи с этим введем следующие

Определение 5. Матрицы вида (без требования принадлежности определяемых ими решеток множеству £*(К2)) с 0 ^ у\ ^ х\, 0 ^ Х2 ^ У2, Х1У2 у^ 0, назовем матрицами Вороного. зисом Вороного, если соответствующая ему матрица эквивалентна матрице Вороного.

Построим отображение Ф2, сопоставляющее каждой матрице Вороного вектор в К2 по правилу

Определение 6. Базис (7^,7^) двумерной решетки Г назовем багде Б = Х\У2 + Х2У1 — определитель М. Назовем его образ У(Е2) двумерной областью Валена.

По причине однородности достаточно найти образ матриц Вороного с х\ = у2 = 1- То есть, образ квадрата [О, I]2 при отображении

Я2,У1) -> ( ~~—, т-^- ) •

1 + х2У1 1 ~Ь Х2У\)

Якобиан этого отображения равен

- <0, (1 + У1Х2У

Легко проверить, что образ границы [0,1]2 совпадает с границей области

ИЪ = {{х,у)еШ2 | 0 х + у ^ 1}.

Из простейших геометрических соображений отсюда следует, что У(М2) = \У2. Таким образом, мы вычислили двумерную область Валена, совпадающую с И^

Из вышесказанного следует, что для любого базиса Вороного (7^, 7^) решетки Г выполняется неулучшаемое неравенство

ЧЧ + Ы^'К^г), (6) которое уточняет оценку п{ Ы'Чг1'!. |712)722)| } < (7) непосредственно вытекающую из результатов работы Вороного [12]. По аналогии со своим частным случаем для подходящих дробей (см. оценку (4)), последнее неравенство называют теоремой Валена для двумерных решеток.

Вернемся теперь к решеткеГа (0 < а < 1/2). Хорошо известно (см. [17]), что с точностью до знака первой строки л г / ч I ~ Ъ 1 ~

М{(а) = (

Qi ^¿+1 матрица Вороного. Поэтому, в соответствии с (6), выполняется неравенство ЯшМ<+1 II ^ D(гa) = 1, уточняющее упомянутую выше классическую теорему Валена о том, что тт{д*||а<2*||, ЗшМшН } < ^ (4)

Это наблюдение, впервые отмеченное в [2], служит мотивировкой введенного нами понятия "область Валена" для двумерных решеток. В первой главе мы распространяем этот результат на трехмерный случай: мы вычисляем явный вид трехмерных областей Валена первого и второго типов. Обозначим через 03 С Мв единичный ¿-мерный куб: дз = {(хь.,Ое1Г| Кг^}.

Для приближенного вычисления кратных интегралов функций на кубе Я3 используются квадратурные формулы /(*<*>)-Я„(Л (8) в. к=1 где N — натуральное число. Точки . в которых вычисляются значения подынтегральной функции, называются узлами, их совокупность — сеткой, а величина Длг(/) — погрешностью квадратурной формулы.

Пусть а\,., а3 — целые числа, для которых НОД(аь ., а3, Щ = 1. В конце 60-х годов двадцатого века Н.М. Коробов [19] (см. также [20] и [21]) предложил использовать параллелепипедальные сетки для подынтегральных функций, непрерывных в единичном 5-мерном кубе и имеющих период 1 по каждой из переменных х\,.,х3.

Пусть функция f(x) разлагается в ряд Фурье

00

2ni(V'X) (9) vi,.,vs=-oo с коэффициентами с(у) = J f(x) e~27Ti^x) dx.

Gs

Введем обозначения щ = max{l, v||| = v\ •. -vs.

Будем говорить, что функция f(x) принадлежит классу Е£, если для ее коэффициентов Фурье выполняется оценка ф,)| * IMP где а > 1 — действительное число. В работе [21] показано, что если функция f(x) G Eg, то ее ряд Фурье (9) сходится абсолютно.

Для погрешности квадратурной формулы (8) на классе Е£ справедлива оценка

ЫЛ\« с (Ю)

N\a-v

Суммирование здесь ведется по всем ненулевым целочисленным решениям v — (vi,. ,vs) сравнения a\V\ + . + asvs = О (mod А7"). (11)

Задача состоит в том чтобы найти вектор а = (ai,., as), минимизирующий сумму в правой части оценки (10) для |Длг(/)|. Наибольшие слагаемые в этой сумме соответствуют решениям v сравнения (11) с наименьшими значениями |||и|||. Так возникает идея о нахождении вектора а, который делает величину д(а) =

Ш1П vezn\{o} а-ь=0 (тос! ЛГ)

III У

III

12) как можно больше. Соответствующие значения . ,а3 называются оптимальными коэффициентами

Параметр д, определяемый равенством (12), был предложен Н.С. Ба-хваловым в работе [3] (мы будем называть его параметром Бахвалова) и характеризует равномерную распределенность узлов параллелепипедаль-ной сетки

Первостепенное значение приобретает задача построения эффективных алгоритмов для вычисления параметра д и нахождения оптимальных коэффициентов а\,.,а3 в том смысле, что величина д не меньше заданной границы.

Назовем ненулевое целочисленное решение у = . ,у3) сравнения локально минимальным, если не существует другого ненулевого решения у' = (у[,., у'3), такого что \у[\ ^ |г/г| для всех г = 1,., б и при этом хотя бы одно из этих б неравенств строгое. Заметим, что при определении параметра Бахвалова д(а) можно учитывать только локально минимальдение, сделанное В.А. Быковским (см. работы [5] и [6]), позволяет свести задачу вычисления параметра Бахвалова к задаче нахождения множества всех локально минимальных решений сравнения (11).

Все целочисленные решения сравнения (11) составляют целочисленную решетку в определителя ДО. Локально минимальные решения соответа\У\ + . + а3у3 = 0 (тос! ДО) п) ные решения, количество которых не превосходит 0(к^ 1 ДО). Это наблюствуют локальными минимумами решетки. В связи с этим мы можем рассматривать несколько более общую задачу — о вычислении множества локальных минимумов решетки.

Во второй главе настоящей работы мы разрабатываем алгоритм вычисления множества локальных минимумов целочисленных решеток, основываясь на предложенной в работе В.А. Быковского [7] теоретической схеме. Мы рассматриваем основные составляющие части — алгоритм нахождения ЬЪЬ-приведенного базиса решетки и алгоритм Ртске-Ро]^ для вычисления кратчайшего вектора решетки.

В третьей главе мы рассматриваем применение алгоритма вычисления локальных минимумов к построению эффективного алгоритма нахождения параметра Бахвалова и оптимальных коэффициентов. Для оптимизации вычислений мы вводим понятие эллиптических минимумов решетки и предлагаем алгоритм для их вычисления. Этот алгоритм позволяет находить параметр Бахвалова приближенно и значительно сократить время вычисления оптимальных коэффициентов. В конце главы мы приводим результаты вычислений оптимальных коэффициентов для размерностей 5 = 2,3.

1. Авдеева М.О. Аналог теоремы Валена для совместных приближений пары чисел / М.О. Авдеева, В.А. Быковский // Математический сборник. - 2003. - Т. 194, №7. - С. 4-14.

2. Авдеева М.О. Уточнение теоремы Валена для базисов Минковского трехмерных решеток / М.О. Авдеева, В.А. Быковский // Математические заметки. 2006. - Т. 79, №2. - С. 163-168.

3. Бахвалов Н.С. О приближенном вычислении кратных интегралов / Н.С. Бахвалов // Вестн. Моск. ун-та. Сер. Матем., мех., астрон., физ., хим. 1959. - т. - С. 3-18.

4. Быковский В.А. Теорема Валена для двумерных подходящих дробей / В.А. Быковский // Математические заметки. — 1999. — Т. 66, №1. — С. 30-37.

5. Быковский В.А. О погрешности теоретико-числовых квадратурных формул / В.А. Быковский // Чебышевский сборник. — 2002. — Т. 3. — Вып. 2(4). — Тула: Изд-во Тул. гос. пед. ун-та им. Л.Н. Толстого, 2002. С. 27-33.

6. Быковский В.А. О погрешности теоретико-числовых квадратурных формул / В.А. Быковский // Доклады РАН. 2003. - Т. 389, №2. — С. 154-155.

7. Быковский В.А. Алгоритм вычисления локальных минимумов решеток / В.А. Быковский // Доклады РАН. 2004. - Т. 399, №5. - С. 587-589.

8. Быковский В.А. Алгоритм вычисления локальных минимумов целочисленных решеток и его приложения / В.А. Быковский, C.B. Гассан // Вестник Тихоокеанского государственного университета. — 2011. — №1(20). С. 39-48.

9. Быковский В.А. О параметре оптимальности параллелепипедаль-ных сеток Коробова для кубатурных формул / В.А. Быковский, C.B. Гассан // Журнал вычислительной математики и математической физики. 2011. - Т. 51. - №8. - С. 1363-1369.

10. Василенко О.Н. Теоретико-числовые алгоритмы в криптографии / О.Н. Василенко. М.: МЦНМО, 2003. - 328 с.

11. Вороной Г.Ф. Собрание сочинений / Г.Ф. Вороной. — Т.1. — Киев: 1952.

12. Гассан C.B. Область Валена для трехмерных матриц Минковского второго типа / C.B. Гассан // Препринт №06 / Хабаровское отделение института прикладной математики ДВО РАН. — Владивосток: Даль-наука, 2004. 13 с.

13. Гассан C.B. Структура областей Валена для трехмерных решеток / C.B. Гассан // Чебышевский сборник. — 2005. — Т. 6. — Вып. 3(15). — Тула: Изд-во Тул. гос. пед. ун-та им. JI.H. Толстого, 2005. — С. 51-84.

14. Касселс Дж.В.С. Введение в теорию диофантовых приближений / Дж.В.С. Касселс. М.: ИЛ., 1961. - 213 с.

15. Касселс Дж.В.С. Введение в геометрию чисел / Дж.В.С. Касселс. М.: Мир, 1965. - 421 с.

16. Коробов Н.М. Приближенное вычисление кратных интегралов с помощью методов теории чисел / Н.М. Коробов // Доклады Академии наук СССР. 1957. - Т. 115, №6. - С. 1062-1065.

17. Коробов H.M. О приближенном вычислении кратных интегралов / Н.М. Коробов // Доклады Академии наук СССР. — 1959. — Т. 124, т. С. 1207-1210.

18. Коробов Н.М. Теоретико-числовые методы в приближённом анализе / Н.М. Коробов. М.: МЦНМО, 2004. - 288 с.

19. Рышков С.С. К теории приведения положительных квадратичных форм по Эрмиту-Минковскому / С.С. Рышков // Исследования по теории чисел. 2, Зап. научн. сем. ЛОМИ. — Л.: Наука, 1973. — Т. 33.- С. 37-64.

20. Cohen H. A Course in Computational Algebraic Number Theory / H. Cohen // Graduate Texts in Math. — Vol. 138. — Springer-Verlag, Berlin Heidelberg, 1993. (Algorithm 1.3.14.)

21. Fincke U. Improved methods for calculating vectors of short length in a lattice, including a complexity analysis / U. Fincke, M. Pohst // Math. Сотр. Vol. 44. - 1985. - P. 463-471.

22. Lenstra A.K. Factoring Polynomials with rational coefficients / A.K. Lenstra, H.W. Lenstra, L. Lovasz // Math. Ann. Vol. 261. - 1982.- P. 515-534.

23. Minkowski H. Generalization de la theorie des fraction continues / H. Minkowski // Ann. Sci. École Norm. Sup. 1896. - Vol. 13, №2.- P. 41-60.

24. Vahlen K.Th. Über Näherungswerte und Kettenbrüche / K.Th. Vahlen // J. für Math. Vol. 115. - 1895. - P. 221-233

25. Vallee B. Une approche geometrique des algorithmes de reduction en petite dimension, Thesis / B. Vallee; Univ. of Caen. — 1986.

26. NTL: A Library for doing Number Theory. URL: http://www.shoup.net/ntl/

27. The GNU Multiple Precision Arithmetic Library. URL: http://gmplib.org/

28. The Message Passing Interface (MPI) standard. URL: http://www.mcs.anl.gov/research/projects/mpi/