우의 특성 집합의 방법

Wu's method of characteristic set

Wenjun Wu의 방법은 중국의 수학자 Wen-Tsun Wu에 의해 1970년대 후반에 도입된 다변량 다항식을 풀기 위한 알고리즘입니다. 이 방법은 J.F.가 1940년대 후반에 도입한 특성 집합의 수학적 개념을 기반으로 합니다. 릿. 특성 집합을 계산하는 데 그뢰브너 기저를 사용할 수 있다고 하더라도 Bruno Buchberger(1965)가 도입한 그뢰브너 기저 방법과는 완전히 독립적입니다.[1][2]

Wu의 방법은 기본 기하학에서 기계적 정리 증명에 강력하며 특정 클래스의 문제에 대한 완전한 결정 프로세스를 제공합니다. 그의 연구실(KLMM, Key Laboratory of Mathematics Mechanization in Chinese Academy of Science)과 전 세계에서 연구에 사용되었습니다. Wu의 방법에 대한 주요 연구 동향은 Ritt의 결과가 효과적인 양의 차원의 다항식과 미분 대수 시스템에 관한 것입니다.[3][4] Wu의 방법은 생물학, 컴퓨터 비전, 로봇 운동학 및 특히 기하학의 자동 증명과 같은 다양한 과학 분야에 적용되었습니다.[5]

비공식적 설명

Wu의 방법은 다항식 나눗셈을 사용하여 형식의 문제를 해결합니다.

여기서 f는 다항식이고 I는 다항식의 합입니다. 알고리즘은 복잡한 도메인에서 이러한 문제에 대해 완전합니다.

알고리즘의 핵심 아이디어는 하나의 다항식을 다른 다항식으로 나누어 나머지를 줄 수 있다는 것입니다. 분할을 반복하면 나머지가 사라지거나(이 경우 I는 f 문이 참임을 암시함), 축소할 수 없는 나머지가 남습니다(이 경우 문이 거짓임).

보다 구체적으로, 어떤 장 k 위의 고리 k[x1, ..., xn]에서 이상 I에 대하여, I의 (Ritt) 특성 집합 C는 삼각형 모양인 I의 다항식 집합으로 구성되며, C의 다항식은 서로 다른 주요 변수를 갖습니다(아래 공식 정의 참조). I의 특성 집합 C가 주어지면 다항식 f가 0 모듈로 I인지 여부를 결정할 수 있습니다. 즉, I의 특성 집합을 제공하면 I에 대해 멤버십 테스트를 확인할 수 있습니다.

Ritt 특성 집합

리트 특성 집합은 이상의 삼각형 형태의 유한 다항식 집합입니다. 이 삼각형 집합은 Ritt 순서와 관련하여 특정 최소 조건을 만족하며 이상의 많은 흥미로운 기하학적 특성을 보존합니다. 그러나 발전기 시스템이 아닐 수 있습니다.

표기법

어떤 장 k에 대하여 R을 다변량 다항식환 k[x1, ..., x]라고n 합니다. 변수들은 아래첨자 x1 < ... < x 에n 따라 선형적으로 정렬됩니다. R 에서 비 상수 다항식 p 의 경우, p 에 효과적으로 나타나는 가장 큰 변수인 주 변수 또는 클래스가 특정한 역할을 합니다. p 는 당연히 k[x1, ..., x] 의k−1 계수를 갖는 주 변수 xk 에서 일변량 다항식으로 간주될 수 있습니다. 주 변수에서 일변량 다항식인 p의 차수를 주 차수라고도 합니다.

삼각집합

일정하지 않은 다항식의 집합 T는 T의 모든 다항식이 서로 다른 주 변수를 갖는 경우 삼각형 집합이라고 합니다. 이를 통해 삼각형 선형 방정식 시스템을 자연스러운 방식으로 일반화할 수 있습니다.

리트오더

두 개의 일정하지 않은 다항식 p와 q의 경우, 다음 중 하나의 인수가 성립하는 경우, p는 Ritt 순서와 관련하여 q보다 작으며 p r< q로 표기됩니다.

(1) p의 주 변수는 q의 주 변수보다 작습니다. 즉 mvar(p) < mvar(q),
(2) p와 q는 주변수가 같고, p의 주도는 q의 주도보다 작으며, 즉 mvar(p) = mvar(q) 및 mdeg(p) < mdeg(q).

이와 같이 (k[x1, ..., xn],<)r는 잘 부분적인 순서를 형성합니다. 그러나 Ritt 순서는 완전한 순서가 아닙니다. p r< q도 p r> q도 아닌 다항식 p와 q가 존재합니다. 이 경우 p와 q는 비교 대상이 아니라고 합니다. Ritt 순서는 p와 q의 순위를 비교하는 것입니다. 순위(p)로 표시되는 비일관 다항식 p의 순위는 주요 변수의 거듭제곱으로 정의됩니다. mvar(p)mdeg(p)와 순위는 먼저 변수를 비교한 다음 변수가 동일한 경우 차수를 비교합니다.

삼각형 집합에 대한 Ritt 순서 지정

Ritt 순서에 대한 중요한 일반화는 삼각형 집합을 비교하는 것입니다. T = { t, ..., t} 와 S = {s, ..., s} 가 T와 S의 다항식이 주요 변수에 따라 점점 더 많이 정렬되도록 두 삼각형 집합이라고 합니다. 우리는 T가 SWR.T보다 작다고 말합니다. 다음 주장 중 하나가 성립하는 경우 Ritt 순서 지정

  1. 1 ≤ i < k 및 t < s에 대하여 rank(t) = rank(s)가 되도록 k ≤ min(u, v)가 존재하며,
  2. u >v 및 rank(t) = 1 ≤ i ≤ v에 대한 rank(들).

또한, 비교할 수 없는 삼각형 세트 w.r.t Ritt 순서가 존재합니다.

Ritt 특성 집합

k[x1, ..., xn]의 0이 아닌 이상이 되게 해주세요. I의 부분 집합 T는 다음 조건 중 하나가 성립할 경우 I의 Ritt 특성 집합입니다.

  1. T는 0이 아닌 k개의 상수로 구성됩니다.
  2. T는 삼각형 집합이고 T는 I에 포함된 모든 삼각형 집합의 집합에서 최소 w.r.tRitt 순서입니다.

Ritt 순서는 부분 순서이므로 다항식 이상은 (무한히) 많은 특성 집합을 가질 수 있습니다.

Wu 특성 집합

Ritt가 처음 고안한 Ritt-Wu 과정은 Wu가 수정한 Ritt 특성이 아니라 Wu 특성 집합 또는 오름차순이라고 하는 확장된 특성을 계산합니다.

F에 의해 생성된 이상적인 ⟨ F ⟩의 비어 있지 않은 부분 집합 T는 다음 조건 중 하나가 성립할 경우 F의 Wu 특성 집합입니다.

  1. 0이 아닌 상수인 T = {a},
  2. T는 삼각형 집합이고 ⟨ F ⟩ = ⟨ G ⟩ 및 G의 모든 다항식이 T에 대해 의사 reduced 0이 되도록 ⟨ F ⟩의 부분 집합 G가 존재합니다.

Wu 특성 집합은 F에 의해 생성된 이상적인 ⟨ F ⟩이 아니라 다항식의 집합 F로 정의됩니다. 또한 ⟨ F ⟩의 Ritt 특성 집합 T는 F의 Wu 특성 집합임을 알 수 있습니다. Wu 특성 세트는 Wu의 알고리즘 CHRST-REM에 의해 계산될 수 있으며, 이는 의사 나머지 계산만 필요하고 인수분해는 필요하지 않습니다.

Wu의 특성 집합법은 기하급수적인 복잡성을 가지고 있으며, 약사슬, 정사슬, 포화사슬에 의한 연산효율의 향상을 소개했습니다[6].

대수다양체 분해

응용 프로그램은 특성 집합을 통해 대수 방정식 시스템을 푸는 알고리즘입니다. 더 정확하게는, 다항식의 유한 부분 집합 F가 주어졌을 때, 다음과 같은 특성 집합1 T, ..., T를e 계산하는 알고리즘이 있습니다.

여기서 W(Ti)는 V(Ti)와 V(hi)의 차이이고, 여기서 H는i T에i 있는 다항식의 이니셜의 곱입니다.

참고 항목

참고문헌

  1. ^ Corrochano, Eduardo Bayro; Sobczyk, Garret, eds. (2001). Geometric algebra with applications in science and engineering. Boston, Mass: Birkhäuser. p. 110. ISBN 9780817641993.
  2. ^ P. 오브리, D. 라자드, M. 모레노 마자(1999). 삼각형 집합의 이론에 대해서. 기호계산학회지, 28(1–2):105–124
  3. ^ Hubert, E. 미분대수에서의 인수분해 자유분해 알고리즘. Journal of Symbol Computation, (2000년 5월): 641-662.
  4. ^ 메이플(소프트웨어) 패키지 디플로그.
  5. ^ 주, 상칭, 가오, 샤오산, 장, 징중. 기하학에서 기계 증명. 월드 사이언티픽, 1994.
  6. ^ Chou SCC, Gao X S; Ritt-Wu의 분해 알고리즘과 기하학 정리 증명. CADE, 10 LNCS, #449, 베를린, 스프링어 베를라그, 1990 207–220.

외부 링크