近似代数 (近似的代数計算)

— 柔軟な数式処理を目指して —

佐々木建昭（筑波大学数学系）

Abstract

数式処理 (計算機による代数的計算) は今や、数学者・自然科学者・工学者のみならず、教育者や学生たちの机上の計算機にまで装備されるほどに普及したが、依然、大きな課題をかかえている。実際に使ってみると、「数式処理は何と融通がきかないのか！」というのが率直な感想であろう。すなわち、当面の最大の課題は数式処理の柔軟化であり、これを解決すれば幅広い応用が開けてくると期待される。本稿では、従来の数式処理を振り返ってその限界と課題を指摘する。ついで、数式処理の柔軟化に対する一つの試みとして、筆者らが提唱し推進している代数の近似化を紹介する。これはほぼ完全に日本のオリジナルな研究である。

1 数式処理のこれまでの発展状況

1. 動機 (１９５８〜１９６５)

(a) 応用分野の大規模な数式計算の機械化 (多項式演算が中心) ：天体軌道の摂動計算、一般相対論の Einstein 方程式の厳密解探索、量子電磁気学の Feynman ダイアグラムの計算、 etc.

(b) コンピュータの高等数学面での知能化 (大学初年級の数学) ：多項式の因数分解、有理式・三角関数などの不定積分と定積分、 etc.

2. 発展 (１９６５〜１９８５)

(a) 実用上の演算：多項式・有理式演算、線形代数の諸演算、 etc.

(b) 計算法の進展：不定積分、定積分、無限級数の求和、常微分方程式の求解、 etc.

(c) 数学の諸演算：群論 (専用システム Cayley, GAP)、イデアル論、環論、 etc.

(d) 種々の分野へ：高エネルギー物理学、原子核物理学、プラズマ物理学、非線形波動 ( ⇒ ソリトン)、非線形力学 ( ⇒ 分岐現象)、 etc.

3. 特徴 (多くの場合、利点なのだが…)

(a) 数値の厳密な扱い：整数 ⟹ 有理数 ⟹ 代数的数 ⟹ 超越数 (e, π, etc)

(b) 数式の厳密な扱い：多項式 ⟹ 有理式 ⟹ 代数関数 ⟹ 初等関数 ⟹ 特殊関数

(c) 計算方法の代数化：代数的演算に帰着させ、拡大体で対象を広げる。たとえば因数分解：有限体上 ⟹ 整数上 ⟹ 代数拡大体上 ⟹ 超越拡大体上不定積分：有理式 ⟹ 初等関数 (対数・指数拡大, 代数拡大) ⟹ 特殊関数の添加

2 従来の数式処理の限界と課題

1. 計算法の限界 (厳密性を重視すれば不可避だが…)

(a) 絶対不可能な計算：５次以上の代数方程式の代数的非可解性、ある種の０判定問題の決定不可能性 ( Hilbert の第 10 問題と関連 )、 etc.

(b) 非常に難しい計算：特殊関数のからむ不定積分、非線形微分方程式の求解、 etc.

(c) 数式変形の難しさ：一般に正準形が定義できない、数式変形は一意的でない

2. 計算量の限界 (実際計算の多くはこの限界で計算不能となる) (a) 算法の代数化の結果：算法が離散数学的 ⟹ 計算量の組み合わせ的爆発

(b) 数学的に厳密な処理：たとえば数は代数的数で表現 ⟹ 複雑で多量の計算

(c) 愚直な計算スタイル：たとえば行列式は無条件に展開 ⟹ 数式量の爆発

3. ソフトの課題 (次々と克服されつつあるが…)

(a) ソフトウェア危機：プログラム量が膨大で手に負えなくなる？

(b) データ型の多様性：多種で多様な数式をどう統一的に扱うか？

(c) 演算の専門細分化：専門細分化により数人の専門家の手には負えなくなる？

⟹ 計算法と計算量の限界の打破 (breakthrough) が課題である

3 先人の知恵に学ぶ

1. 解析学の方法 (無限と極限および連続の概念の導入) (a) 無限小での解析：微分・積分、微分・積分方程式、変分法、超関数、 etc.

(b) 無限級数の導入： Taylor/Laurent 級数、 Puiseux 級数、 Gauss の超幾何級数、 etc.

(c) 関数近似の導入：ミニマックス近似、漸近展開、 Fourier 展開、 wavelet 展開、 etc.

2. 応用分野では (合目的的で大胆な近似と有限化)

(a) 近似解法：摂動計算法、級数展開法、 WKB 法、 etc.

(b) 数値解法：ニュートン法、数値積分法、有限要素法、シミュレーション、 etc.

(c) 統計処理：サンプリング法、統計力学、確率微分方程式、 etc.

3. 数値計算では (効率的で柔軟な解法の考案)

(a) 関数の数値化：関数を数値の世界に写像 (ある種の準同型写像) として扱う

(b) 浮動小数演算：相対的大きさが ε_{M} 以下の微小数を０と近似する

(c) 効率的な算法：逐次近似解法により問題を線形計算に帰着させる、 etc.

⟹ 限界の打破には近似の導入が必須である (厳密性は犠牲に)

4 数式処理の効率化と柔軟化

1. 算法の効率化 (１９６０年代からの一貫したテーマ) (a) 線形算法の開発：因数分解算法、有理式の不定積分算法、 etc.

(b) モジュラー算法：準同型写像 ( 多変数 ⟺ １変数 ⟺ 数値 ) の利用

(c) 確率的な判定法：確率的０判定法、確率的既約性判定法、 etc.

2. 算法の柔軟化 (現在取り組まれているテーマ)

(a) 数値・数式混合算法：単純で有望そうだが、期待したほどうまくいっていない (b) オペレータ式の処理：演算をオペレータで残しておき、必要に応じて実行する

(c) 代数的演算の近似化：近似的代数演算、近似代数 (日本のオリジナル)

3. 算法の柔軟化 (遠い将来にわたるテーマ？？ )

(a) 数値計算との融合：実数・複素数の連続性に基づく近似の導入木に竹を接ぐような結合でなく、算法レベルで数値計算と数式処理を融合化する

(b) 解析的手法の導入： ⟹ 計算機解析？？ (無限と極限と連続の概念の記号処理) ？？ (c) 応用分野への進出： ⟹ 数式計算物理？？、数式計算工学？？、 etc.

⟹ 魅力的で広大な未開の分野が前途に広がっている！！

5 代数的演算の近似化 (近似代数)

1. 応用面からの願望 (こういうことが出来ればいいな…) (a) もともと不定性を含む数式を扱いたい：実験式、数値計算で決定した式、 etc.

(b) 近似的に成立する関係式を決定したい：近似的線形独立、近似的可約、 etc.

(c) 摂動項をもつ数式を代数的に扱いたい：摂動項も含めて系全体を統一的に扱う

2. 近似演算の有用性 (こんなことが可能になりつつある！！ ) (a) 代数的閉体の実際的扱い：実数・複素数、多変数代数方程式のべき級数解、 etc.

(b) 従来なかった新しい演算：近似 GCD、近似因数分解、近似準素分解、 etc.

(c) 近似化による効率的算法：級数展開解法の実用化、絶対既約性のチェック、 etc.

(d) 悪条件問題の統一的解法：悪条件性は “微小項” の存在によることが多いので…

3. 近似代数の舞台裏 (ちょっと楽屋を覗いてみると…) (a) 数値の近似化：浮動小数演算の利用、 “数値誤差” の解析、数値精度向上法、 etc.

(b) 数式の近似化：浮動小数係数の数式、 “数式誤差” の解析、数式精度向上法、 etc.

(c) 演算の算法化：近似 GCD 算法、近似因数分解算法、近似準素分解算法、 etc.

⟹ “微小項” の大きさはマシーン ε から 10^{−3}〜10^{−2} まで！！

6 近似代数…これまでの成果

1. 算法の開発 (見るべき成果あり)

(a) 一変数浮動小数係数多項式の GCD 計算法と正確な GCD 計算への応用： Schoenhage

(b) 一変数多項式の近似 GCD の計算法 (Euclid の互除法) ：佐々木建昭、野田松太郎

(c) 一変数浮動小数係数多項式の剰余列の桁落ちの解析：佐々木建昭、佐々木睦子

(d) 多変数多項式の近似 GCD の計算法 (互除法) ：越智正明、野田松太郎、佐々木建昭 (e) 多変数多項式の近似 GCD の効率的計算法 (Hensel 法) ：佐々木建昭、河崎雅信

(f) 数値と数式の両演算を併用した近似不定積分法：野田松太郎、宮広栄一

(g) 多変数多項式の近似因数分解算法：佐々木建昭、鈴木正幸、 M. Kolar、佐々木睦子 (h) 多変数多項式の近似因数分解算法の理論解析：佐々木建昭、斎藤友克、平野照比古 (i) 多変数多項式の因数分解 (正確および近似) の統一的算法：佐々木建昭、佐々木睦子 (j) 多変数多項式の近似べき級数解の実際的計算法：佐々木建昭、加古富志雄

(k) 多変数多項式の近似べき級数解の誤差解析：佐々木建昭、北本卓也、加古富志雄

(l) 多項式行列の近似固有値と近似固有ベクトルの計算法：北本卓也

(m) 実数係数の多項式イデアルのグレブナー基底と正確な基底計算への応用：白柳潔

(n) 実数係数の数式計算における計算結果の安定化法：白柳潔、 M. Sweedler

2. 応用化研究 (まだほんの少しだが…) (a) 悪条件代数方程式の近似 GCD による良条件化：佐々木建昭、野田松太郎、越智正明 (b) 一変数有理式近似の正規化に対する近似 GCD の応用：野田松太郎、宮広栄一

(c) 近似 GCD に基づく有理式近似のデータ平滑化への応用：野田松太郎、甲斐博

(d) 代数方程式の近似べき級数解を用いた Riemann 面の決定法：椎原浩輔、佐々木建昭 (e) 代数関数の陰関数描画での近似 GCD による孤立特異点の検出法：福井哲夫

(f) 線形代数系の近似記号解法の制御系設計への応用：北本卓也

(g) 線形代数系の近似記号解法の境界値問題への応用：依田潔

3. 数学的側面 (手をつけ始めたところ) (a) 近似多項式の四則演算 (大きな “微小項” の扱い ⟹ O 記号の再定義) ：佐々木建昭

(b) 近似多項式 (１変数・多変数) の因子の不定性の理論：佐々木建昭

(c) 一変数多項式の近似 GCD の理論：佐々木建昭、佐々木睦子

4. ソフト開発 (前途ほど遠し、思いを…)

(a) 数値・数式混合計算機能： Mathematica, Macsyma, Maple, Reduce, etc. (国産システム GAL にも：鈴木正幸、加古富志雄、佐々木建昭、佐藤三久、福井義成)

(b) 桁落ちをモニターできる浮動小数演算機能：加古富志雄、佐々木建昭

(c) 近似代数算法のインプリメント (国産システム GAL へ) ：佐々木建昭、北本卓也、他

⟹ 興味ある方は、まず岩波講座応用数学第５巻「計算代数と計算幾何」を参照されたい