원통대수분해
Cylindrical algebraic decomposition수학에서 원통형 대수분해(CAD)는 컴퓨터 대수학과 실제 대수 기하학의 기초가 되는 개념이자 이를 계산하는 알고리즘이다.R에서n 다항식의 집합 S를 주어진 원통형 대수 분해는 R을n 셀이라고 불리는 연결된 반항게브라 집합으로 분해하는 것으로, 그 위에 각 다항식에는 +, - 또는 0의 상수 기호가 있다.원통형이 되려면 이 분해는 다음 조건을 만족시켜야 한다.1 ≤ k < n과 π이 마지막 k 좌표를 제거하는 데 구성된 R에서n R까지n−k 투영된 경우, c와 d의 모든 쌍에 대해 ((c) = ((d) 또는 ((c) ((c) ∅(d) = ∅. 이는 세포의 π에 의한 영상이 R의n−k 원통형 분해를 정의한다는 것을 의미한다.
이 개념은 1975년 조지 E. 콜린스에 의해 그것을 계산하는 알고리즘과 함께 도입되었다.
콜린스의 알고리즘은 계산 복잡성이 n에서 두 배로 기하급수적이다.이것은 대부분의 항목에서 도달하는 상한 값이다.원통형 대수분해를 위한 모든 일반 알고리즘이 이중 지수적 복잡성을 갖는다는 것을 보여 주는 최소한의 셀 수가 이중 지수적임을 보여주는 사례도 있다.
CAD는 Tarski-Seidenberg 정리의 원래 증명에서 비롯되는 것보다 훨씬 더 우수한 계산 복잡성을 가진 실물에 대한 정량화 제거의 효과적인 버전을 제공한다.그것은 컴퓨터로 실행될 만큼 충분히 효율적이다.그것은 계산 실제 대수 기하학의 가장 중요한 알고리즘 중 하나이다.콜린스의 알고리즘을 개선하거나, 일반 관심사에 대한 하위 문제에 대해 더 나은 복잡성을 가진 알고리즘을 제공하기 위해 검색하는 것은 활발한 연구 분야다.
구현
참조
- 바수, 스가타; 폴락, 리처드; 로이, 마리 프랑수아즈 알고리즘 실제 대수 기하학.제2판.수학에서의 알고리즘과 연산, 10. 베를린, 2006. x+662 pp. ISBN978-3-540-33098-1; 3-540-33098-4
- 스트르제본스키, 아담.수학월드에서 원통형 대수분해.
- Steven M. LaValle에 의한 계획 알고리즘의 원통 대수 분해.2007년 7월 13일에 액세스
- Caveness, Bob; Johnson, Jeremy; Quantifier Removal and Circlean Gaemiic Discovery.심볼 연산에서의 텍스트 및 모노그래프.1998년 베를린 스프링거-베를라크.
- 콜린스, 조지 E.:원통형 대수 분해에 의한 실제 폐쇄장 기본 이론의 정량화 제거, Second GI Conf.오토마타 이론과 공식 언어, Springer LNCS 33, 1975.
