Triangular decomposition とは

コンピュータ代数では、多項式系Sの三角分解は、それがシステムS1、…、Seのうちの1つの解である場合に限り、点がSの解であるようなより単純な多項式系S1、 …、Se。
その目的が係数フィールドの代数的閉包におけるSの解集合を記述することである場合、これらのより単純なシステムは規則的な連鎖である。多項式系S1、…、Seの係数が実数である場合、Sの実際の解は、規則的な半代数系への三角分解によって得ることができる。どちらの場合も、これらのよりシンプルなシステムは、三角形の形状と顕著な特性を持ち、用語を正当化します。

Kronecker substitution とは

クロネッカー(Kronecker)置換は、未知の多項式の係数を単一の値で評価することによって、Leopold Kroneckerの名前をつけた技術です。 p(x)が整数係数を有する多項式であり、xがpの係数のいずれかより大きさが2のべき乗であるように選択された場合、各項の係数はバイナリから直接読み取られるp(x)の表現。
この方法の1つの応用は、多項式を乗算する計算上の問題を、整数を乗算する(潜在的に簡単な)問題に低減することである。 p(x)およびq(x)が既知の係数を有する多項式である場合、これらの係数を使用して、読み出される積p q(x)の係数が十分大きい2のべき乗であるxの値を決定することができる数p(x)q(x)のバイナリ表現から切り捨てる。 p(x)およびq(x)自体はpおよびqの係数から決定するのが簡単であるので、この結果は、多項式乗算が単一の2進乗算の時間に実行され得ることを示す。

Berlekamp’s algorithm とは

数学、特に計算代数では、Berlekampのアルゴリズムは有限体(ガロア体としても知られている)上の多項式を因数分解するためのよく知られた方法です。このアルゴリズムは、主に行列減少と多項式GCD計算で構成されています。それは1967年にElwyn Berlekampによって考案されました。これは1981年のCantor-Zassenhausアルゴリズムまで問題を解決するための支配的なアルゴリズムでした。現在、多くのよく知られたコンピュータ代数システムで実装されています。

Polynomial identity testing とは

数学では、多項式同定テスト(PIT)は、2つの多変量多項式が同一かどうかを効率的に決定する問題です。より形式的には、PITアルゴリズムは、フィールド内の多項式pを計算し、pがゼロ多項式であるかどうかを決定する算術回路を与えられる。多項式同定テストに必要な計算量を決定することは、代数的計算の複雑さにおいて最も重要な未解決の問題の1つです。

System of polynomial equations とは

多項式方程式のシステムは、f1 = 0、…、fh = 0の連立方程式の集合である。ここで、fiはいくつかの変数、例えばx1、…、xnの多項式である。
通常、フィールドkは有理数のフィールドまたは有限フィールドのいずれかですが、理論の大半はどのフィールドにも適用されます。
解は、すべての方程式を真とし、kの代数的に閉じたフィールド拡張Kに属するxiの値の集合です。 kが有理数のフィールドであるとき、Kは複素数のフィールドです。

Pollard’s kangaroo algorithm とは

計算数論と計算代数では、Pollardのカンガルーアルゴリズム(Pollardのラムダアルゴリズム、下記の命名を参照)は、離散対数問題を解くアルゴリズムです。このアルゴリズムは、同じ問題を解決するための彼のよく知られているρアルゴリズムと同じ論文の中で、数学者J. M. Pollardによって1978年に導入されました。 Pollardは、素数pを法とする乗法群の離散対数問題へのアルゴリズムの適用について説明しましたが、実際には有限の離散対数アルゴリズムであり、任意の有限循環グループで機能します。

Janet basis とは

数学では、ジャネット基底は、そのようなシステムの本質的な恣意性を取り除く、線形均質偏微分方程式(PDE)のシステムのための通常の形式です。それは1920年にモーリス・ジャネットによって導入されました。 1998年にフリッツ・シュワルツによって最初にジャネット基盤と呼ばれた。
このような連立方程式の左辺は、環の微分多項式とみなされ、ジャネットの正規形は、それらが生成する理想の特別な基盤とみなすことができる。言語の乱用により、この用語は元のシステムと、左辺によって生成された差分多項式の理想の両方に適用されます。 Janet基底は、Bruno Buchbergerによって多項式の理想のために導入されたGröbner基底の前身です。任意の与えられた線形pde系のJanet基底を生成するためには、その導関数の順位付けを提供しなければならない。対応するジャネット基盤はユニークです。線形pde系がJanet基底で与えられる場合、その微分次元は容易に決定される。一般的な解決策の不確定性の程度の尺度である。線形pde系のLoewy分解を生成するためには、そのJanet基底を最初に決定しなければならない。

International Symposium on Symbolic and Algebraic Computation とは

ISSACは、シンボリックおよび代数計算に関する国際シンポジウムであり、コンピュータ代数の学術会議です。 ISSACは1988年から毎年7月に開催されています。この会議は、コンピューティング・マシーンズ・スペシャル・インタレスト・グループSIGSAMによって定期的に開催されており、1989年以降の議事はACMによって公表されています。 ISSACは、科学計算研究の出版のための最も影響力のある会議の1つであると考えられている。

Dimension of an algebraic variety とは

数学において、特に代数幾何学において、代数多様体の次元は、様々な等価な方法で定義され得る。
これらの定義の幾つかは幾何学的性質のものであり、他のものは純粋に代数的であり、可換代数に依存している。代数多様体に限定されるものもあれば、代数的集合にも適用されるものもあります。アフィンや射影空間への多様体の埋め込みから独立したものもあれば、そのような埋め込みに関連するものもあります。

Polynomial long division とは

代数では、多項式の長除算は、多項式を同じかそれ以下の多項式で除算するためのアルゴリズムです。これは、長時間分割と呼ばれるおなじみの算術技法の一般化されたバージョンです。複雑な分割問題を小さな問題に分割するため、手作業で簡単に行うことができます。合成区分と呼ばれる簡略版を使用すると、書き込みが少なく、計算が少なくなることがあります。
多項式のlong divisionは、2つの多項式A(被除数)とB(除数)から始まり、Bがゼロでない場合、商Qと剰余Rを生成する多項式のユークリッド分裂を実装するアルゴリズムです。
A = BQ + R、
R = 0またはRの次数がBの次数よりも低い。これらの条件はQとRを一意的に定義する。つまり、QとRはそれらを計算するために使用される方法に依存しない。
結果R = 0は、多項式AがBを係数として持つ場合にのみ発生します。したがって、長い分割は、1つの多項式が別の多項式を要素として持つかどうかをテストする手段であり、そうであれば、それを分解するための手段です。例えば、Aの根rが分かっているならば、Aを(x-r)で割ることで因数分解することができる。