Вычислительные алгоритмы в геометрии чисел тема диссертации и автореферата по ВАК РФ 01.01.07, кандидат физико-математических наук Гассан, Сергей Владимирович

• Гассан, Сергей Владимирович
• кандидат физико-математических наук
• 2011

Оглавление диссертации кандидат физико-математических наук Гассан, Сергей Владимирович

Введение

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.

Список литературы диссертационного исследования кандидат физико-математических наук Гассан, Сергей Владимирович, 2011 год

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/