計算機数学 (2020) 第11回

今回から、有限体上の1変数多項式の因数分解に入りました。今回は、Berlekamp（バールカンプ）の因数分解アルゴリズムのうち、f-簡約多項式の存在性に関する議論を行いました。

次回は f-簡約多項式の存在性に関する議論の続きを行ったのち、f-簡約多項式の計算方法の説明に進みます。

計算機数学 (2020) 第10回

今回は、標数0の一意分解整域上の1変数多項式の無平方分解に関する性質について述べ、無平方分解のアルゴリズムと計算量を概観しました。その後、有限体上の1変数無平方分解のアルゴリズムを紹介しました。

次回から、有限体上の1変数多項式の因数分解のアルゴリズムの話題に入る予定です。

計算機数学 (2020) 第9回

今回は、前半で、モジュラー法のもう一つの方法として、中国剰余定理 (Chinese Remainder Theorem) に基づく1変数多項式の最大公約式 (GCD) 計算のアルゴリズムを紹介しました。

後半では、1変数多項式の無平方分解の話題に入り、無平方の定義に触れたのち、標数0の一意分解整域上の無平方分解に関する基本的な性質について述べました。

次回は、今回の続きの説明を行ったのち、標数0の一意分解整域上の1変数多項式の無平方分解、ついで有限体上の1変数多項式の無平方分解のアルゴリズムを紹介します。

計算機数学 (2020) 第8回

今回は、Henselの補題の証明の最後の部分を説明し、Hensel構成の計算量の見積もりを行いました。その後、Hensel構成を持ちいたGCD計算の際に遭遇しうる「共通因子問題」と、その回避策を紹介しました。

次回は中国剰余定理に基づくGCD計算のアルゴリズムの紹介から始める予定です。

計算機数学 (2020) 第7回

今月は1週おきの授業になっています。

今回は、2個の1変数多項式の共通因子のノルムの見積もりに関する定理を紹介し、モジュラー法の一つとして使われるHensel構成の「Henselの補題」とその証明を紹介しました。

次回は、Hensel構成を用いた整数係数1変数多項式のGCD計算のアルゴリズムについて述べる予定です。

計算機数学 (2020) 第6回

今回は、前回途中で終わりました拡張Euclid互除法の応用例の説明として、1変数多項式環の剰余環における逆元計算について説明しました。その後、モジュラー算法の導入として、1変数多項式のノルムの定義を行い、ついで、1変数多項式の因子の係数の絶対値の上界の見積もりを紹介しました。

次回は、この続きで、2つの1変数多項式の最大公約子 (GCD) の係数の絶対値の上界の見積もりを紹介し、Hensel構成に進みます。

計算機数学 (2020) 第5回

今回は「拡張Euclid互除法」の導入を行い、その性質に関する定理の証明を中心に行いました。

拡張Euclid互除法の応用例として、1変数多項式環の剰余環における逆元計算がありますが、この紹介を始めたところで授業時間が終わってしまいましたので、次回はこの紹介から始めたいと思います。そして、モジュラー法を用いたGCD計算の効率化の説明に進む予定です。

計算機数学 (2020) 第4回

今回は、一意分解整域上の1変数多項式環における擬除算の定義から入りました。擬除算の定義を行い、Euclid互除法の除算を擬除算に置き換えることで、一意分解整域上の1変数多項式環でも最大公約因子 (GCD) を計算できるというものです。

後半では、多項式剰余列の定義を行いました。擬除算による多項式剰余列の計算の際、係数膨張が発生することを指摘し、対応策の一つとして、擬剰余を計算するたびに原始的部分 (primitive part) を計算することによる係数膨張の回避を紹介しました。この手法では、原始的部分の計算に係数部のGCD計算が必要になりますが、これを回避する方法として、部分終結式を用いる手法などがあります。

次回は、拡張Euclid互除法から進みます。

計算機数学 (2020) 第3回

今回は、一意分解整域上の多項式環における最大公約因子 (GCD) や最小公倍因子 (LCM) の定義を行いました。それから、体上の1変数多項式環におけるEuclid互除法の計算量の評価を行いました。

次回は、商体を導入せずに最大公約因子の計算を行うためのアイディアとして、擬除算の定義から解説します。

計算機数学 (2020) 第2回

本年度、秋学期の数学学位プログラム「計算機数学」を担当します。

今年は、及川一誠先生が数値解析、私が計算機代数のテーマで、それぞれ1コマずつ担当します。

先週はガイダンスでしたが、今週から授業が始まりました。これからしばらく、1変数多項式の最大公約因子 (GCD) 計算を扱います。今回は、GCD や 最小公倍因子 (LCM) 、ユークリッド整域などの定義を行い、ユークリッド互除法を導入しました。

次回は、擬除算を導入して多項式剰余列を扱う予定です。

LaTeX で DOI などのリンクの埋め込み方 (Springer LNCS)

今、LaTeX で Springer の Lecture Notes in Computer Science のスタイルで原稿を書いているところですが、DOI などのハイパーリンクの埋め込みに際し、いくつかトラブルに遭い、調べて解決したので、解決方法の一例を紹介します。
（下記には技術的な誤りがあるかもしれません。ご指摘いただければ幸いです。参考資料の例示は申し訳ありませんが時間の都合上省略させていただきます。）

参考文献は bibtex で読み込ませていますが、LNCS の bibtex のスタイル (splncs04.bst) によると、doi のフィールドは自動的に "https://doi.org/..." の形式に書き換えられます。
しかし、使ってみると不具合が見つかりました。

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}

というオプションを入れることで解決しました。

3番目のエラーは

doiが変換されたURIが途中で改行されていると、埋め込まれたハイパーリンクのURIが改行前の文字列で止まってしまう

ことです。 例えば、

\url{http://hoge.fuga}

の入力に対し、タイプセットの結果が

http://hoge.　
fuga

のようになった場合、埋め込まれるハイパーリンクは

http://hoge.

となり、正しいサイトに飛べません。
これに対しては、urlパッケージにhyphensオプションを加えた上でhyperrefパッケージも併用し

\usepackage[hyphens,allowmove]{url}
\usepackage{hyperref}

とすることで、正しいハイパーリンクが埋め込まれるようになります。
ついでに、私はcrevrefパッケージも使っていますが、crevrefパッケージはhyperrefパッケージの後で読み込むように言われます。ですので

\usepackage[hyphens,allowmove]{url}
\usepackage{hyperref}
\usepackage{cleveref}

として、当初の目的が達成されました。

計算機数学（大学院）第13回

今回は、前回からのバールカンプアルゴリズムの紹介の続きで、f-簡約多項式からfの既約因子を計算する方法について詳しく説明し、例題を示しました。

これで本年度の授業が一通り終わりました。今年はこれまで通年だった授業が半期の実施になり、一方で、1回あたりの授業時間数が増えたりしたことから授業のペース配分に若干戸惑った部分もありましたが、今回の授業が、計算機代数のアルゴリズムを理解する上での一助になればと思います。

計算機数学II (2019) 第10回：偏微分方程式 (2)

今回は、偏微分方程式の数値解法の2回目で、双曲型（波動方程式）および楕円型（ラブラス方程式）の偏微分方程式に対する差分法を説明し、各解法における安定性の条件について議論しました。

以上で、この授業を一通り終えますが、この授業では、数値計算における基本的な問題に対する手法を概観しました。この授業が、世の中で広く使われている数値計算を理解する上でのヒントになり、さらに先を学ぶ上でのきっかけになれば幸いです。

計算機数学（大学院）第12回

今回は、バールカンプアルゴリズムの中で、f-簡約多項式の計算方法を紹介したのち、f-簡約多項式からfの既約因子を計算する方法の途中まで説明しました。

次回は、f-簡約多項式からfの既約因子を計算する方法の残りを説明し、例題などを示す予定です。

計算機数学II (2019) 第9回：偏微分方程式 (1)

今回と次回で、偏微分方程式の数値解法を紹介します。

今回は、まず、この授業で扱う偏微分方程式として、放物型、双曲型、楕円型の3種類の偏微分方程式と、それぞれの例題をを紹介しました。次に、放物型の偏微分方程式の一つである拡散方程式を解くための差分法について、陽解法と陰解法の2種類の差分法を説明し、各解法の安定性の条件について説明しました。

次回がこの授業の最終回ですが、次回は残った2種類（双曲型、楕円型）の偏微分方程式について、差分法による各解法や安定性の条件について説明します。

計算機数学（大学院）第11回

今回からは有限体上の1変数多項式の因数分解のアルゴリズムについて説明します。最初にバールカンプのアルゴリズムを紹介します。

今回は、バールカンプアルゴリズムの流れを説明した後、重要な道具である「f-簡約多項式」に関し、その存在性などの性質について説明しました。

次回は、f-簡約多項式の計算方法から説明を進めます。

計算機数学（大学院）第10回

今回は、前回の説明を踏まえ、標数0の一意分解整域上の1変数多項式の無平方分解のアルゴリズムと、有限体上の1変数多項式の無平方分解のアルゴリズムを説明しました。

次回からは有限体上の1変数多項式の因数分解のアルゴリズムについて説明します。

計算機数学II (2019) 第8回：常微分方程式 (2)

今回は、前回に引き続き、常微分方程式の数値解法の説明を行いました。オイラー法、ホイン法、ルンゲ-クッタ法の各アルゴリズムを紹介したのち、各アルゴリズムによる計算例と、差分法の不安定性について紹介しました。

次回からは偏微分方程式の数値解法を扱います。