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