記号計算（数式処理）

Symbolic Computation / Computer Algebra

概要

記号計算では、数学的な式を数値に変換することなく記号のまま操作する計算体系を扱う。 式の内部表現から始まり、多項式の演算・補間・GCD・結式・因数分解、イデアル論 (グレブナー基底)、 書き換えシステムと式の簡約化、記号微分・積分・極限・総和、厳密線形代数、代数的数、微分代数、 量化子除去と計算代数幾何、形式的べき級数まで、全30章で体系的に学ぶ。

レベル別

  • 入門（2章）

    数式処理の基本概念、式の内部表現 (木・DAG・ハッシュコンシング)

  • 初級（5章）

    多項式の表現と演算、補間、GCD、結式と部分終結式

  • 中級（7章）

    有理関数の部分分数分解、各種因数分解、p-adic 計算、グレブナー基底

  • 上級（16章）

    書き換えシステム、式の簡約化、記号微分・積分・極限・総和、厳密線形代数、代数的数、微分代数、CAD、計算代数幾何、形式的べき級数

全章一覧

入門 — 基本概念

  1. 第1章 数式処理入門

    数式処理とは何か、CASの歴史 (MACSYMA〜SymPy)、式の木構造表現、正準形と正規形、計算量の考え方

  2. 第2章 式の内部表現 — 木・DAG・ハッシュコンシング

    式木の詳細実装、n 項演算の平坦化、DAG による共通部分式の共有、ハッシュコンシング、主要 CAS の内部表現比較

初級 — 多項式演算の基盤

  1. 第3章 多項式の表現

    密表現と疎表現、再帰表現と分配表現、項順序の選択、多変数多項式の構造

  2. 第4章 多項式の基本演算

    加減乗除、Horner 法による評価、長除法、擬除算、記号微分、Newton 基底・Bernstein 基底

  3. 第5章 多項式補間

    Lagrange 補間、Newton の分割差分、Neville のアルゴリズム、FFT ベース高速補間、Chinese Remainder 補間、Chebyshev 節点

  4. 第6章 多項式の GCD 計算

    式膨張問題、部分終結式アルゴリズム、モジュラ GCD、疎モジュラ GCD、多変数 GCD

  5. 第7章 結式と部分終結式

    Sylvester 行列式、共通根の判定、Euclid 互除法と結式、部分終結式 PRS、Collins-Brown-Traub、陰関数消去

中級 — 有理関数・因数分解・イデアル

  1. 第8章 有理関数の部分分数分解

    未定係数法、Heaviside カバーアップ、Hermite 簡約、Horowitz のアルゴリズム、記号積分の前処理

  2. 第9章 因数分解（有限体上）

    無平方分解、相異次数分解、Cantor-Zassenhaus、Berlekamp、Kaltofen-Shoup

  3. 第10章 因数分解（整数・有理数上）

    Hensel 持ち上げ、Zassenhaus、因子結合問題、LLL 格子基底簡約、van Hoeij のアルゴリズム

  4. 第11章 代数体上の因数分解

    代数体 $\mathbb{Q}(\alpha)$ 上の因数分解、norm の利用、Trager のアルゴリズム、Tschirnhaus 変換、LLL による因子結合

  5. 第12章 p-adic 計算と Hensel 持ち上げ

    p-adic 数、p-adic 絶対値、Hensel の補題、単一・複数因子持ち上げ、Dixon の p-adic 線形代数

  6. 第13章 グレブナー基底

    多項式イデアル、S 多項式、Buchberger のアルゴリズム、sugar strategy、F4・F5 アルゴリズム

  7. 第14章 グレブナー基底の応用

    連立方程式の求解、変数消去、イデアル演算、幾何定理の自動証明、ロボティクス

上級 — 高度な記号計算

🔗 が付いた「橋渡し」章は、前後の分野をつなぎ、次のテーマへ自然に接続する理由を解説する短めの章。「（前後編）」は 2 ファイルに分かれた長編。

  1. 式の簡約化と正規形（前後編）

    項書き換え系、Knuth-Bendix 完備化、三角関数の簡約化、ゼロ判定問題、Richardson の定理

  2. 🔗 計算代数から書き換え系へ（橋渡し）

    Gröbner 基底から抽象書き換え系への一般化、Knuth-Bendix の射程、決定不能性

  3. 式の書き換えシステム

    項書き換えシステム、合流性と停止性、Knuth-Bendix 完備化、パターンマッチング、AC マッチング

  4. 記号微分

    chain rule の形式化、式木の再帰的変換、高階微分、多変数偏微分、Faà di Bruno の公式、自動微分との対比

  5. 🔗 機械的微分から困難な積分へ（橋渡し）

    微分が易しく積分が難しい理由（表現・決定・構成の3層）、Liouville から Bronstein まで

  6. 記号積分（前後編）

    Liouville の定理、Hermite 簡約、Risch アルゴリズム (対数部・指数部)、heuristic 手法

  7. 記号的極限計算

    L'Hôpital 則の限界、Hardy 体、Gruntz アルゴリズム、MrvSet と level、特殊関数への拡張

  8. 微分代数と ODE の記号解法

    微分体、Picard-Vessiot 理論、微分ガロア群、Kovacic のアルゴリズム、Liouvillian 解

  9. 形式的べき級数と応用展望（前後編）

    形式的べき級数の代数、Newton 反復、合成と逆合成、微分方程式の級数解、高速計算

  10. 記号的総和と超幾何級数（前後編）

    Gosper のアルゴリズム、Zeilberger のアルゴリズム、WZ 理論、ホロノミック系

  11. 差分方程式と q-超幾何

    線形差分方程式、Petkovšek アルゴリズム、q-差分、q-超幾何級数、q-版の総和アルゴリズム

  12. 厳密線形代数（前後編）

    Bareiss のアルゴリズム、Hermite 標準形、Smith 標準形、Dixon の p-adic 法、LLL 格子基底簡約

  13. 🔗 厳密線形代数から代数的数へ（橋渡し）（前後編）

    特性/最小多項式、companion 行列、乗算行列、resultant、LLL による最小多項式復元

  14. 代数的数と体拡大（前後編）

    最小多項式、根の分離、代数的数の四則演算、代数拡大体、Trager の因数分解、ガロア群

  15. 計算代数幾何

    イデアルの根基、一次分解、Hilbert 関数、特異点検出、次元の計算

  16. 量化子除去と CAD

    Tarski-Seidenberg 定理、Collins の CAD、射影と持ち上げ、partial CAD、QEPCAD と Redlog

読み物

  • 機械に代数をさせる夢 ［読み物］

    Mathematica や SymPy はどうやって数式を展開し微分し積分するのか。数値と記号の違い、式を木として扱う発想、そして「微分は易しく積分は難しい」謎を、肩の力を抜いて語る。