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

• Автор: Гассан, Сергей Владимирович
• Шифр специальности: 01.01.07
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Владивосток
• Количество страниц: 71 с. : ил.

Оглавление
Введение

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 Результаты вычислений
Литература

Введение
Напомним, что
(У. [іо, П? 2) > и,.] (1)
есть формальная запись канонического разложения вещественного числа а в непрерывную дробь

а = іо -
с целым £о = [а] (целая часть а) и натуральными Д, , к, (неполные частные). Оборвав непрерывную дробь (1) наг—ом шаге, получим подходящую дробь
= [<о;*1,*2
с взаимно простыми целым р и натуральным (г. Удобно положить Р_х = 1 и <2_1 = 0.
Обозначим через ||а|| расстояние от числа а до ближайшего целого:
||а|| — тш |а - п — тт({а}, 1 — {а}),
где {а:} — дробная часть числа а. Имеем 0 ||а|| 1/2.
Для подходящих дробей Pi/Qi хорошо известна оценка
которую можно представить в виде
<2гМг|| < 1. (3)
Вален [28] усилил ее, доказав неравенство
тт{ф||аф||, ф-иНаф+хН } < (4)
В обоих случаях константы 1 и 1/2 нельзя заменить меньшими. Последнее неравенство обычно называют теоремой Валена для подходящих дробей.
Определение 1. Дробь р/д (р 6 2/ д 6 К) назовем наилучшим приближением числа а, если
1М| = щ-р
и если
ЦодН < ||сп/|| для всех натуральных ({ < д.
Классическая теорема Лагранжа (см. [17]) утверждает, что последовательность подходящих дробей Р{/С}1 (г 0 при {а} 1/2 и г 1 при {а} > 1/2) состоит из всех наилучших приближений числа а.
В конце XIX века, независимо друг от друга, Г.Ф. Вороной [12] и Г. Мин-ковский [27] положили это наблюдение в основу концепции локальных минимумов решеток с целью обобщения классического алгоритма непрерывных дробей на многомерный случай.
Определение 2. Пусть {7
Г = Г(С) = {7 = (71

Глава
Алгоритм вычисления локальных минимумов целочисленных решеток
В данной главе рассматривается построение алгоритма вычисления множества локальных минимумов целочисленных решеток. Ключевую роль в вычислительной схеме играют приведенные базисы и кратчайшие вектора решеток, алгоритмы вычисления которых обсуждаются в отдельных параграфах. В конце главы предлагается алгоритмическая модель для программной реализации рассмотренных алгоритмов и оценивается асимптотическое время работы.
Настоящая глава основана па работе [8] (см. также [9, 15, 16, 25]).
§2.1. Основные определения и соотношения
Пусть £: произвольное невырожденное линейное преобразова-
ние, которое в координатной форме имеет вид
1а(гаЛ (ьп Ъп ЬіД /гаД
—> С{т)
Ь2(т) Ь21 £>22 £>2£ т2