Оглавление
Предисловие 6
Несколько замечаний исторического характера ...................... 6
О тематике диссертации............................................ 7
I ВВЕДЕНИЕ 9
1 Общая характеристика работы 10
1.1 Актуальность темы и обзорные замечания ....................... 10
1.1.1 О перемножении чисел................................. 10
1.1.2 О перемножении полиномов ............................ 11
1.1.3 Метод БВЕ............................................ 12
1.1.4 О вычислении полиномов одного переменного ........... 14
1.1.4.1 Постановка задач ............................ 14
1.1.4.2 Нижние оценки................................ 15
1.1.4.3 Верхние оценки............................... 16
1.1.4.4 Общие замечания ............................. 16
1.1.5 О вычислении полиномов многих переменных............. 16
1.1.6 Вычисления в алгебрах................................ 16
1.1.6.1 Алгебры с делением........................... 16
1.1.6.2 Матричная алгебра (верхние оценки)........... 17
1.1.6.3 Нижние оценки для некоторых ассоциативных
алгебр....................................... 18
1.1.6.4 Групповые алгебры ........................... 19
1.1.6.5 Антикоммутативные алгебры и алгебры Ли . . 20
1.2 Краткое содержание и основные результаты диссертации ... 21
1.2.1 Цель диссертации..................................... 21
1.2.2 Научная и практическая ценность...................... 22
1.2.3 Методы исследования.................................. 22
1.2.4 Публикации и апробирование........................... 22
1.2.5 Личный вклад автора.................................. 22
1.2.6 Структура и объем диссертации........................ 23
1.2.7 Несколько замечаний о доказательствах теорем .... 23
2
1.2.8 Гипотеза о мультипликативной сложности простых алгебр ........................................................ 23
1.2.9 Научная новизна........................................ 24
1.2.10 Сравнение нижних оценок, полученных автором диссертации, с нижними оценками других авторов.................. 25
1.2.10.1 Нижние оценки для простых алгебр Ли .... 25
1.2.10.2 Нижние оценки для пильпотентных и разрешимых алгебр Ли ...................................... 26
1.2.10.3 Нижние оценки для пильпотентных ассоциативных алгебр......................................... 26
1.2.10.4 Нижние оценки для пильпотентных верхнетреугольных матричных алгебр и алгебр Ли малых размерностей.................................... 27
1.2.11 Основные результаты диссертации, выносимые на защиту ........................................................ 27
1.2.11.1 Нижние оценки тензорного ранга для классических простых алгебр Ли серий 21/, 23/, £/,
£/............................................ 27
1.2.11.2 Нижние оценки тензорного ранга для нильпо-тентных алгебр Ли..................................... 27
1.2.11.3 Нижние оценки тензорною ранга для разрешимых алгебр Ли ...................................... 28
1.2.11.4 Нижние оценки тензорного ранга для нильпо-тентных ассоциативных алгебр ......................... 29
1.3 Благодарности................................................ 29
2 Предварительные сведения, основные определения и обозначения 30
2.1 Основы алгебраической теории сложности ...................... 30
2.1.1 Направленные схемы (иеветвящиеся программы) .... 30
2.1.2 Вычислительная модель.................................. 31
2.1.3 Сложность направленной схемы........................... 32
2.1.4 Алгебраическая сложность............................... 33
2.1.5 Алгоритмы без деления.................................. 34
2.2 Кольца и алгебры ............................................ 34
2.3 Тензоры...................................................... 37
2.3.1 Определение тензора.................................... 37
2.3.2 Координаты тензора..................................... 38
2.3.3 Структурный тензор алгебры............................. 40
2.3.4 Тензорный ранг......................................... 41
2.3.5 Тензорный ранг алгебры................................. 42
2.4 Обозначения применяемые в основной части диссергации ... 43
--------- 3 ----
2.4.1 Некоторые используемые шрифты.................... 43
2.4.2 Некоторые используемые сокращения и обозначения . . 43
2.5 Структуры, рассматриваемые в основной части диссертации . 44
II ОРИГИНАЛЬНЫЕ РЕЗУЛЬТАТЫ АВТОРА 45
3 Нижние оценки тензорного ранга для классических простых алгебр Ли серий 21/, 23/, £/, £>/ 46
3.1 Обозначения .............................................. 46
3.2 Нижние оценки для простых алгебр.......................... 48
4 Нижние оценки тензорного ранга для нильпотентных и разрешимых алгебр Ли 56
4.1 Обозначения .............................................. 56
4.2 Нижние оценки для нильпотентных алгебр Ли................. 57
4.3 Об алгебре нильпотентных строго верхнетреугольных матриц 62
4.4 О константах в оценках для нильпотентных алгебр Ли .... 63
4.5 Вторая нижняя оценка...................................... 63
4.6 Нижние оценки для разрешимых алгебр Ли ................... 65
5 Нижние оценки тензорного ранга для нильпотентных ассоциативных алгебр 68
5.1 Обозначения .............................................. 68
5.2 Нижние оценки для нильпотентных ассоциативных алгебр . . 69
5.3 Первая нижняя оценка ..................................... 69
5.4 О коэффициентах при слагаемых в нижних оценках............ 75
5.5 Нижняя оценка тензорного ранга для алгебры строго верхнетреугольных нильпотентных матриц 76
5.6 Вторая нижняя оценка ..................................... 77
6 Применение нижних оценок тензорного ранга к нильпотент-ным алгебрам Л[и малых размерностей над полями К и С 79
6.1 Обозначения .............................................. 79
6.2 Алгебры над полем комплексных чисел....................... 80
6.2.1 Идеалы в алгебрах................................... 80
6.2.2 Некоторые замечания о верхних оценках............... 80
6.2.3 Сравнение верхних и нижних оценок................... 81
6.3 Алгебры над полем действительных чисел ................... 82
Заключение 85
Простые классические алгебры Ли серий 21/, 23/, С/, ©/...... 85
Нильпотентные и разрешимые алгебры.......................... 85
Алгебры Ли малых размерностей .................................... 86
Литература 87
Публикации других авторов по теме диссертации..................... 87
Публикации автора но теме диссертации............................. 92
5
Предисловие
Несколько замечаний исторического характера
Вычислительная сложность в античные времена. Без всякого преувеличения можно утверждать, что возникновение вопросов, касающихся сложности вычислений, относится к тем самым временам, когда происходили первые попытки систематизации математического знания. В качестве примера можно привести составленные в античные времена таблицы отношений хорд к дуге окружности, которые в современной терминологии можно охарактеризовать как „грандиозный вычислительный проект“ и который выполнить было бы намного труднее, если бы длину хорды вычисляли традиционным для того времени способом — как периметр вписанных в окружность правильных многоугольников. При подобных вычислениях, однако, широко применялось утверждение, известное как теорема Птолемея: прямоугольник на диагонали вписанного в круг четырехугольника равен сумме прямоугольников па двух парах противолежащих сторон. Данная теорема позволяла „заменять“ умножение сложением — имея определенный запас вычисленных хорд, можно довольно просто вычислять некоторые новые хорды из комбинаций уже имеющихся. Этот способ вычисления соответствует современным формулам
виДа ± /3) = ып(а) сов(/?) ± 8ш()0) соз(а)
2вт2(а/2) = 1 — соз(а)
Это позволяло значительно сократить объем вычислений и провести их в более сжатые (по меркам того времени) сроки.
Даже беглый взгляд на историю математики показывает, что появление практически любого математического раздела, исследовавшего ту или иную задачу, рано или поздно влекло появление соответствующего „вычислительного“ раздела, в котором задачи, имеющие более или менее „теоретическое“ обоснование, исследовались с позиций сложности, затратности вычислений. Со временем эти разделы становились практически самостоятельными областями исследования, которые развивались по своим собственным законам
ПРЕДИСЛОВИЕ
и имели свои собственные побудительные причины и движущие силы.
Все они были направлены на поиски оптимальных путей решения задач, где оптимальность поиимааась естественным образом как возможность производить наименьшее количество (например, арифметических) действий. В какой-то степени их можно рассматривать как попытку очертить реальные возможности науки и практики для данного исторического уровня развития.
Теория сложности в XX веке. Х1Х-ХХ века открыли новую страницу в теории сложности. Уточнялось понятие алгоритма, были предложены его новые определения, также появилось понимание эквивалентности его различных определений. Это создало серьезный базис для дальнейших теоретических и практических исследований.
В середине XX века под влиянием как инженерно-производственных, так и внутриматематических причин получил новый импульс круг задач довольно широкой тематики, в которых ключевым стало понятие сложности вычислений и который условно можно назвать алгоритмической и дискретной теорией сложности. К этому кругу можно отнести:
• некоторые области теории чисел,
• новые области так называемых быстрых вычислений,
• криптографию,
• алгебраические и комбинаторные алгоритмы,
• теорию булевых функций (схемы из логических элементов)
и многие другие области.
В этих областях понятие сложности стало либо ключевым, либо одним из наиболее важных. С учетом новых понятий были переосмыслены прежние и поставлены новые задачи. Одни из поставленных задач были решены относительно быстро. Другие быстрому решению не поддавались, перерастая, таким образом, в математические проблемы, которые, впрочем, продолжали исследоваться. Все это позволяет говорить о том, что в XX веке появилось новое направление в вычислительной науке — теория сложности, со своим кругом задач, подходами к их решению, методами и достижениями. Каждая отдельная область, впрочем, имеет свою специфику и свои особенности.
О тематике диссертации
Самая общая тема, рассматриваемая в данной работе, — оптимальные алгоритмы для вычисления произведений в алгебрах, над полями характе-
- Київ+380960830922