부흐베르거 알고리즘

계산 대수 기하학 및 계산 정류 대수학에서 Buchberger의 알고리즘은 다항적 이상에 대한 주어진 생성기 집합을 어떤 단항적 순서에 관한 Gröbner 기준으로 변환하는 방법이다.오스트리아의 수학자 브루노 부흐베르거에 의해 발명되었다.일변량 GCD 연산을 위한 유클리드 알고리즘의 일반화와 선형 시스템을 위한 가우스 소거로 볼 수 있다.

알고리즘.

다항식 링 R의 이상적인 I에 대한 근거를 찾기 위한 이 알고리즘의 조잡한 버전은 다음과 같이 진행된다.

I를 생성하는 다항식 F 집합 입력

출력 A Gröbner basis G for I

G :=F
모든 f_i, G에서 f는_j 주어진 순서와 관련하여 g의_i_i 선행 조건 및 g와_i g의_j 최소_ij 공통 배수를 나타낸다.
G에서_ij 두 개의 다항식을 선택하고 S = (a_ij_i / g) f_i - (a_ij / g_j) f_j(여기 있는 선행 조건은 시공에 의해 취소됨)로 두십시오.
결과가 더 이상 축소할 수 없을 때까지 설정된 G에 상대적인 다변량 분할 알고리즘을 사용하여_ij S를 감소시킨다.결과가 0이 아닌 경우 G에 추가한다.
4단계에 추가된 새로운 다항식을 포함하여 가능한 모든 쌍이 고려될 때까지 2-4단계를 반복하십시오.
출력 G

다항식 S는_ij 일반적으로 S-폴리놈(S-pollynomial)이라고 하며, 여기서 S는 감산(Buchberger)이나 시지(기타)를 가리킨다.연관된 다항식 쌍을 보통 임계 쌍이라고 한다.

위에서 말한 것 이상으로 이 알고리즘을 개선할 수 있는 방법은 수없이 많다.예를 들어 F의 모든 새로운 요소를 추가하기 전에 서로 상대적으로 줄일 수 있다.f와_i f의_j 선행 항이 공통 변수를 공유하지 않으면 S는_ij 항상 0으로 감소하므로(축소를 위해 f와_i f만_j 사용하는 경우) 전혀 계산할 필요가 없다.

알고리즘은 우리 세트 F의 선도적인 용어에 의해 생성되는 단일한 이상형의 크기를 지속적으로 증가시키고 있기 때문에 종료되며, 딕슨의 보조정리(혹은 힐버트 기본 정리)는 그러한 어떤 상승 체인이 결국 일정해져야 한다는 것을 보증한다.

복잡성

Buchberger 알고리즘의 계산 복잡성은 계산 시간을 획기적으로 바꿀 수 있는 선택 수 때문에 추정하기가 매우 어렵다.그럼에도 불구하고 T. W. 두베는 그뢰브너(Gröbner)의 감소된 원소의 정도가 항상 경계한다는 것을 증명했다^[1].

2\left({\frac {d^{2}}{2}}+d\right)^{2^{n-2}}

(

2\left({\frac {d^{2}}{2}}+d\right)^{2^{n-2}}

2\left({\frac {d^{2}}{2}}+d\right)^{2^{n-2}}

+ d

2\left({\frac {d^{2}}{2}}+d\right)^{2^{n-2}}

)

2\left({\frac {d^{2}}{2}}+d\right)^{2^{n-2}}

2\left({\frac {d^{2}}{2}}+d\right)^{2^{n-2}}

-

2\left({\frac {d^{2}}{2}}+d\right)^{2^{n-2}}

{\

여기서 $n$ 은 변수의 수 및 d $입력$ 다항식의 최대 총도.이것은 이론적으로 복잡성 $d^{2^{n+o(1)}}$ $d^{2^{n+o(1)}}$ + $d^{2^{n+o(1)}}$ ( $){\$ d $^{2^{n+o(1)}$ 의 알고리즘을 얻기 위해, 이 값으로 경계된 다항식의 벡터 공간 위에 선형대수를 사용할 수 있게 한다 $d^{2^{n+o(1)}}$

한편, 그뢰브너 바탕에 정도 요소가 포함되어 있는 예도^[2] 있다.

d^{2^{\Omega (n)}}

d^{2^{\Omega (n)}}

)

{\

그리고 위의 복잡성 상한이 최적이다.그럼에도 불구하고 그러한 예는 극히 드물다.

그것의 발견 이후, 많은 종류의 부흐버거가 그것의 효율성을 향상시키기 위해 도입되었다.Faugere의 F4와 F5 알고리즘은 현재 Gröbner 베이스를 계산하는 데 가장 효율적인 알고리즘이며, 각각 수백 개의 항과 계수를 수백 개의 숫자로 이루어진 수백 개의 다항식으로 구성된 Gröbner 베이스를 일상적으로 계산할 수 있다.

참고 항목

크누스-벤딕스 완성 알고리즘
Quine-McCluskey 알고리즘 - 부울 대수에 대한 유사 알고리즘

참조

^ Dubé, Thomas W. (1990). "The Structure of Polynomial Ideals and Gröbner Bases". SIAM Journal on Computing. 19 (4): 750. doi:10.1137/0219053.
^ Mayr, Ernst W; Meyer, Albert R (1982). "The complexity of the word problems for commutative semigroups and polynomial ideals". Advances in Mathematics. 46 (3): 305. doi:10.1016/0001-8708(82)90048-2.

추가 읽기

Buchberger, B. (August 1976). "Theoretical Basis for the Reduction of Polynomials to Canonical Forms". ACM SIGSAM Bulletin. ACM. 10 (3): 19–29. doi:10.1145/1088216.1088219. MR 0463136.
데이비드 콕스, 존 리틀, 도널드 오셔(1997년).이상, 다양성 및 알고리즘: 계산대수 기하학과 정류대수학, 스프링거에 대한 소개ISBN 0-387-94680-2.
블라디미르 P.게르트, 유리 A.블링코프(1998년).시뮬레이션에서 다항식 이상, 수학 및 컴퓨터의 비자발적 기반, 45:519ff

외부 링크

"Buchberger algorithm", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
Scholarpedia에 관한 Buchberger 알고리즘
Weisstein, Eric W. "Buchberger's Algorithm". MathWorld.

[1] Dubé, Thomas W. (1990). "The Structure of Polynomial Ideals and Gröbner Bases". SIAM Journal on Computing. 19 (4): 750. doi:10.1137/0219053.

[2] Mayr, Ernst W; Meyer, Albert R (1982). "The complexity of the word problems for commutative semigroups and polynomial ideals". Advances in Mathematics. 46 (3): 305. doi:10.1016/0001-8708(82)90048-2.

[1]

[2]

Search

부흐베르거 알고리즘

네임스페이스

더

목차

알고리즘.

복잡성

참고 항목

참조

추가 읽기

외부 링크