お気楽さんすう屋さんateruiの小技とお知らせのまとめです。
"easy arithmetician" aterui's spot for tips and announcements.
今回は、一意分解整域上の1変数多項式環における擬除算の定義から入りました。擬除算の定義を行い、Euclid互除法の除算を擬除算に置き換えることで、一意分解整域上の1変数多項式環でも最大公約因子 (GCD) を計算できるというものです。
後半では、多項式剰余列の定義を行いました。擬除算による多項式剰余列の計算の際、係数膨張が発生することを指摘し、対応策の一つとして、擬剰余を計算するたびに原始的部分 (primitive part) を計算することによる係数膨張の回避を紹介しました。この手法では、原始的部分の計算に係数部のGCD計算が必要になりますが、これを回避する方法として、部分終結式を用いる手法などがあります。
次回は、拡張Euclid互除法から進みます。
今回は、一意分解整域上の多項式環における最大公約因子 (GCD) や最小公倍因子 (LCM) の定義を行いました。それから、体上の1変数多項式環におけるEuclid互除法の計算量の評価を行いました。
次回は、商体を導入せずに最大公約因子の計算を行うためのアイディアとして、擬除算の定義から解説します。
本年度、秋学期の数学学位プログラム「計算機数学」を担当します。
今年は、及川一誠先生が数値解析、私が計算機代数のテーマで、それぞれ1コマずつ担当します。
先週はガイダンスでしたが、今週から授業が始まりました。これからしばらく、1変数多項式の最大公約因子 (GCD) 計算を扱います。今回は、GCD や 最小公倍因子 (LCM) 、ユークリッド整域などの定義を行い、ユークリッド互除法を導入しました。
次回は、擬除算を導入して多項式剰余列を扱う予定です。
doiがアンダーラインを含んでいると bibtex -> (pdf)latex でタイプセットする際にエラーが出る。これに対しては、splncs04.bst で
"\providecommand{\doi}[1]{https://doi.org/#1}"となっていた行を
"\renewcommand{\doi}[1]{\url{https://doi.org/#1}}"と書き換えた上で、本体の.texファイルで
\usepackage{url}としてURLパッケージを使うことにしました。
URLパッケージを使った際、プリアンブル内で \url を使うとエラーが出ることです。（例えば \author{ ... \thanks{... \url{...} ...} ...} のような場合
\usepackage[allowmove]{url}というオプションを入れることで解決しました。
doiが変換されたURIが途中で改行されていると、埋め込まれたハイパーリンクのURIが改行前の文字列で止まってしまうことです。 例えば、
\url{http://hoge.fuga}の入力に対し、タイプセットの結果が
http://hoge.のようになった場合、埋め込まれるハイパーリンクは
fuga
http://hoge.となり、正しいサイトに飛べません。
\usepackage[hyphens,allowmove]{url}とすることで、正しいハイパーリンクが埋め込まれるようになります。
\usepackage{hyperref}
\usepackage[hyphens,allowmove]{url}として、当初の目的が達成されました。
\usepackage{hyperref}
\usepackage{cleveref}
今回は、前回からのバールカンプアルゴリズムの紹介の続きで、f-簡約多項式からfの既約因子を計算する方法について詳しく説明し、例題を示しました。
これで本年度の授業が一通り終わりました。今年はこれまで通年だった授業が半期の実施になり、一方で、1回あたりの授業時間数が増えたりしたことから授業のペース配分に若干戸惑った部分もありましたが、今回の授業が、計算機代数のアルゴリズムを理解する上での一助になればと思います。
今回は、偏微分方程式の数値解法の2回目で、双曲型（波動方程式）および楕円型（ラブラス方程式）の偏微分方程式に対する差分法を説明し、各解法における安定性の条件について議論しました。
以上で、この授業を一通り終えますが、この授業では、数値計算における基本的な問題に対する手法を概観しました。この授業が、世の中で広く使われている数値計算を理解する上でのヒントになり、さらに先を学ぶ上でのきっかけになれば幸いです。
今回は、バールカンプアルゴリズムの中で、f-簡約多項式の計算方法を紹介したのち、f-簡約多項式からfの既約因子を計算する方法の途中まで説明しました。
次回は、f-簡約多項式からfの既約因子を計算する方法の残りを説明し、例題などを示す予定です。
今回と次回で、偏微分方程式の数値解法を紹介します。
今回は、まず、この授業で扱う偏微分方程式として、放物型、双曲型、楕円型の3種類の偏微分方程式と、それぞれの例題をを紹介しました。次に、放物型の偏微分方程式の一つである拡散方程式を解くための差分法について、陽解法と陰解法の2種類の差分法を説明し、各解法の安定性の条件について説明しました。
次回がこの授業の最終回ですが、次回は残った2種類（双曲型、楕円型）の偏微分方程式について、差分法による各解法や安定性の条件について説明します。
今回からは有限体上の1変数多項式の因数分解のアルゴリズムについて説明します。最初にバールカンプのアルゴリズムを紹介します。
今回は、バールカンプアルゴリズムの流れを説明した後、重要な道具である「f-簡約多項式」に関し、その存在性などの性質について説明しました。
次回は、f-簡約多項式の計算方法から説明を進めます。
今回は、前回の説明を踏まえ、標数0の一意分解整域上の1変数多項式の無平方分解のアルゴリズムと、有限体上の1変数多項式の無平方分解のアルゴリズムを説明しました。
次回からは有限体上の1変数多項式の因数分解のアルゴリズムについて説明します。
今回は、前回に引き続き、常微分方程式の数値解法の説明を行いました。オイラー法、ホイン法、ルンゲ-クッタ法の各アルゴリズムを紹介したのち、各アルゴリズムによる計算例と、差分法の不安定性について紹介しました。
次回からは偏微分方程式の数値解法を扱います。
今回は、前半で、モジュラー法の一つとして、中国剰余定理を用いた1変数多項式のGCD計算のアルゴリズムについて説明しました。後半では、1変数多項式の無平方分解の話題に入り、無平方分解に用いる性質を説明しました。
次回は、今回の説明を踏まえ、無平方分解のアルゴリズムを紹介します。
今回と次回では、常微分方程式の数値解法を扱います。
今回は、常微分方程式の種類と問題例を紹介したのち、微分方程式の差分化による差分方程式の導出について説明しました。
次回は、差分法のアルゴリズムを紹介し、代表的な問題に対する差分法の計算について説明します。
今回は、モジュラー法の中から、Hensel構成による1変数多項式のGCDの計算を行うアルゴリズムを紹介しました。
次回は中国剰余定理に基づく1変数多項式のGCDの計算法を紹介し、無平方分解の話題に進みます。
今回からは、1変数多項式の最大公約子 (GCD) 計算のうち、モジュラー法の話題を紹介します。今回は、モジュラー法の背景と、モジュラー法を用いる際に必要となる、多項式の約元や公約式のノルムの見積もりについて説明したのち、Hensel構成の基礎となるHenselの補題の証明を行いました。
次回は、Hensel構成によるGCD計算のアルゴリズムの説明から行う予定です。
今回は、1変数関数の定積分の計算法として、台形則、シンプソン則およびその一般化であるロンバーグ積分法を紹介しました。
次回からは常微分方程式の解法について説明します。
今回は、前回までで証明した「部分終結式の基本定理」に基づき、多項式剰余列の係数膨張を抑える「縮小PRSアルゴリズム」および「部分終結式PRSアルゴリズム」の紹介を行いました。
次回からは、モジュラー法による多項式の最大公約子 (GCD) 計算の効率化手法の紹介に入ります。
今回は、前回のラグランジュ補間のアルゴリズムに続き、ラグランジュ補間の誤差評価を行った後で、スプライン補間と最小二乗法について説明しました。
次回は数値積分の説明を行う予定です。
今回は、前回の内容を踏まえ、2つの補題の証明をした後で「部分終結式の基本定理」の証明を行いました。
次回は、部分終結式の基本定理に基づいて多項式剰余列の係数膨張を抑えるアルゴリズムの紹介を行う予定です。
今回は、前半で、1変数方程式の近似解法として「2分法」および「ニュートン法」を紹介しました。後半では、曲線の推定方法の一つとして「ラグランジュの補間法」を紹介しました。
次回は、ラグランジュの補間法の誤差評価を説明し、曲線の推定の後半として、スプライン補間法と、最小二乗法について説明します。