Polynomial decomposition

Original article: w:Polynomial decomposition

수학(mathematics)에서, 다항식 분해(polynomial decomposition)는 다항식(polynomial) g과 h의 함수형 합성(functional composition) $g\circ h$으로 다항식 f를 표현하며, 여기서 g와 h가 1보다 큰 차수(degree)를 가집니다; 그것은 대수적 함수형 분해(functional decomposition)입니다. 알고리듬(algorithms)은 다항식 시간(polynomial time)에서 일변수 다항식(univariate polynomial)을 분해하는 것으로 알려져 있습니다.

이런 방법에서 분해-가능한 다항식은 합성 다항식(composite polynomials)입니다; 그렇지 않은 것은 비-분해가능 다항식(indecomposable polynomials) 또는 때때로 소수 다항식(prime polynomials)입니다 (다항식의 곱으로 인수화될 수 없는, 기약 다항식(irreducible polynomial)과 혼동해서는 안됩니다).

이 기사의 나머지 부분에서는 오직 일변수 다항식을 논의합니다; 알고리듬은 역시 임의적인 차수의 다변수 다항식에도 존재합니다.

Examples

가장 간단한 경우에서, 다항식 중 하나는 단항식(monomial)입니다. 예를 들어, 다음은

$f=x^{6}-3x^{3}+1$

다음으로 분해됩니다:

$g=x^{2}-3x+1{\text{ and }}h=x^{3}$

왜냐하면

$f(x)=(g\circ h)(x)=g(h(x))=g(x^{3})=(x^{3})^{2}-3(x^{3})+1,$

여기서 링 연산자 기호 ∘를 함수 합성(function composition)을 나타내기 위해 사용합니다.

덜 자명하게,

${\begin{aligned}&x^{6}-6x^{5}+21x^{4}-44x^{3}+68x^{2}-64x+41\\={}&(x^{3}+9x^{2}+32x+41)\circ (x^{2}-2x).\end{aligned}}$

Uniqueness

다항식은 비-분해가능 다항식으로의 구별되는 분해를 가질 수 있으며 여기서 $f=g_{1}\circ g_{2}\circ \cdots \circ g_{m}=h_{1}\circ h_{2}\circ \cdots \circ h_{n}$이고 일부 $i$에 대해 $g_{i}\neq h_{i}$입니다. 일보다 큰 차수의 다항식에 대한 그 정의에서 제한은 선형 다항식으로 가능한 무한하게 많은 분해를 배제합니다.

조세프 릿(Joseph Ritt)은 $m=n$이고, 성분의 차수가 선형 변환까지 같지만, 순서는 다를 수 있음을 입증했습니다; 이것이 릿의 다항식 분해 정리(Ritt's polynomial decomposition theorem)입니다. 예를 들어, $x^{2}\circ x^{3}=x^{3}\circ x^{2}$.

Applications

다항식 분해는 다항식을 보다 효율적으로 평가할 수 있습니다. 예를 들어, 다음은

${\begin{aligned}&x^{8}+4x^{7}+10x^{6}+16x^{5}+19x^{4}+16x^{3}+10x^{2}+4x-1\\={}&\left(x^{2}-2\right)\circ \left(x^{2}\right)\circ \left(x^{2}+x+1\right)\end{aligned}}$

분해를 사용하여 오직 셋의 곱셈으로 계산될 수 있지만, 호너의 방법(Horner's method)은 7을 요구할 것입니다.

다항식 분해는 심지어 일부 기약 다항식(irreducible polynomial)에 대해 제곱근(radicals)을 사용하여 기호적 근의 계산을 활성화합니다. 이 기술은 많은 컴퓨터 대수학 시스템(computer algebra systems)에서 사용됩니다. 예를 들어, 분해를 사용하여

${\begin{aligned}&x^{6}-6x^{5}+15x^{4}-20x^{3}+15x^{2}-6x-1\\={}&\left(x^{3}-2\right)\circ \left(x^{2}-2x+1\right),\end{aligned}}$

이 기약 다항식의 근은 다음으로 계산될 수 있습니다:

$1\pm 2^{1/6},1\pm {\frac {\sqrt {-1\pm {\sqrt {3}}i}}{2^{1/3}}}.$

심지어 사차 다항식(quartic polynomial)의 경우에서, 여기서 근에 대해 분명한 공식이 있으며, 분해를 사용하여 푸는 것은 더 단순한 형식을 제공합니다. 예를 들어, 다음 분해는

${\begin{aligned}&x^{4}-8x^{3}+18x^{2}-8x+2\\={}&(x^{2}+1)\circ (x^{2}-4x+1)\end{aligned}}$

다음 근을 제공합니다:

$2\pm {\sqrt {3\pm i}}$

그러나 사차 공식(quartic formula)의 직접 적용은 동등한 결과를 제공하지만 단순화하기 어렵고 이해하기 어려운 형식으로 나타납니다:

$2-{\frac {\sqrt {{9\left({\frac {8{\sqrt {10}}i}{3^{3/2}}}+72\right)^{2/3}+36\left({\frac {8{\sqrt {10}}i}{3^{3/2}}}+72\right)^{1/3}+156} \over {\left({\frac {8{\sqrt {10}}i}{3^{3/2}}}+72\right)^{1/3}}}}{6}}-{{\sqrt {-\left({\frac {8{\sqrt {10}}i}{3^{3/2}}}+72\right)^{1/3}-{{52} \over {3\left({\frac {8{\sqrt {10}}i}{3^{3/2}}}+72\right)^{1/3}}}+8}} \over 2}.$

Algorithms

다항식 분해를 위한 첫 번째 알고리듬은 1985년에 발표되었지만, 그것은 1976년에 발견되었고, Macsyma/Maxima 컴퓨터 대수 시스템(computer algebra system)에서 구현되었습니다. 해당 알고리듬은 최악의 경우 기하급수적인 시간이 걸리지만, 놓여있는 필드(field)의 특성(characteristic)과 독립적으로 작동합니다.

1989년 알고리듬은 다항식 시간으로 실행되지만 특성에 제한이 있습니다.

2014 알고리듬은 특성에 대한 제한없이 다항식 시간에서 분해를 계산합니다.

References

• Joel S. Cohen (2003). "Chapter 5. Polynomial Decomposition". Computer Algebra and Symbolic Computation. ISBN 1-56881-159-4.