お気楽さんすう屋さんateruiの小技とお知らせのまとめです。
"easy arithmetician" aterui's spot for tips and announcements.
今回は、前回から説明している同時因子分離分解の中で、係数体が奇標数の場合に、ある条件下で無作為に与えられた多項式が分離多項式になる確率に関する補題を証明しました。
その後、係数体が偶標数の場合に成り立つ同様の補題を証明し、同時因子分離分解のアルゴリズムを提示した上で、計算量の見積もりを行いました。
今学期の授業内容はここまでです。今学期は、1変数多項式の最大公約子 (GCD) 計算と、有限体上の1変数多項式の因数分解のアルゴリズムを紹介しました。この話は、一意分解整域上の1変数多項式の因数分解へとつながっていくわけですが、この辺の話題はまた機会がありましたら別の授業などで触れることにしたいと思います。
今回から、有限体上の1変数多項式の因数分解を行うもう一つの手法として、因子次数分離分解 (Distinct Degree Factorization) と同次因子分離分解 (Equal Degree Factorization) を組み合わせたアルゴリズムの解説に入りました。
今回は、因子次数分離分解の手法を説明し、同次因子分離分解の中で、係数体が奇標数の場合に、ある条件下で無作為に与えられた多項式が分離多項式になる確率に関する補題を紹介するところまで進みました。
次回（最終回）は、今回提示した補題の証明を行い、引き続いて係数体が偶標数の場合の分離多項式の探索について紹介します。
今回は、前半で、f-簡約多項式と f を使って f の既約因子を分離する方法について説明しました。後半では、その分離のために用いる多項式を早く見つけるために、f-簡約多項式の最小多項式を用いる方法について説明しました。
Berlekamp の因数分解のアルゴリズムの説明は今回で終わりましたので、この授業の残り2回で、有限体上の1変数多項式の因数分解のもう一つのアルゴリズムとして知られる、カンターとザッセンバウスによるアルゴリズムを紹介する予定です。
今回は、まず前回の授業に引き続き、f-簡約多項式の個数と f の既約因子の個数の関係について調べました。その後、f-簡約多項式を求める方法として、ある行列で定まる線形写像の零空間の基底を求めることによる方法を紹介しました。
次回は、f-簡約多項式から f の既約因子を求める方法に関する議論から始めたいと思います。
今回から、有限体上の1変数多項式の因数分解に入りました。今回は、Berlekamp（バールカンプ）の因数分解アルゴリズムのうち、f-簡約多項式の存在性に関する議論を行いました。
次回は f-簡約多項式の存在性に関する議論の続きを行ったのち、f-簡約多項式の計算方法の説明に進みます。
今回は、標数0の一意分解整域上の1変数多項式の無平方分解に関する性質について述べ、無平方分解のアルゴリズムと計算量を概観しました。その後、有限体上の1変数無平方分解のアルゴリズムを紹介しました。
次回から、有限体上の1変数多項式の因数分解のアルゴリズムの話題に入る予定です。
今回は、前半で、モジュラー法のもう一つの方法として、中国剰余定理 (Chinese Remainder Theorem) に基づく1変数多項式の最大公約式 (GCD) 計算のアルゴリズムを紹介しました。
後半では、1変数多項式の無平方分解の話題に入り、無平方の定義に触れたのち、標数0の一意分解整域上の無平方分解に関する基本的な性質について述べました。
次回は、今回の続きの説明を行ったのち、標数0の一意分解整域上の1変数多項式の無平方分解、ついで有限体上の1変数多項式の無平方分解のアルゴリズムを紹介します。
今回は、Henselの補題の証明の最後の部分を説明し、Hensel構成の計算量の見積もりを行いました。その後、Hensel構成を持ちいたGCD計算の際に遭遇しうる「共通因子問題」と、その回避策を紹介しました。
次回は中国剰余定理に基づくGCD計算のアルゴリズムの紹介から始める予定です。
今月は1週おきの授業になっています。
今回は、2個の1変数多項式の共通因子のノルムの見積もりに関する定理を紹介し、モジュラー法の一つとして使われるHensel構成の「Henselの補題」とその証明を紹介しました。
次回は、Hensel構成を用いた整数係数1変数多項式のGCD計算のアルゴリズムについて述べる予定です。
今回は、前回途中で終わりました拡張Euclid互除法の応用例の説明として、1変数多項式環の剰余環における逆元計算について説明しました。その後、モジュラー算法の導入として、1変数多項式のノルムの定義を行い、ついで、1変数多項式の因子の係数の絶対値の上界の見積もりを紹介しました。
次回は、この続きで、2つの1変数多項式の最大公約子 (GCD) の係数の絶対値の上界の見積もりを紹介し、Hensel構成に進みます。
今回は「拡張Euclid互除法」の導入を行い、その性質に関する定理の証明を中心に行いました。
拡張Euclid互除法の応用例として、1変数多項式環の剰余環における逆元計算がありますが、この紹介を始めたところで授業時間が終わってしまいましたので、次回はこの紹介から始めたいと思います。そして、モジュラー法を用いたGCD計算の効率化の説明に進む予定です。
今回は、一意分解整域上の1変数多項式環における擬除算の定義から入りました。擬除算の定義を行い、Euclid互除法の除算を擬除算に置き換えることで、一意分解整域上の1変数多項式環でも最大公約因子 (GCD) を計算できるというものです。
後半では、多項式剰余列の定義を行いました。擬除算による多項式剰余列の計算の際、係数膨張が発生することを指摘し、対応策の一つとして、擬剰余を計算するたびに原始的部分 (primitive part) を計算することによる係数膨張の回避を紹介しました。この手法では、原始的部分の計算に係数部のGCD計算が必要になりますが、これを回避する方法として、部分終結式を用いる手法などがあります。
次回は、拡張Euclid互除法から進みます。
今回は、一意分解整域上の多項式環における最大公約因子 (GCD) や最小公倍因子 (LCM) の定義を行いました。それから、体上の1変数多項式環におけるEuclid互除法の計算量の評価を行いました。
次回は、商体を導入せずに最大公約因子の計算を行うためのアイディアとして、擬除算の定義から解説します。
本年度、秋学期の数学学位プログラム「計算機数学」を担当します。
今年は、及川一誠先生が数値解析、私が計算機代数のテーマで、それぞれ1コマずつ担当します。
先週はガイダンスでしたが、今週から授業が始まりました。これからしばらく、1変数多項式の最大公約因子 (GCD) 計算を扱います。今回は、GCD や 最小公倍因子 (LCM) 、ユークリッド整域などの定義を行い、ユークリッド互除法を導入しました。
次回は、擬除算を導入して多項式剰余列を扱う予定です。