数理科学IIA（第15回）

今回は、この授業の最終回でしたが、前回までに証明した「部分終結式の基本定理」を踏まえ、（拡張）Euclid 互除法による多項式剰余列計算の際に起こり得る係数膨張を抑える方法の一つとして、Collins (1967) による「縮小 PRS 算法」を紹介しました。

• George E. Collins. Subresultants and Reduced Polynomial Remainder Sequences. Journal of the ACM, Volume 14, Issue 1, 128-142, 1967. doi: 10.1145/321371.321381

縮小 PRS 算法による係数膨張の抑制の仕組みを説明した上で、数式処理システム Mathematica を用いて例題を計算し、擬剰余による PRS と縮小 PRS での係数膨張の程度を比較しました。

以上でこの授業を一通り終えました。この授業では、計算代数の基礎を取り上げ、多項式演算、アルゴリズム、計算量といった、現実の計算を考慮する上で必要な概念を説明しました。今後も皆さんの学習に役立てていただければ嬉しく思います。

なお、今回、本授業最後となるレポート課題を出題しました。それから、今回のレポート課題には、今日の授業の内容が必要ですが、今日は学会参加等で授業を欠席している人もいましたので、今回のレポート課題と授業資料を PDF ファイルにして配布します。

授業サポートページ：https://www.math.tsukuba.ac.jp/~terui/ms2a-2013

数理科学IIA（第14回）

今回は、前回残った「補題2」の証明を終えた後、「部分終結式の基本定理」の証明を一通り終えました。

来週7月24日（水）は月曜日の授業のため、この授業はありません。再来週7月31日（水）がこの授業の最終回となります。次回は、部分終結式の基本定理を用いて、多項式剰余列を計算する際に起こり得る係数膨張を防ぐ工夫について説明する予定です。

数理科学IIA（第13回）

今回は「部分終結式の基本定理」の証明に向けた最初の補題である「補題1」の証明の後半部分を行った後、次の「補題2」の証明のほとんどの部分を行いました。

次回は「補題2」の証明の残りの部分を行った後、「部分終結式の基本定理」の証明を行いたいと思います。

数理科学IIA（第12回）

今回は、部分終結式を1つの行列式で表す表現について説明した後、「部分終結式の基本定理」の証明に向けて、最初の補題の証明に入りました。

次回は、この補題の証明の残りの部分から先へ進めていく予定です。

数理科学IIA（第11回）

今回は、前回に引き続き、例題を用いて、多項式剰余列の各要素の係数が、与えられた2つの多項式からどのように導かれるかを調べました。その上で、1変数多項式の「部分終結式」の定義を行いました。

来週6月26日は私が出張ですので休講となり、次回の授業は7月3日となります。次回以降は、部分終結式を1つの行列式で表す表現を導入した上で、「部分終結式の基本定理」を証明するための準備に入る予定です。

数理科学IIA（第10回）

今回は、部分終結式の導入の第1弾として、1変数多項式の擬剰余の係数が、与えられた2つの多項式からどのように導かれるかを、例題を用いて調べました。

次回は、同じく第2弾として、多項式剰余列を例に取り上げ、多項式剰余列の各要素の係数が、与えられた2つの多項式からどのように導かれるかを調べる予定です。

数理科学IIA（第9回）

今回から、多項式剰余列を計算する際の係数膨張を防ぐための方法に関する話題に入りました。

多項式剰余列を計算する場合、擬除算などを用いると、計算される多項式剰余の係数がどんどん大きくなることがあります。ところが、これらの係数には共通な因子があり、しかもそれらは、多項式剰余の定義に応じてある規則に従って増えていきます。この規則を調べることにより、わざわざ係数の GCD を計算しなくても、共通な因子を計算して多項式から取り除くことができます。この規則を知る手がかりになるのが「部分終結式の理論」です。

今回はまず、多項式剰余列を計算する際に起きる係数膨張の例を、数式処理システム Mathematica で実際に多項式剰余列を計算しながら説明しました。後半では、今後の準備として「終結式」や「判別式」の定義を説明しました。

次回からは、擬除算や多項式剰余列の計算の際の係数膨張の様子を例題を通して見つつ、部分終結式の導入につなげたいと思います。

数理科学IIA（第8回）

今回は、前回の授業の続きで、拡張 Euclid 互除法の余因子 (cafactor) の次数上限の証明と、余因子の一意性の証明を行いました。そして、拡張 Euclid 互除法をアルゴリズムの形で提示して時間となりました。

次回からは、多項式剰余列計算の際に生ずる係数膨張などの問題点を紹介し、その対策の話題に入りたいと思います。

数理科学IIA（第7回）

今回はまず、前回の時間にシステムの不具合でできなかった、MathLibre 2013 のデモンストレーションを行いました。今度はシステムが無事起動し、ひとまず、ソフトウェアの紹介ページを紹介して（くどいですが）説明しました。

その後、Euclid の互除法について、前回、証明が途中までで終わった "GCD recursion theorem" の証明の残りを説明しました。後半では、拡張 Euclid 互除法の説明に入りました。拡張 Euclid 互除法の定理の証明は、余因子 (cofactor) の次数に関する性質の証明の途中まで行ったところで、今日は時間になりました。

次回は、拡張 Euclid 互除法の定理の残りの部分を説明し、同アルゴリズムの説明を行う予定です。

数理科学IIA（第6回）

今回から、1変数多項式の最大公約子 (GCD) の話題に入りました。今年度の授業の残りの時間はこの話題が中心になると思います。

今回は、Euclid の互除法のアルゴリズムと、Euclid の互除法の理論的根拠を与える "GCD recursion theorem" を紹介し、同定理の証明の前半を説明して終わりました。

授業時間の残り5分程度で、最初の時間に配った MathLibre 2013 DVD のデモンストレーションを行おうとしましたが、DVD がうまく起動しませんでしたので、授業はそのまま終わりとしました。授業終了後、パソコンの電源を切ってもう一度電源を投入すると DVD が起動しましたが、デモンストレーションは次回行いたいと思います。

次回はMathLibre 2013 DVD のデモンストレーションを行うとともに、今日の定理の証明の続きを行い、 拡張 Euclid の互除法に進みたいと思います。

数理科学IIA（第5回）

今回は、計算量の表記法について説明した後、1変数多項式の四則演算の計算量解析について説明しました。

今回、計算量の基本とした演算は、係数どうしの加減乗除で、これを伴わないような単項や多項式の和は除きました。この辺は、計算機における多項式の内部表現と合わせて議論する必要があると思いますが、ひとまず単純な解析をしています。なお、擬剰余の計算量解析をレポート課題にしました。

次回からは1変数多項式に対する拡張 Euclid の互除法を扱う予定です。

数理科学IIA（第4回）

今回は、1変数多項式の四則演算のアルゴリズムの続きで、減算、乗算、擬除算の定義を行いました。それから、計算量の紹介をちょっと行ったところで時間になりました。

次回は計算量の評価の際に現われる O 記号の定義について説明した後、これまでに授業で定義した、1変数多項式の四則演算のアルゴリズムについて、それらの計算量を見積もる予定です。

数理科学IIA（第3回）

今回はまず、アルゴリズムの基本的な事項として、アルゴリズムの要件と記法、制御構造について説明しました。後半では、1変数多項式の四則演算をアルゴリズムの形で書き下すことにし、今回はまず加法のアルゴリズムについて説明しました。

次回は、今回に引き続き、1変数多項式の四則演算のうち、減算からアルゴリズムの形で書き表すことについて説明します。

数理科学IIA（第2回）

今日は、多項式演算を考える上での基礎として、まず、多項式環の中での記法や概念の定義に関する説明を行いました。

その後、多項式演算のうち、計算代数特有のものとして「擬除算」の説明を行いました。最後に、擬除算の計算を1題、レポート課題として出題しました。

次回はアルゴリズムの基本的な事項や記法について説明する予定です。

数理科学IIA（第1回）

今日から今年度の大学院の授業が始まりましたが、早速、私の授業も始まりました。

私が担当する大学院の授業は、これまでと内容は同じで、5回目の担当になりますが、授業編成で昨年度からの変更点がいくつかあります。まず、2学期制への移行に伴い、これまでの「数理科学II」が、春学期（前期）の「数理科学IIA」と秋学期（後期）の「数理科学IIB」に分割されました。春学期の「数理科学IIA」を私が担当し、秋学期の「数理科学IIB」を田島慎一先生が担当される構成は昨年度と同じです。次に、この授業は今年度から教育研究科 教科教育専攻 数学教育コースの授業「情報数学概論IIA」を兼ねての開講になりました。

春学期の「数理科学IIA」では、おもに1変数多項式の最大公約式 (GCD) を計算する部分終結式算法を中心に、多項式演算やアルゴリズムの概要について説明します。今日は授業のガイダンスとして、授業内容の説明と、参考書や主な数式処理システムの紹介を行いました。次回から数学の話に入ります。次回は多項式環の基本的事項から説明する予定です。

今年度から教育研究科の授業を兼ねたためか、これまで片手で数えられるくらいだった履修者数が、今日は大幅に増えました。皆さんいずれ履修科目の取捨選択を行うとは思いますが、より多くの人が理解できる授業にしていきたいと思います。