Цилиндрическое алгебраическое разложение

В математике цилиндрическая алгебраическая декомпозиция ( САПР ) — это понятие, а также алгоритм его вычисления, которое является фундаментальным для компьютерной алгебры и реальной алгебраической геометрии . Учитывая набор S многочленов из R ^н, цилиндрическое алгебраическое разложение — это разложение R ^н на связные полуалгебраические множества , называемые клетками , в которых каждый многочлен имеет постоянный знак: +, - или 0. Чтобы быть цилиндрическим , это разложение должно удовлетворять следующему условию: Если 1 ≤ k < n и π — проекция из R ^н на R ^{п - к}заключающийся в удалении последних k координат, то для каждой пары ячеек c и d имеет место либо π ( c ) = π ( d ), либо π ( c ) ∩ π ( d ) = ∅. Отсюда следует, что образы по π ячеек определяют цилиндрическое разложение R ^{п - к}.

Это понятие было введено Джорджем Э. Коллинзом в 1975 году вместе с алгоритмом его вычисления.

Алгоритм Коллинза имеет вычислительную сложность , двойную экспоненциальную по n . Это верхняя граница, которая достигается для большинства записей. Существуют также примеры, для которых минимальное количество ячеек является дважды экспоненциальным, показывая, что каждый общий алгоритм цилиндрического алгебраического разложения имеет двойную экспоненциальную сложность.

САПР обеспечивает эффективную версию исключения кванторов над действительными числами, которая имеет гораздо лучшую вычислительную сложность, чем та, которая получена в результате исходного доказательства теоремы Тарского-Зейденберга . Он достаточно эффективен, чтобы быть реализованным на компьютере. Это один из наиболее важных алгоритмов вычислительной реальной алгебраической геометрии . Поиск улучшения алгоритма Коллинза или создание алгоритмов большей сложности для подзадач, представляющих общий интерес, является активной областью исследований.

Реализации [ править ]

Ссылки [ править ]

Басу, Саугата; Поллак, Ричард; Рой, Мари-Франсуаза Алгоритмы в реальной алгебраической геометрии. Второе издание. Алгоритмы и вычисления в математике, 10. Springer-Verlag, Берлин, 2006. x+662 стр. ISBN 978-3-540-33098-1 ; 3-540-33098-4
Стржебонский, Адам. Цилиндрическое алгебраическое разложение из MathWorld .
Цилиндрическая алгебраическая декомпозиция в главе 6 («Комбинаторное планирование движения») алгоритмов планирования Стивена М. ЛаВалле. По состоянию на 8 февраля 2023 г.
Кэвинесс, Боб; Джонсон, Джереми; Устранение кванторов и цилиндрическое алгебраическое разложение . Тексты и монографии по символьным вычислениям. Шпрингер-Верлаг, Берлин, 1998 г.
Коллинз, Джордж Э.: Устранение кванторов в элементарной теории действительных замкнутых полей путем цилиндрического алгебраического разложения, Вторая конференция GI. Теория автоматов и формальные языки, Springer LNCS 33, 1975.
Давенпорт, Джеймс Х.; Хайнц, Йоос : Исключение реальных кванторов является дважды экспоненциальным, Журнал символических вычислений, 1988. Том 5, выпуски 1–2, ISSN 0747-7171,

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