В математике цилиндрическое алгебраическое разложение ( САПР ) — это понятие, наряду с алгоритмом его вычисления, которое является фундаментальным для компьютерной алгебры и реальной алгебраической геометрии . Если задано множество S полиномов в Rn , цилиндрическое алгебраическое разложение — это разложение Rn на связные полуалгебраические множества , называемые ячейками , на которых каждый полином имеет постоянный знак, либо +, −, либо 0. Чтобы быть цилиндрическим , это разложение должно удовлетворять следующему условию: если 1 ≤ k < n и π — это проекция из Rn на Rn − k , состоящая в удалении последних k координат, то для каждой пары ячеек c и d выполняется либо π ( c ) = π ( d ) , либо π ( c ) ∩ π ( d ) = ∅. Это означает, что изображения ячеек по π определяют цилиндрическое разложение R n − k .
Понятие было введено Джорджем Э. Коллинзом в 1975 году вместе с алгоритмом его вычисления.
Алгоритм Коллинза имеет вычислительную сложность , которая является двойной экспоненциальной по n . Это верхняя граница, которая достигается для большинства записей. Существуют также примеры, для которых минимальное число ячеек является двойной экспоненциальной, показывая, что каждый общий алгоритм для цилиндрической алгебраической декомпозиции имеет двойную экспоненциальную сложность.
САПР предоставляет эффективную версию исключения квантификаторов по действительным числам, которая имеет гораздо лучшую вычислительную сложность, чем та, что получается из исходного доказательства теоремы Тарского–Зейденберга . Она достаточно эффективна для реализации на компьютере. Это один из важнейших алгоритмов вычислительной действительной алгебраической геометрии . Поиски улучшения алгоритма Коллинза или предоставления алгоритмов, которые имеют лучшую сложность для подзадач общего интереса, являются активной областью исследований.