System of polynomial equations

Original article: w:System of polynomial equations

다항 방정식의 시스템 (때때로 간단히 다항 시스템)은 연립 방정식(simultaneous equations) f₁ = 0, ..., f_h = 0의 집합이며 여기서 f_i는 여러 변수에서 다항식(polynomial), 말하자면 어떤 필드(field) k에 걸쳐 x₁, ..., x_n입니다.

다항 시스템의 해는 k의 어떤 대수적으로 닫힌(algebraically closed) 필드 확장(field extension) K에 속하고, 모든 방정식을 참으로 만드는 x_i에 대해 값의 집합입니다. k가 유리수(rational number)의 필드일 때, K는 일반적으로 복소수(complex number)의 필드인 것으로 가정하는데, 왜냐하면 각 해는 k의 필드 확장(field extension)에 속하며, 이것은 복소수의 부분-필드와 동형입니다.

이 기사는 푸는, 즉 모든 해를 찾거나 해를 설명하는 방법에 대한 것입니다. 이들 방법은 컴퓨터에서 구현되도록 설계되었기 때문에, 계산 (상등 테스트 포함)이 쉽고 효율적인 필드 k, 즉 유리수(rational number) 및 유한 필드(finite field)에서 주어짐을 강조합니다.

특정 집합에 속하는 해를 찾는 것은 일반적으로 훨씬 더 어려운 문제이고, 주어진 유한 필드의 해의 경우를 제외하고는 이 문서의 범위를 벗어납니다. 모든 성분이 정수 또는 유리수인 해의 경우에 대해, 디오판토스 방정식(Diophantine equation)을 참조하십시오.

Definition

The numerous singular points of the Barth sextic are the solutions of a polynomial system

다항 방정식의 시스템의 가장 간단한 예제는 다음입니다:

${\begin{aligned}x^{2}-1&=0\\y^{2}-4&=0.\end{aligned}}$

그것의 해는 네 쌍 (x,y) = (1, 2), (−1, 2), (1, −2), (−1, −2)입니다.

이 기사의 주제는 이 예제의 일반화의 연구와 해를 계산하는 것에 사용되는 방법의 설명입니다.

다항 방정식의 시스템, 또는 다항 시스템은 다음 방정식의 모음입니다:

${\begin{aligned}f_{1}\left(x_{1},...,x_{m}\right)&=0\\\vdots \\f_{n}\left(x_{1},...,x_{m}\right)&=0,\end{aligned}}$

여기서 각 f_h는 정수 계수, 또는 어떤 고정된 필드(field), 종종 유리수(rational number)의 필드 또는 유한 필드(finite field)에서 계수를 갖는 불확정수(indeterminates)에서 다항식(polynomial)입니다. 실수(real number)와 같은 계수의 다른 필드는 덜 종종 사용되는데, 왜냐하면 그것들의 원소는 컴퓨터에서 표현될 수 없기 때문입니다 (오직 실수의 근사가 계산에서 사용될 수 있고, 이들 근사는 항상 유리수입니다).

다항 시스템의 해는 모든 다항 시스템의 방정식을 만족시키는 (x₁, ..., x_m)의 값의 튜플(tuple)입니다. 해는 복소수(complex number), 또는 보다 일반적으로 계수를 포함하는 대수적으로 닫힌 필드(algebraically closed field)에서 찾아집니다. 특히, 특성 영(characteristic zero)에서, 모든 복소(complex) 해가 찾아집니다. 실수(real) 또는 유리수(rational) 해를 찾는 것은 이 기사에서 고려하지 않는 훨씬 더 어려운 문제입니다.

해의 집합은 항상 유한하지는 않습니다; 예를 들어, 다음 시스템의 해는

${\begin{aligned}x(x-1)&=0\\x(y-1)&=0\end{aligned}}$

점 (x,y) = (1,1)이고 직선 x = 0입니다. 심지어 해 집합이 유한일 때, 일반적으로 행의 닫힌-형식 표현(closed-form expression)이 없습니다 (단일 방정식의 경우에서, 이것은 아벨–루피니 정리(Abel–Ruffini theorem)입니다).

그림에 표시된 바르트 표면(Barth surface)은 3개의 변수에서 차수 6의 단일 방정식으로 축소된 다항 시스템의 해의 기하학적 표현입니다. 수많은 특이 점(singular points) 중 일부가 이미지에 시각적으로 표시됩니다. 그것들은 3 변수에서 차수 5의 4 방정식의 시스템의 해입니다. 그러한 초과-결정된 시스템은 일반적으로 해를 가지지 않습니다 (즉, 만약 계수가 구체적이지 않으면). 만약 그것이 유한 개수의 해를 가지면, 이 숫자는 베주의 정리(Bézout's theorem)에 의해 많아야 5³ = 125입니다. 어쨌든, 차수 6의 표면의 특이 점의 경우에 대해, 최대 해의 숫자는 65이고, 바르트 표면에 도달되는 것으로 나타났습니다.

Basic properties and definitions

시스템은 만약 방정식의 숫자가 변수의 숫자보다 높으면 초과-결정된(overdetermined) 것입니다. 시스템은 만약 그것이 복소(complex) 해를 가지지 않으면 (또는, 만약 계수들이 복소수가 아니고, 계수를 포함하는 대수적으로 닫힌 필드(algebraically closed field)에서 해가 없으면) 불일치(inconsistent)입니다. 힐베르트 영점-정리(Hilbert's Nullstellensatz)에 의해, 이것은 1이 방정식의 첫 번째 구성원의 (계수로 다항식을 갖는) 선형 조합(linear combination)임을 의미합니다. 무작위 계수로 구성될 때, 대부분이지만 모두는 아닌 과도-결정된 시스템은 불일치입니다. 예를 들어, 시스템 x³ – 1 = 0, x² – 1 = 0은 (두 방정식이지만 오직 하나의 미지수를 가지는) 초과-결정된 것이지만, 그것은 불일치가 아닌데 왜냐하면 그것은 해 x = 1를 가지기 때문입니다.

시스템은 만약 방정식의 숫자가 변수의 숫자보다 낮으면 미달-결정된(underdetermined) 것입니다. 미달-결정된 시스템은 불일치 또는 무한하게 많은 복소 해 (또는 방정식의 계수를 포함하는 대수적으로 닫힌 필드(algebraically closed field)에서 해) 중 하나입니다. 이것은 특히 힐베르트 영점-정리(Hilbert's Nullstellensatz) 및 크룰의 주요 아이디얼 정리(Krull's principal ideal theorem)를 포함하는 교환 대수(commutative algebra)의 비-자명한 결과입니다.

시스템은 만약 그것이 유한 숫자의 복소 해 (또는 대수적으로 닫힌 필드에서 해)를 가지면 영-차원(zero-dimensional)입니다. 이 용어는 해의 대수적 다양체(algebraic variety)가 차원(dimension) 영을 가지는 사실에서 옵니다. 무한하게 많은 해를 갖는 시스템은 양의-차원이라고 말합니다.

변수만큼 많은 방정식을 갖는 영-차원 시스템은 때때로 잘-행동된(well-behaved) 것이라고 말합니다. 베주의 정리(Bézout's theorem)는 그것의 방정식의 차수 d₁, ..., d_n인 잘-행동된 시스템은 많아야 d₁⋅⋅⋅d_n 해를 갖는다고 주장합니다. 이 경계는 날카롭습니다. 만약 모든 차수가 d와 같으면, 이 경계는 dⁿ이 되고 변수의 숫자에서 지수입니다. (대수학의 기본 정리(fundamental theorem of algebra)는 특별한 경우 n = 1입니다.)

이 지수 행동은 다항 시스템을 풀기 어렵게 만들고 베주의 경계가, 말하자면 25보다 높은 시스템을 자동으로 풀 수 있는 솔버가 거의 없는 이유를 설명합니다 (차수 3의 세 방정식 또는 차수 2의 다섯 방정식이 이 경계를 벗어납니다).

What is solving?

다항식 시스템을 푸는 것을 행하기 위한 첫 번째 일은 그것이 불일치, 영-차원 또는 양의 차원인지 여부를 결정하는 것입니다. 이것은 방정식의 왼쪽 변의 그뢰브너 기저(Gröbner basis)를 계산함으로써 행해질 수 있습니다. 시스템은 만약 이 그뢰브너 기저가 1로 줄어들면 불일치입니다. 시스템이 만약, 모든 각 변수에 대해 이 변수의 순수한 거듭제곱인 그뢰브너 기저의 일부 요소의 선행하는 단항식(leading monomial)이 있으면 영-차원입니다. 이 테스트에 대해, 가장 좋은 단항식 순서(monomial order) (즉, 일반적으로 가장 빠른 계산으로 이어지는 순서)는 보통 등급화된 역 사전-편집식(graded reverse lexicographic) 순서 (grevlex)입니다.

만약 시스템이 양의-차원이면, 그것은 무한하게 많은 해를 가집니다. 따라서 그것들을 열거하는 것이 가능하지 않습니다. 이 경우에서, 푸는 것은 오직 "해의 관련 속성이 쉽게 추출될 수 것으로부터 해의 설명을 찾는 것"을 의미할 수 있습니다. 공통적으로 허용되는 그러한 설명이 있지 않습니다. 사실, 대수적 기하학(algebraic geometry)의 거의 모든 각 부분분야를 포함하는 많은 다른 "관련 속성"이 있습니다.

양의 차원 시스템과 관련하여 그러한 질문의 자연스러운 예제는 다음입니다: 만약 유리수에 걸쳐 다항식 시스템이 유한한 숫자의 실수 해를 가지면 결정하고 그것들을 계산하십시오. 이 질문의 일반화는 다항식 시스템의 실수 해 집합의 각 연결된 성분(connected component)에서 적어도 하나의 해를 찾는 것입니다. 이들 문제를 푸는 것에 대해 고전적인 알고리듬은 원통형 대수적 분해(cylindrical algebraic decomposition)이며, 이것은 이중으로 지수(doubly exponential) 계산적 복잡도(computational complexity)를 가지고 따라서 매우 작은 예제를 제외하고는 실제에서 사용될 수 없습니다.

영-차원 시스템에 대해, 푸는 것은 모든 해를 계산하는 것으로 구성됩니다. 해를 출력하는 다른 두 방법이 있습니다. 가장 공통적인 방법은 실수 또는 복소 해에 대해 가능하고, 해의 숫자 근사를 출력하는 것으로 구성됩니다. 그러한 해는 수치적(numeric)이라고 불립니다. 해가 만약 근사의 오차에 대한 경계가 제공되고, 만약 이 경계가 다른 해를 분리하면 인증됩니다.

해를 나타내는 나머지 다른 방법은 대수적(algebraic)이라고 말합니다. 그것은 영-차원 시스템에 대해, 해가 시스템의 계수의 필드 k의 대수적 클로저(algebraic closure)에 속한다는 사실을 사용합니다. 아래에서 논의되는, 대수적 클로저에서 해를 표현하기 위한 여러 방법이 있습니다. 그것들의 모두는 하나 또는 여러 일변수 방정식을 풂으로써 해의 수치적 근사를 계산하는 것을 허용합니다. 이 계산에 대해, 해 당 오직 하나의 일변수 다항식을 푸는 것을 포함하는 표현을 사용하는 것이 선호되는데, 왜냐하면 근사 계수를 가지는 다항식의 근을 계산하는 것은 매우 불안정한 문제이기 때문입니다.

Extensions

Trigonometric equations

삼각 방정식은 g가 삼각 다항식(trigonometric polynomial)인 방정식 g = 0입니다. 그러한 방정식은 그것에서 (합과 차 공식(sum and difference formulas)을 사용하여) 사인과 코사인을 확장하고, sin(x)과 cos(x)을 두 새로운 변수 s와 c로 대체하고 새로운 방정식 s² + c² – 1 = 0을 더함으로써 다항 시스템으로 변환될 수 있습니다.

예를 들어, 다음 항등식때문에:

$\cos(3x)=4\cos ^{3}(x)-3\cos(x),$

다음 방정식을 푸는 것은

$\sin ^{3}(x)+\cos(3x)=0$

다음 다항 시스템을 푸는 것과 동등합니다:

${\begin{cases}s^{3}+4c^{3}-3c&=0\\s^{2}+c^{2}-1&=0.\end{cases}}$

이 시스템의 각 해 (c₀, s₀)에 대해, 0 ≤ x < 2π을 만족하는 방정식의 고유한 해 x가 있습니다.

이 간단한 예제의 경우에서, 시스템이 방정식보다 풀기 쉬운지 여부가 명확하지 않을 수 있습니다. 더 복잡한 예제에서, 우리는 방정식을 직접 풀기 위한 체계적인 방법이 부족하지만, 소프트웨어는 해당 시스템을 자동으로 풀기 위해 이용될 수 있습니다.

Solutions in a finite field

q 원소를 갖는 유한 필드 k에 걸쳐 시스템을 풀 때, 우리는 주로 k에서 해에 관심을 가집니다. k의 원소가 정확히 방정식 x^q – x = 0의 해이므로, 해를 k로 제한하는 것에 대해 각 변수 x_i에 대해 방정식 x_i^q – x_i = 0를 더하는 것으로 충분합니다.

Coefficients in a number field or in a finite field with non-prime order

대수적 숫자 필드(algebraic number field)의 원소는 보통 일부 일변수 다항식을 만족시키는 필드의 생성기에서 다항식으로 표현됩니다. 그것의 계수가 숫자 필드에 속하는 다항식 시스템으로 작업하기 위해, 이 생성기를 새로운 변수로 여기고 생성기의 방정식을 시스템의 방정식에 더하는 것으로 충분합니다. 따라서 숫자 필드에 걸쳐 다항식 시스템을 푸는 것은 유리수에 걸쳐 또 다른 시스템을 푸는 것으로 줄어듭니다.

예르 들어, 만약 시스템이 ${\sqrt {2}}$를 포함하면, 유리수에 걸쳐 시스템은 방정식 r₂² – 2 = 0을 더하고 다른 방정식에서 ${\sqrt {2}}$을 r₂으로 대체함으로써 얻습니다.

유한 필드의 경우에서, 같은 변환은 필드 k가 소수 순서를 가짐을 항상 지원하는 것을 허용합니다.

Algebraic representation of the solutions

Regular chains

Main article: Regular chain

해를 나타내는 보통 방법은 영-차원 정규 체인을 통한 것입니다. 그러한 체인은 1 ≤ i ≤ n을 만족하는 모든 각 i에 대해 다음을 만족하는 일련의 다항식 f₁(x₁), f₂(x₁, x₂), ..., f_n(x₁, ..., x_n)으로 구성됩니다:

• f_i는 오직 x_i에서 차수 d_i > 0를 가지는 x₁, ..., x_i에서 방정식입니다;
• f_i에서 x_i^d_i의 계수는 f₁, ..., f_{i − 1}와 함께 임의의 공통 영을 가지지 않는 x₁, ..., x_{i −1} 에서 다항식입니다.

그러한 정규 체인(regular chain)은 다음 삼각 방정식의 시스템과 결합됩니다:

${\begin{cases}f_{1}(x_{1})=0\\f_{2}(x_{1},x_{2})=0\\\quad \vdots \\f_{n}(x_{1},x_{2},\ldots ,x_{n})=0.\end{cases}}$

이 시스템의 해는 첫 번째 일변수 방정식을 풀고, 나머지 방정식에서 해를 대체하고, 그런-다음 이제 일변수인 두 번째 방정식을 풀고, 이런 식으로 계속 풂으로써 얻습니다. 정규 체인의 정의는 f_i로부터 구해진 일변수 방정식이 차수 d_i를 가지고 따라서 그 시스템이 d₁ ... d_n 해를 갖는다는 것을 의미하며, 이 해결 과정에서 중복 근이 없다는 조건 아래에서 제공됩니다 (대수학의 기본 정리(fundamental theorem of algebra)).

모든 각 영-차원 다항 방정식의 시스템은 정규 체인의 유한 숫자와 동등합니다 (즉, 같은 해를 가집니다). 여러 정규 체인은 요구될 수 있는데, 그것은 세 해를 가지는 다음 시스템에 대한 경우이기 때문입니다.

${\begin{cases}x^{2}-1=0\\(x-1)(y-1)=0\\y^{2}-1=0.\end{cases}}$

임의의 다항식 시스템 (반드시 영-차원일 필요는 없음)의 삼각 분해(triangular decomposition)를 정규 체인(regular chain) (또는 정규 반-대수 시스템(regular semi-algebraic system))으로 계산하는 여러 알고리듬이 있습니다.

영-차원 경우에 특화되고, 이 경우에서, 직접 알고리듬과 경쟁하는 역시 알고리듬이 있습니다. 그것은 먼저 등급화된 역 사전식 순서(graded reverse lexicographic order, 줄여서 grevlex)에 대한 그뢰브너 기저(Gröbner basis)를 계산하고, 그런-다음 FGLM 알고리듬에 의한 사전식 그뢰브너 기저를 추론하고, 마지막으로 Lextriangular 알고리듬을 적용하는 것으로 구성됩니다.

그 해의 표현은 유한 필드에서 계수에 대해 완전히 편리합니다. 어쨌든, 유리 계수에 대해, 두 가지 관점이 고려되어야 합니다:

• 출력은 계산과 문제가 되는 결과의 사용을 만들 수 있는 거대한 정수를 포함할 수 있습니다.
• 출력으로부터 해의 수치적 값을 추론하기 위해, 우리는 근사 계수를 갖는 일변수 다항식을 풀어야 하며, 이것은 매우 불안정한 문제입니다.

첫 번째 문제는 다앙(Dahan)과 쇼스트(Schost)에 의해 해결되었습니다: 주어진 해의 집합을 나타내는 정규 체인의 집합 중에서, 입력 시스템의 크기의 관점에서 계수가 명시적으로 경계져 있는 집합이 있으며, 거의 최적의 경계를 가집니다. 동등한-투영가능 분해(equiprojectable decomposition)라고 불리는 이 집합은 오직 좌표 선택에 의존합니다. 이것은 동등한-투영가능 분해를 효율적으로 계산하기 위한 모듈러 방법(modular methods)의 사용을 허용합니다.

두 번째 문제는, 때때로 모양 보조정리(shape lemma)라고 불리며, 모든 d_i이지만 첫 번째 하나는 1과 같은, 특수한 형식의 정규 체인을 출력함으로써 일반적으로 해결됩니다. 그러한 정규 체인을 얻는 것에 대해, 우리는 분리하는 변수(separating variable)라고 불리는 인덱스 0으로 주어지는 그 이상의 변수를 더해야 할 수 있습니다. 아래에 설명된, 유리 일변수 표현(rational univariate representation)은 정규 체인 또는 그뢰브너 기저에서 시작함으로써, 다앙–쇼스트 경계를 만족시키는, 그러한 특수한 정규 체인을 계산하는 것을 허용합니다.

Rational univariate representation

유리 일변수 표현 또는 RUR은 F. Rouillier에 의해 도입되어 온 유리수에 걸쳐 영-차원 다항식 시스템의 해의 표현입니다.

영-차원 시스템의 RUR은 분리하는 변수라고 불리는 변수 x₀의 선형 조합과 다음 방정식의 시스템으로 구성됩니다:

${\begin{cases}h(x_{0})=0\\x_{1}=g_{1}(x_{0})/g_{0}(x_{0})\\\quad \vdots \\x_{n}=g_{n}(x_{0})/g_{0}(x_{0}),\end{cases}}$

여기서 h는 차수 D의 x₀에서 일변수 다항식이고 g₀, ..., g_n는 D보다 작은 차수의 x₀에서 일변수 다항식입니다.

유리수에 걸쳐 영-차원 다항식 시스템이 주어지면, RUR은 다음 속성을 가집니다.

• 변수의 전부이지만 유한 숫자 선형 조합은 분리하는 변수입니다.
• 분리하는 변수가 선택될 때, RUR은 존재하고 고유합니다. 특히 h와 g_i는 그것들을 계산하기 위한 임의의 알고리듬과 독립적으로 정의됩니다.
• 시스템의 해는 h의 근과 일-대-일 대응이고 h의 각 근의 중복도(multiplicity)는 대응하는 해의 중복도와 같습니다.
• 시스템의 해는 h의 근을 나머지 방정식에 대입함으로써 얻습니다.
• 만약 h가 임의의 중복 근을 가지지 않으면 g₀는 h의 도함수(derivative)입니다.

예를 들어, 이전 섹션에서 시스템에 대해, x, y 및 x + y의 중복을 제외하고 변수의 모든 각 선형 조합은 분리하는 변수입니다. 만약 우리가 분리하는 변수로 t = x – y/2를 선택하면, RUR은 다음입니다:

${\begin{cases}t^{3}-t=0\\x={\frac {t^{2}+2t-1}{3t^{2}-1}}\\y={\frac {t^{2}-2t-1}{3t^{2}-1}}.\\\end{cases}}$

RUR은 임의의 알고리듬과 독립적으로 주어진 분리하는 변수에 대해 고유하게 정의되고, 그것은 근의 중복도를 보존합니다. 이것은, 일반적으로, 중복도를 보존하지 않는 삼각 분해 (심지어 동등한-투영가능 분해)와의 현저한 차이입니다. RUR은 상대적으로 작은 크기의 계수로 출력을 생성하는 속성을 동등한-투영가능 분해와 공유합니다.

영-차원 시스템에 대해, RUR은 단일 일변수 다항식을 풀고 그것을 유리 함수로 대체함으로써 해의 수치적 값의 검색을 허용합니다. 이것은 임의의 주어진 정밀도에 대한 해의 인증된 근사의 생산을 허용합니다.

게다가, RUR의 일변수 다항식 h(x₀)는 인수화될 수 있고, 이것은 모든 각 기약 인수에 대해 RUR을 제공합니다. 이것은 주어진 아이디얼의 소수 분해(prime decomposition)를 제공합니다 (즉, 아이디얼의 제곱근(radical)의 으뜸 분해(primary decomposition)를 제공합니다). 실제에서, 이것은 특히 높은 중복도를 갖는 시스템의 경우에서 훨씬 더 작은 계수를 갖는 출력을 제공합니다.

삼각 분해와 동등한-투영가능 분해와는 반대로, RUR은 양의 차원에서 정의되지 않습니다.

Solving numerically

General solving algorithms

임의의 비선형 방정식의 시스템(system of nonlinear equations)에 대해 설계된 일반적인 수치적 알고리듬은 역시 다항식 시스템에 대해 작동합니다. 어쨌든 특정 방법이 일반적으로 선호되는데, 왜냐하면 일반적인 방법은 보통 모든 해를 찾는 것을 허용하지 않기 때문입니다. 특히, 일반적인 방법이 임의의 해를 찾지 못하면, 이것은 보통 해가 없음을 나타내는 것이 아닙니다.

그럼에도 불구하고, 두 방법이 여기서 언급될 가치가 있습니다.

• 뉴턴의 방법(Newton's method)은 만약 방정식의 개수가 변수의 개수와 같으면 사용될 수 있습니다. 그것은 모든 해를 찾는 것을 허용하지 않고 해가 없음을 입증하는 것을 허용하지 않습니다. 다른 알려진 방법과 함께 그러나 그것은 해에 가까운 점으로부터 시작할 때 매우 빠릅니다. 그러므로, 그것은 아래에서 설명된 호모토피 연속 방법에 대해 기본 도구입니다.
• 최적화(Optimization)는 다항식 시스템을 푸는 데 드물게 사용되지만, 1970년 경에, 56개의 변수에서 81개의 이차 방정식의 시스템이 불일치가 아님을 보여주는 데 성공했습니다. 다른 알려진 방법과 함께 이것은 현대 기술의 가능성을 뛰어넘습니다. 이 방법은 단순히 방정식의 제곱의 합을 최소화하는 것으로 구성됩니다. 만약 영이 지역적 최솟값으로 발견되면, 그것이 해에서 달성됩니다. 이 방법은 초과-결정된 시스템에서 작동하지만, 만약 발견된 모든 지역적 최솟값이 양수이면 빈 정보를 출력합니다.

Homotopy continuation method

Main article: Homotopy continuation

이것은 방정식의 숫자가 변수의 숫자와 같다고 가정하는 반-수치적 방법입니다. 이 방법은 비교적 오래되었지만 지난 수십 년 동안 극적으로 개선되었습니다.

이 방법은 세 단계로 나뉩니다. 먼저 해의 숫자의 위쪽 경계가 계산됩니다. 이 경계는 가능한 한 뚜렷해야 합니다. 그러므로, 그것은, 적어도, 네 다른 방법으로 계산되고 최적의 값, 말하자면 $N$이 유지됩니다.

두 번째 단계에서, 다항 방정식의 시스템 $g_{1}=0,\,\ldots ,\,g_{n}=0$이 계산하기 쉬운 정확히 $N$를 가지는 것으로 생성됩니다. 이 새로운 시스템은 변수의 같은 숫자 $n$과 방정식의 같은 숫자 $n$과 풀기 위한 시스템, $f_{1}=0,\,\ldots ,\,f_{n}=0$과 같은 일반적인 구조를 가집니다.

그런-다음 두 시스템 사이의 호모토피(homotopy)가 고려됩니다. 그것은, 예를 들어, 두 시스템 사이의 직선으로 구성지만, 다른 경로가, 특히 다음 시스템에서, 일부 특이점을 피하기 위해 고려될 수 있습니다:

$(1-t)g_{1}+tf_{1}=0,\,\ldots ,\,(1-t)g_{n}+tf_{n}=0$.

호모토피 연속은 매개변수 $t$를 0에서 1로 변형하고 이 변형 동안 $N$ 해를 따르는 것으로 구성됩니다. 이것은 $t=1$에 대해 원했던 해를 제공합니다. 따르는 것은 만약 $t_{1}<t_{2}$이면, $t=t_{2}$에 대해 해가 뉴턴의 방법에 의해 $t=t_{1}$에 대해 해로부터 추론될 수 있음을 의미합니다. 여기서 어려운 점은 $t_{2}-t_{1}$의 값을 잘 선택하는 것입니다: 너무 크면, 뉴턴의 수렴이 느릴 수 있고 심지어 해 경로로부터 또 다른 해로의 뛰어넘을 수 있습니다. 너무 작고, 단계의 숫자가 많으면 방법을 늦춥니다.

Numerically solving from the rational univariate representation

RUR로부터 해의 수치적 값을 추론하는 것은 쉬운 것처럼 보입니다: 그것은 일변수 다항식의 근을 계산하고 그것들을 나머지 다른 방정식에 대입하는 것으로 충분합니다. 이것은 그렇게 쉽지 않은데 왜냐하면 또 다른 다항식의 근에서 다항식의 평가가 매우 불안정하기 때문입니다.

일변수 다항식의 근은 따라서 모두에 대해 한 번만 정의될 수 없는 높은 정밀도로 계산되어야 합니다. 이 요구조건을 만족시키는 두 가지 알고리듬이 있습니다.

• 아베스 방법(Aberth method)은 MPSolve에서 모든 복소 근을 임의의 정밀도로 계산하도록 구현되었습니다.
• 콜린스(Collins)와 아크리타스(Akritas)의 유스펜스키(Uspensky)의 알고리듬은, Rouillier와 Zimmermann에 의해 개선되었고, 데카르트의 부호의 규칙(Descartes' rule of signs)을 기반으로 합니다. 이 알고리듬은 임의적으로 작은 폭의 구간으로 분리된 실수 근을 계산합니다. 그것은 Maple에서 구현됩니다 (함수 fsolve와 RootFinding[Isolate]).

Software packages

영-차원 시스템을 자동으로 풀 수 있는 적어도 네 개의 소프트웨어 패키지가 있습니다 (자동으로, 하나는 사람이 입력과 출력 사이에 필요하지 않고, 따라서 사용자에 의한 방법의 지식이 필요하지 않음을 의미합니다). 역시 영-차원 시스템을 푸는 데 유용할 수 있는 여러 다른 소프트웨어 패키지가 있습니다. 그것들 중 일부는 자동 해결기 후에 나열됩니다.

Maple 함수 RootFinding[Isolate]는 유리수에 걸쳐 임의의 다항식 시스템을 입력으로 취하고 (만약 일부 계수가 부동 점 숫자이면 그것들은 유리수로 변환됨) 유리수의 구간 또는 임의의 정밀도의 부동 점(floating point) 근사로 (선택적으로) 표현된 실수 해를 출력합니다. 만약 시스템이 영-차원이 아니면, 이것은 오류로 신호를 보냅니다.

내부적으로, F. Rouillier에 의해 설계된 이 해결기는 먼저 그뢰비너 기저를 계산하고 그런-다음 해의 요구된 근사치가 추론되는 유리 일변수 표현을 계산합니다. 그것은 수백 개의 복소 해까지 가지는 시스템에 대해 일상적으로 작동합니다.

유리 일변수 표현은 Maple 함수 Groebner[RationalUnivariateRepresentation]로 계산될 수 있습니다.

유리 일변수 표현으로부터 모든 복소 해를 추출하기 위해, 우리는 MPSolve를 사용할 수 있으며, 이것은 일변수 다항식의 복소 근을 임의의 정밀도로 계산합니다. MPSolve를 여러 번 실행하여, 해가 안정적으로 유지될 때까지, 매번 정밀도를 두 배로 늘리는 것이 추천되는데, 왜냐하면 입력 변수 방정식에서 근의 대체가 매우 불안정할 수 있기 때문입니다.

두 번째 해결기는 J. Verschelde의 감독 아래에서 쓰인 PHCpack입니다. PHCpack은 호모토피 연속 방법을 구현합니다. 이 해결기는 변수만큼 많은 방정식을 가지는 다항식 시스템의 분리된 복소 해를 계산합니다.

세 번째 해결기는 Bertini, D. J. Bates, J. D. Hauenstein, A. J. Sommese, 및 C. W. Wampler에 의해 쓰인 Bertini입니다. Bertini는 적응 정밀도로 수치적 호모토피 연속을 사용합니다. 영-차원 해 집합을 계산하는 것 외에도, PHCpack과 Bertini 둘 다는 양의 차원 해 집합으로 작업할 수 있습니다.

네 번째 해결기는 Marc Moreno-Maza와 공동 작업자에 의해 쓰인 Maple 라이브러리 RegularChains입니다. 그것은 정규 체인(regular chain)을 수단으로 다항식 시스템을 푸는 다양한 함수를 포함합니다.

See also

• Systems of polynomial inequalities
• Triangular decomposition
• Wu's method of characteristic set