『近似代数』とは？^{∗}

佐々木建昭（筑波大学数学系）、加古富志雄（奈良女子大学理学部）

1 厳密数式処理の限界と近似代数の登場

従来の厳密数式処理は、非常に強力かつ有用で、小・中規模な計算に適用している限り大きな問題点はないように見える。しかし、応用分野で現れるような大規模な計算に適用してみると、大きな問題点を抱えていることが解る。筆者らはそれを計算量の限界と計算法の限界と呼ぶ。計算量の限界とは、計算時間が多すぎたり数式量が大きくなりすぎて、実際的に計算不能に陥ることである。たとえば、厳密数式処理では整数と有理数以外の数は記号で表されるが、そうすると一般の数はそれらの記号の有理式で表されることになり、数式量が増えるとともに計算に非常に時間がかかる。計算法の限界とは、算法が融通性に欠けるうえに、時として計算不能な事態に遭遇することである。たとえば、数値積分では被積分関数が解析的でありさえすれば、簡単な算法で答を 10^{−8} の精度で計算することは容易である。しかし、数式積分は算法が面倒なうえ、被積分関数が少し変わると全く異なる算法が必要になる。さらに、５次以上の一般の方程式が代数的に不可解なように、問題が少し変わると途端に原理的に計算不能に陥ることがある。

厳密数式処理のもつこれらの限界を打破するには何らかの近似の導入が不可欠であろうと思う。たとえば、自然現象を記述するには偏微分方程式が多く用いられるが、理想的に単純化された場合を除き、偏微分方程式を厳密に解くのは絶望的に難しい。これに対して、物理学者は各種の近似を導入し、近似解を求めて自然現象を論じている。 Taylor 展開や Puiseux 展開、 Fourier 展開などは、近似の基礎となる一般的方法であるといえる。そして究極的に柔軟な近似法が数値計算法と言えるだろう。実際、代数的数を浮動小数で近似するだけで計算は非常に楽になる。

しからば、柔軟な数値計算の手法を数式処理に取り込めば素晴らしい計算法ができるだろう、と期待される。この考えは誰でも思いつくもので、数式処理が始まって約 10 年後の 1960 年代末にはその夢が語られている。しかし、その後の 20 年間に得られた成果は驚くほど少ない。見るべき成果は、計算機で計算した膨大な数式を数値計算用のプログラムに変換する際のコード最適化、微分方程式の数値解法における差分化の自動化など、木に竹を接ぐようなものばかりである [4, 6, 7]。なぜ、このような成果しか得られなかったのか？それは、従来の数式処理が根本的には整数・有理数の不連続性に基づく厳密計算であるのに対して、数値計算は根本的には実数・複素数の連続性に基づく近似計算であり、両者はその根本において決定的に異なっているからである。

∗雑誌『数理科学 (サイエンス社)』特集 “数式処理とその周辺” の一記事、 1998 年６月執筆

この事態を打破したのは 1989 年の佐々木・野田の論文 [9] である。この論文において著者らは１変数多項式の “近似 GCD” の概念を提唱し、近似 GCD の “近似精度” と近接根の近接度との関係を論じた。近似 GCD の計算により、通常の GCD 計算では得られない近接根の近接度が得られ、さらに “近似無平方分解” を実行すれば、一定の近接度以下の近接根因子を分離できる。すなわち、近似 GCD の導入により、従来の厳密数式処理では得られなかった有用な情報が得られることを示したのである。彼らは多項式にノルムを導入し、微小な “摂動項” のノルムで近似精度を定義したが、ノルムは連続的に変化しえるし、近似 GCD 自体が一意的には定まらず、（一定の範囲内で）連続的に変動しえるものである。かくして、厳密数式処理で離散的にのみ扱われていた GCD が、連続的概念である近似 GCD にごく自然な形で拡張されたのである。

上記著者らは直ちに近似 GCD を多変数多項式に拡張し、それを使ってある種の悪条件連立代数方程式が良条件化されることを示し [14]、さらに野田は院生とともに有理関数近似の “正規化” に近似 GCD が有用であることを示した [15]。一方、佐々木は、近似 GCD におけるような近似は非常に多くの代数的演算に成立することを指摘し [1]、摂動項を許容しつつ代数的計算を実行する “近似的代数計算法” を提唱し、ついで多変数多項式を摂動項を許容しつつ因数分解する “近似因数分解” の算法を考案し [17, 18]、それ以後、共同研究者らと精力的に近似的代数演算の研究を推進した。このような近似的代数演算は一松信教授により “近似代数” と命名された [2]。

日本における上述の研究は当初、意図的に外国には秘密にされた。素晴らしいアイデアなので、なるべく多くの成果を日本で得ようと考えたからである。しかし、４〜５年のうちに外国に洩れ伝わり、 1994 年頃から欧米の多くの著名な研究者が近似代数の研究に着手し、近似代数はあっというまに世界の数式処理のホットな研究テーマになったのである。

2 １変数多項式の近似 GCD

１変数多項式 P (x) = p_{n}x^{n} + p_{n−1}x^{n−1} + ⋯ + p_{0} に対するノルム ∥P ∥ は無数に定義できるが、代表的なものは次の三つである。

∥P ∥_{1} =^{def} |p_{n}| + |p_{n−1}| + ⋯ + |p_{0}|,
∥P ∥_{2} =^{def} (|p_{n}|^{2} + |p_{n−1}|^{2} + ⋯ + |p_{0}|^{2})^{1/2},
∥P ∥_{∞} =^{def} max{|p_{n}|, |p_{n−1}|, ⋯, |p_{0}|}.

本稿では、特に断らないかぎり、 ∥P ∥ は無限大ノルム ∥P ∥_{∞} を表すものとする。

さて、 ε は正の微小量を表し、１変数多項式 F (x), G(x) は次の関係式を満たすとする。

\{ \begin{matrix}F (x) = D(x)F̃(x) + Δ_{F} (x), \\ G(x) = D(x)G̃(x) + Δ_{G}(x), \end{matrix} max \{\frac{∥Δ_{F} ∥}{∥F ∥}, \frac{∥Δ_{G}∥}{∥G∥}\} = ε ≪ 1.

このとき D を F と G の精度 ε の近似共通因子という。精度（詳しくいえば近似精度）を固定したままで因子 D の次数を最大に選ぶとき、 D のことを近似 GCD という。近似 GCD は非常に稀な場合（たとえば ε = 0 の場合）には一意的に定まるが、一般にはそうでない。たとえば、 ε がやや緩く設定されていれば、 Δ を非常に微小な多項式として次式が成立するが、これは D + Δ が精度 ε 程度の近似 GCD であることを示す。

\{ \begin{matrix}F = (D + Δ)F̃ + Δ′_{F} , & Δ′_{F} = Δ_{F} − F̃Δ, \\ G = (D + Δ)G̃ + Δ′_{G}, & Δ′_{G} = Δ_{G} − G̃Δ. \end{matrix}

近似 GCD に関する主な問題は、１) 効率のよい計算法、２) 近接根と近似 GCD との関係、３) 近似 GCD の次数を定めたときの最小精度とそのときの近似 GCD、であろう。第一の問題に対して、佐々木・野田 [9] は Euclid の互助法を用いた算法を提案した。通常の互助法と異なり、近似 GCD 計算では剰余列 (P_{1}, P_{2}, ⋯, P_{i}, ⋯) の要素が０にならない時点で剰余列計算を停止しなければならない。そのためには剰余をうまく規格化する必要があるが、彼らは次の規格化を提案した。多項式剰余列の要素 P_{i−1} を P_{i} で割ったときの商と剰余をそれぞれ Q_{i}, R_{i+1} とする（すなわち P_{i−1} = Q_{i}P_{i} + R_{i+1}）とき、剰余列の要素 P_{i+1} を次のように規格化する。

P_{i+1} = R_{i+1}/ max{1, ∥Q_{i}∥} (i = 2, 3,…, k).

この規格化を行うとき、上記の問題２) に対する一つの解答として、佐々木・野田は次の興味深い事を示した：多項式 F (x), G(x) は原点を中心とする半径１程度の円内にすべての根をもち、いくつかの根は近接度 δ で互いに近接しているが、他の根は互いに十分離れているならば、 F (x), G(x) から生成される剰余列は i = 3,…, k に対しては ∥P_{i}∥ = O(δ^{0}) となり、 ∥P_{k+1}∥ = O(δ) となる。特に、 G(x) = dF (x)/dx のときは ∥P_{k+1}∥ = O(δ^{2}) となる。残念なことに、佐々木・野田の論文は近似 GCD の精度に関して数学的厳密さを欠き、数学的厳密さを最重要視する人たちからの攻撃にさらされることになった。

なお、１変数多項式の GCD を浮動小数係数にして高速に計算しようとのアイデアが 1985 年、 Schönhage[8] によって提案されていることをコメントしておく。ただし、 Schönhage は本来正確に計算できる GCD を高速に計算するのが目的で、得られた浮動小数係数の GCD を quasi-GCD と呼んだ。これに対し、佐々木・野田の近似 GCD は近似精度０では存在しえない近似共通因子をも対象にしており、 quasi-GCD より広い概念である。

佐々木・野田の近似 GCD を数学的に厳密な形で、あるいは各種に拡張した形で研究しようとの努力が 1993 年頃から世界各地で行われるようになった [4]。そのうち二つを紹介する。第一は Corless ら [10] による最小精度近似 GCD の議論である。簡単な例を調べてみるとすぐに解るが、規格化剰余列により計算した近似 GCD は最小精度のものではない。さて、 A をランクが k 以上の l × l 数値行列とし（k < l）、その特異値を σ_{1} ≥ σ_{2} ≥ ⋯ ≥ σ_{l} とするとき、これらは次の性質を持つ：行列 A に適当な摂動項 Δ を加えて rank(A + Δ) = k となるならば、摂動行列 Δ は ∥Δ∥_{2} ≥ σ_{k+1} を満たし、等式を成立させる Δ が存在する。 Corless らはこの定理を F と G の Sylvester 行列に適用して、 F と G の最小精度の近似 GCD の計算方法を与えた： Sylvester 行列の特異値 σ_{1} ≥ σ_{2} ≥ ⋯ ≥ σ_{l} を計算し、 σ_{k+1}/σ_{k} = O(ε) となるとき近似 GCD が存在する。

近似 GCD の計算は現在のところ効率の面から剰余列計算に頼らざるをえないが、 Hribernig ・ Stetter[12] と佐々木・佐々木 [13] は多項式剰余列に対する明快な関係式を見出した。剰余列の各要素 P_{i} に対し、 A_{i}P_{1} + B_{i}P_{2} = P_{i} を満たす多項式 A_{i}, B_{i} を拡張互助法で計算できる。このとき、 P_{1} と P_{2} は P_{i}, P_{i+1} を用いて次のように表される。

P_{1} = (−1)^{i} · (−B_{i+1}P_{i} + B_{i}P_{i+1}), P_{2} = (−1)^{i} · ( A_{i+1}P_{i} − A_{i}P_{i+1}).

この関係式によれば、剰余列の各要素を max{∥A_{1}∥, ∥B_{i}∥} = 1 (i=3,…, k, k+1) と規格化することにより、 ∥P_{k+1}∥ ≪ 1 のとき P_{k} が近似 GCD となり、 B_{k}P_{k+1} および A_{k}P_{k+1} が摂動項となることがわかる。すなわち、剰余列で計算する近似 GCD の精度がピタリと定まる。

3 １変数・多変数の近似 GCD の応用

佐々木・野田は、 1989 年の論文において既に近似 GCD の重根・近接根問題への応用を論じている。１変数代数方程式を Newton 法などで解くと、重根・近接根に対して収束が異常に遅くなり、得られた結果も精度が非常に悪い（m 重根に対しては有効桁が 1/m に減少する）。これを重根・近接根問題と呼ぶ。重根は微分を繰り返すことにより単根に落ちるから実際上は問題ないが、近接根はそうはいかない。佐々木・野田は近似 GCD を使って近接根因子を分離する算法を与えた。任意の多項式 F (x) は

F (x) = F_{1}(x)F_{2}(x)^{2} ⋯ F_{m}(x)^{m}, i 重根因子はすべて F_{i}(x)^{i}に含まれる,

と表すことができ、与式 F から F_{1}, F_{2},…, F_{m} を分離する無平方分解という有名な算法がある。この分解に必要なのは GCD(F, dF/dx) などの GCD 計算である。 F が近接根を含んでいる場合には、 GCD 演算のかわりに近似 GCD 演算を用いて

F (x) = F_{1}(x)F_{2}(x)^{2} ⋯ F_{m}(x)^{m} + Δ_{F} (x), ∥Δ_{F} ∥/∥F ∥ = ε ≪ 1,

と分解でき、 i 重近接根因子を F_{i} として分離できる。以下に簡単な例をあげる。

例１（近似無平方分解）入力： F (x) = (2x^{2} − 1)(x − 29./41.)(x − 70./99.) の展開形。

• ε = 10^{−4} での分解： F (x) ⟹ (x − 0.707164833)^{3} (x + 0.707106719).

• ε = 10^{−8} での分解： F (x) ⟹ (x − 0.707094337)^{2} (x^{2} − 0.000199 ⋯ x − 0.5001 ⋯).

前章で述べたように、 F が近接度 δ の近接根を持つとき、 GCD(F, dF/dx) は精度 O(δ^{2}) の近似 GCD を持つ。したがって、近似無平方分解は高い安定性で実行できるのみならず、近接根の近接度の大雑把な値も与えてくれる。さらに、 F_{i} の添字 i が近接根の “多重度” を与えてくれる。近似的な代数演算が厳密な代数演算よりも多くの情報を与える典型例と言える。 Euclid の互助法による近似無平方分解の数値的安定性の実験は尾崎・佐々木 [16] により行われた。彼らは、根がランダムに分布する多項式を多数生成して近似無平方分解算法をテストした結果、近接根がある程度クラスター化していれば、算法は十分安定に働くことを確認している。

佐々木・野田の仕事に関連して、最近、 nearest singular 多項式なるものが研究されている [11]。１変数多項式 F (x) が x = α の近辺に m 個の近接根を持つ場合に、 F′(x) = (x − α)^{m}F̃(x) なる多項式で ∥F − F′∥_{2} を最小にする多項式を nearest singular 多項式と呼ぶ。明らかに nearest singular 分解は近似無平方分解の一部である。近似無平方分解については最小精度の議論はまだだが、 nearest singular 分解については最小精度の議論が行われている。

１変数近似 GCD の面白い応用が野田・宮広 [15] により発表された。彼らは１変数関数 F (x) の有理式近似を考えた： F (x) ⇒ N(x)/M(x)。教科書に記載されている理論は多項式 N と M が互いに素であることを前提にしている。ところが、近似式を計算する算法を適用すると、 N と M が互いに素でなくなることが多々生じる。 N と M が有理数係数ならば共通因子は容易に除けるし、たとえ除かなくても近似式は有限個の点 (共通因子の零点) 以外では F (x) をよく近似する。ところが、浮動小数係数の場合、 N と M の近似共通零点は微妙にずれて、それらの零点の近傍で近似式は非常に狭く無限に高いスパイクを持つことになる。 N と M の近似共通因子を近似 GCD で除くと、得られた近似式は与えられた区間で F (x) をよく近似するようになる。野田らはさらに近似 GCD の別の応用もいくつか考案している [4]。

近似 GCD は多変数多項式に対しても定義できる。越智・野田・佐々木 [14] は、多項式剰余列を利用した多変数近似 GCD の計算法を提案し、それを用いてある種類の悪条件連立代数方程式を良条件化する方法を示した。簡単のため、次の形の２変数多項式で説明する。

\{ \begin{matrix}F (x, y) = D(x, y)F̃(x, y) + Δ_{F} (x, y), \\ G(x, y) = D(x, y)G̃(x, y) + Δ_{G}(x, y), \end{matrix} max \{\frac{∥Δ_{F} ∥}{∥F ∥}, \frac{∥Δ_{G}∥}{∥G∥}\} = ε ≪ 1.

連立代数方程式 {F = 0, G = 0} は有限個の解を持つとする。 F と G の数係数を微小に変えて得られる連立代数方程式 {DF̃ = 0, DG̃ = 0} は、 D = 0 と {F̃ = 0, G̃ = 0} に分解でき、前者から無限個の解がでてくる。すなわち、上記の形の連立方程式は悪条件であり、数値的に解くのが非常に難しい。ところで、 D は F と G の精度 ε の近似 GCD であり、近似 GCD 演算により D と F̃, G̃ を計算できる。そこで、次式 H を計算する：

H(x, y) = G̃F − F̃G = G̃Δ_{F} − F̃Δ_{G}.

連立方程式 {F = 0, H = 0} の解が連立方程式 {F = 0, G = 0} の解を全て含むことは容易に解る。しかも、例外的な場合を除き、前者の方程式は後者の方程式が有した悪条件性を有しない。すなわち、悪条件連立代数方程式が良条件に変換されたのである。

4 多変数多項式の近似因数分解

複素数体 C 上の多変数多項式 F (x, y,…, z), G(x, y,…, z), H(x, y,…, z) が

F (x, y,…) = G(x, y,…)H(x, y,…) + Δ_{F} (x, y,…), ∥Δ_{F} ∥/∥F ∥ = ε ≪ 1, なる関係式を満たすとき、 F は精度 ε で G と H に近似因数分解されるという。（近似因数分解は、１変数多項式に対しては根を一定精度で求めればよく、考える必要はない。また、整数環 Z 上の近似因数分解も定義できるが、これは扱いが難しい。）

近似因数分解の概念自体はおそらく以前にもあったであろうが、どう計算すればよいのか途方にくれる。 1991 年、佐々木は協力者らと以下に述べる二つの算法を考案した [17, 18]。 F (x, y,…, z) は x に関してモニック (主係数が１) かつ無平方とし、 F (x, 0,…, 0) は無平方と仮定する。 C 上では F (x, 0,…, 0) は１次因子に分解できる：

F (x, 0,…, 0) = (x − u_{1}) ⋯ (x − u_{n}), u_{i} ≠ u_{j} (i ≠ j).

（根 u_{1},…, u_{n} は数値計算で一定精度まで計算する）。 u_{1},…, u_{n} から Hensel 構成により

F (x, y,…, z) ≡ (x − ϕ_{1}(y,…, z)) ⋯ (x − ϕ_{n}(y,…, z)) (mod (y,…, z)^{k+1})

を満たす y,…, z のべき級数 ϕ_{1},…, ϕ_{n} を計算できる。 k = tdeg_{y,...,z}(F) とし（tdeg は全次数を表す）、上記右辺の因子を二つのグループに分ける： Ĝ = (x − ϕ_{i_{1}}) ⋯ (x − ϕ_{i_{m}}), Ĥ = (x − ϕ_{i_{m+1}}) ⋯ (x − ϕ_{i_{n}}), {i_{1}, ⋯, i_{n}} = {1, ⋯, n}。通常の除算を修正した近似除算を用いて F を Ĝ で試し割りし、残余のノルムが ε 以下かどうかを調べる（ε 以下だと Ĝ は近似因子である）。 Ĝ としてあらゆる組合せを調べることにより、精度 ε の近似因数分解が求まる。

上記算法は、次数 n が小さければ十分実用的だが、最大 2^{n−1} 個の因子候補をチェックするので、 n が大きいとき非常に非効率的である。それに対して佐々木らはエレガントな算法を考案した。２変数多項式で F (x, 0) の根が正確に求まる例を選んで説明する。

例２（第二算法による因数分解）： F (x, y) = x^{4} + (y − 2)x^{3} − (y + 1)x^{2} + (y^{2} + 2)x − y.

• F (x, 0) の因数分解： F (x, 0) = (x − 0) (x − 1) (x − 2) (x + 1).

• Hensel 構成：\{ \begin{matrix}F_{1} & = & (x − 0) & −y/2 & −y^{2}/8 & −y^{3}/16 & −5y^{4}/128 & + ⋯, \\ F_{2} & = & (x − 1) & +y/2 & −y^{2}/8 & −0 & +y^{4}/128 & + ⋯, \\ F_{3} & = & (x − 2) & +y/2 & +y^{2}/8 & +y^{3}/16 & +5y^{4}/128 & + ⋯, \\ F_{4} & = & (x + 1) & +y/2 & +y^{2}/8 & +0 & −y^{4}/128 & + · · · . \end{matrix}

• y の２次以上の係数ベクトルの線形従属性： F_{1}, F_{3} および F_{2}, F_{4} がそれぞれ線形従属。以上より、因子として F_{1}F_{3} = x^{2} − 2x + y, F_{2}F_{4} = x^{2} + yx − 1 が得られる。

この例が示すように、上記の Ĝ が F の多項式因子ならば、 T_{j} =^{def} ϕ_{i_{1}}^{j} + ⋯ + ϕ_{i_{m}}^{j}, (j = 1, 2,…, m) は多項式となる。逆に、べき級数根の j乗和 T_{j} を作り、 T_{j} の高次項が j = 1, 2,…, m について０となるなら T_{j} は F の多項式因子となる。高次項が０となる組合せはべき級数根の j乗の高次項の係数行列に Gauss の消去法を適用して計算できる。

近似因数分解の場合には係数行列の要素は浮動小数であり、計算すべきは行ベクトルの近似線形従属関係である。長坂・佐々木 [21] は、佐々木らのアルゴリズムのいくつかの欠点を補完・改良するとともに、計算量を解析した。その結果、数係数の演算の計算量を O(1) とするとき、上記第二算法の計算量は入力多項式の次数 n について多項式時間であることを示した。上記第二算法はエレガントで、第一算法に比べて漸近的にははるかに効率的であるが、 n = 10 程度でも計算に大変時間がかかり、アルゴリズムの改善が必要である。最近、 Galligo ・ Watt[20] は上記第一算法の改善策を発表している。べき級数根 ϕ_{1},…, ϕ_{n} のうち互いに共役なものはすぐに解るので、その情報やさらなる情報を使ってチェックすべき組合せの個数を減らそうというのである。

上記第二算法の要点は、根の対称式 S_{1} = ϕ_{1}+⋯+ϕ_{m}, ⋯, S_{m} = ϕ_{1} ⋯ ϕ_{m} が y,…, z の多項式になる組合せを、根のべき乗和 T_{1} = ϕ_{1} + ⋯ + ϕ_{m}, ⋯, T_{m} = ϕ_{1}^{m} + ⋯ + ϕ_{m}^{m} の高次項の線形従属関係を調べることにより決定するものである。この論法は、 C 上の近似因数分解に限らず、多くの係数体上での厳密因数分解にも使える。佐々木・佐々木 [19] はこの考えに基づいて、代数拡大体上の多変数多項式、代数関数体上のモニックな多変数多項式、などの統一的因数分解法を発表している。

多変数の代数方程式で記述される社会があるとしよう。二つの社会が小さな摂動項を通じて相互作用している場合、厳密因数分解ではこれらの社会を分離できないが、近似因数分解では分離でき、摂動項の大きさまで分る。このように、近似因数分解は厳密因数分解が成しえない演算を行なうことができるので、今後、各種の応用がなされると思う。現在のところ、応用として多変数多項式の絶対既約性判定が研究されているので、それを説明する。多変数多項式が C 上で既約なとき絶対既約というが、これを厳密計算で判定するのは大変である。佐々木ら [17] は、近似因数分解を使えば、絶対既約であることだけは容易に判定できることを指摘した。 C 上で可約ならば、本章の冒頭に述べた関係式において Δ_{F} = 0 となるから、 Δ_{F} ≠ 0 であることが検出されれば絶対既約であると言える。最近、この方法の効率化が Galligo ・ Watt[20] により発表されている。

5 近似 Puiseux 級数展開

唐突だが、多変数多項式の Hensel 構成から話を始める。多変数多項式 F (x, y,…, z) はモニックかつ無平方で、 F (x, 0,…, 0) も無平方とする（これらの条件を課しても一般性を失わない）。互いに素な１変数多項式 G^{(0)}(x), H^{(0)}(x) に対して

F (x, y,…, z) ≡ G^{(0)}(x)H^{(0)}(x) (mod (y,…, z))

が成立するとき、任意の正整数 k に対して次式を満たす多項式 G^{(k)}, H^{(k)} が存在する。

F (x, y,…, z) ≡ G^{(k)}(x, y,…, z)H^{(k)}(x, y,…, z) (mod (y,…, z)^{k+1}).

G^{(k)}, H^{(k)} を k = 1 ⇒ 2 ⇒ 3 ⇒ ⋯ と順に計算する算法の一つが有名な (一般化された) Hensel 構成である。上記 Hensel 構成は F (x, 0,…, 0) = x^{n} となる場合には破綻するが、佐々木・加古 [22] は Hensel 構成を拡張することにより、この場合にも上記と同様のことができるようにした。

まず、２変数の場合を説明する。最初に Newton 多項式を定義する。 F (x, y) に現れる各単項式 c x^{a}y^{b}, c ∈ C, の指数部 (a, b) を２次元平面上にプロットする。 F がモニックと仮定したから頭項 x^{n} は (n, 0) にプロットされる。この点を通る直線で、 F の頭項以外のどれかの単項式に対応する点を通り、しかもあらゆる単項式に対応する点はこの直線より下にはプロットされない、そのような直線がただ一つ定まる。この直線を L とする。 L 上にプロットされるあらゆる単項式の和を F の Newton 多項式と呼び、 F_{N}(x, y) と表す。 L の傾きを −γ とすると、 F_{N}(x, y) は x と y^{γ} の同次式となる。 F_{N}(x, y) は C 上では互いに素な２個以上の因子に分解できる：

F_{N}(x, y) = (x − u_{1}y^{γ})^{n_{1}} ⋯ (x − u_{m}y^{γ})^{n_{m}}, u_{1},…, u_{m} ∈ C.

（この分解は近似的には F_{N}(x, 1) の数値根 u_{1},…, u_{m} を用いて容易に計算できる）。通常の Hensel 構成は、法を S = (y) とし、 S ⇒ S^{2} ⇒ S^{3} ⇒ ⋯ とあげていく。これに対し、 F (x, y) ≡ F_{N}(x, y) (mod (x, y^{γ})^{n} (y^{γ})) ゆえ、佐々木・加古は法を S_{k} = (x, y^{γ})^{n} (y^{γ})^{k} として、 S_{1} ⇒ S_{2} ⇒ S_{3} ⇒ ⋯ とあげた。このとき、任意の正整数 k に対し

F (x, y) ≡ G_{1}^{(k)}(x, y) ⋯ G_{m}^{(k)}(x, y) (mod S_{k+1})

を満たす G_{1}^{(k)},…, G_{m}^{(k)} を計算する算法を考案し、拡張された Hensel 構成と名付けた。

上記算法を繰り返し適用すると、 F (x, y) は x の１次因子に分解できる。

F (x, y) = (x − ϕ_{1}(y)) ⋯ (x − ϕ_{n}(y)).

上述の説明から解るように、 ϕ_{i}(y) は y の分数べき級数、すなわち Puiseux 級数となる。 Puiseux 展開に関しては、 Newton-Puiseux 法と呼ばれる有名な方法があり、大抵の教科書に載っている。その方法は、次々と代数的数を導入しながら厳密に計算を進めるのだが、大変な計算量となる。試みに、ある院生がその方法を浮動小数で実行してみたところ、とんでもない結果が得られた。 Puiseux 級数は F (x, y) の根を特異点で級数展開したものだが、浮動小数による近似計算では、特異点のすぐ近傍の通常点での Taylor 展開になってしまったのである。すなわち、 Newton-Puiseux 法は近似計算では非常に不安定な方法なのである。一方、佐々木・加古法は数値的に非常に安定な方法であるのみならず、非常に効率的な方法でもある。

佐々木・加古は上記算法を多変数 F (x, y,…, z) の場合に拡張した。ただし、多変数の場合には、 Puiseux 級数に対応する級数展開は一意的ではなく、佐々木・加古は従変数 y,…, z に全次数変数 t を導入し、 t に関する分数べき級数に展開する方法を与えた [22]。主変数 x と全次数変数 t に関する指数の組から、２変数の場合と同様に、 Newton 多項式 F_{N}(x, ty,…, tz) を一意的に定義できる。 F_{N} は、２変数の場合のようには因数分解できないが、代数関数を導入するならば互いに素な因子の積に形式的に分解できる：

F_{N}(x, ty,…, tz) = (x − t^{γ}u_{1}(y,…, z))^{n_{1}} ⋯ (x − t^{γ}u_{m}(y,…, z))^{n_{m}}.

ここで、 u_{1},…, u_{m} は y,…, z の代数関数である。２変数の場合と同様、

F (x, ty,…, tz) ≡ G_{1}^{(k)}(x, ty,…, tz) ⋯ G_{m}^{(k)}(x, ty,…, tz) (mod (x, t^{γ})^{n} (t^{γ})^{k+1})

を満たす G_{1}^{(k)},…, G_{m}^{(k)} を代数関数 u_{1},…, u_{m} を用いて構成することができる。

近似 Puiseux 級数展開は、厳密 Puiseux 級数展開に比べて圧倒的に高速なので、多くの演算で利用されると期待されるが、今のところ、椎原・佐々木 [23] による Riemann 面決定への応用が唯一である。 F (x, y) = 0 の根として定まる代数関数 x = ϕ(y) の Riemann 面を決定するには、各分岐点で代数関数を Puiseux 級数展開し（n 個の分枝がある）、分岐点間でこれらの分枝のどれとどれが繋がっているかを決定すればよい。椎原・佐々木は、１変数代数方程式の数値解の誤差上界で有名な Smith の定理を使うことにより、分枝どうしの繋がりを効率よく決定する方法を考案した。近似演算を使いながらも、数学的に厳密な結果を導けるのが面白い。

6 近似的代数計算の誤差について

数値計算では昔から誤差の重要性が認識され、計算過程で発生する誤差の大きさと伝搬を研究する誤差解析なる言葉が生まれ、また悪条件問題の存在が明らかになった。近似的代数計算においても誤差解析は非常に重要な研究対象である。

浮動小数による計算の誤差については、 1) 丸め誤差の集積、 2) 桁落ち（上位 k ビットが一致する数を引くと答の有効桁数が k ビット減少する）、 3) 情報落ち（無限べき級数を有限項で打ち切る場合のように、本来あるべき情報が欠落する）、の３種が重要である。丸め誤差については、地道に誤差上界を決めるのが正当的方法であろうし、また、入力における誤差をパラメータとみなしてパラメータに関する微分により出力における誤差 (上限ではない) を見積もるのも一法であろう。桁落ちは、たった一度の加減算で誤差が千倍にも百万倍にも大きくなりえるので、非常に危険である。本稿では桁落ちを考える。

一番激しい桁落ちは、正確な計算では等しくなるはずの二数による桁落ちである。これら二数は、一般に別のルートで計算されていて異なる誤差を含んでいるので、引くと答は誤差だけの数となる。計算に重要な役割を演じる項にこのような桁落ちが起きれば、以後の計算は全く意味のないものになってしまう。たとえば、除算においては除多項式の主項が決定的役割を演じるから、多項式剰余列において非常に小さい係数の主項が現れることは大きな問題である。現在のところ、この問題への対策は二つのものがある。第一は白柳・ Sweedler の安定化法（文献 3) 参照）であり、第二は微小項が結果式に及ぼす意味を明らかにしていくことである。

第一の白柳・ Sweedler の安定化法はこうである。対象は浮動小数係数の多項式・有理式であり、演算は有理演算であると仮定する。係数を区関数で表し、係数に関して区間算術で計算を進める。このとき、二数の差 (和) が正確に計算すれば０になる場合、区間数での計算結果は０を含む区間になる。正確に計算すれば０にならない場合にもいくつかの係数は０を含む区間になることがあるが、計算精度を上げていけばいつかは０を含まない区間になる（区間幅の増大は精度には無関係である）。したがって、０を含む区間を０とおいて（その項を捨てて）計算を進めるのである。こうすると、誤差のみからなる項（本来は０になるべき項）は捨てられるので、全く誤った結果に導くことはなくなる。もちろん、本来は０にならない項を０とする危険性は残るが、それは計算精度を上げていけばいつかは消える。一方、第二の方法とは、たとえば多項式剰余列で近似 GCD を計算する場合、除多項式の微小主項を０とおいて計算を進めると、得られる近似 GCD がどう変動するかを明らかにし、ある精度の近似 GCD の計算においては、どの程度の微小主項なら無視してよいかを明らかにすることである。

白柳・ Sweedler の安定化法は、入力が厳密に正しく、無限精度で実行すれば厳密に正しい結果が得られる場合にのみ適用できる。しかし、どれくらい精度を上げれば（係数部の誤差を除いて）正しい答に到達するのかが未解決である。実際、０ではないが任意に小さくなる項が計算途中に現れるよう入力式を細工できることを考えれば、この問題に答えるのは至難である。一方、第二の方法は、実験式などのように入力式に誤差が含まれる場合にも適用可能であり、計算法としてははるかに望ましいと言える。しかし、誤差項が計算結果に及ぼす効果を一般的に論じることは非常に難しく、個々の演算毎に誤差項の効果を論じる必要がある。

7 桁落ちをモニタできる浮動小数システム

上述の三つの誤差のうち、近似的代数計算で最も恐ろしいのは桁落ちである。数値解析での経験によれば、桁落ちは計算過程を丁寧に解析することで大体予言できる。しかし、そのためには個々の演算を各種の場合に詳細に解析する必要があり、解析結果を取り込んだプログラムも複雑にならざるをえない。さらに、近似的代数計算では、どうして桁落ちが生じるのか理解できないような原因で大きな桁落ちが発生することがある。たとえば、剰余列算法による多変数多項式の終結式計算がそうである [27]。したがって、当分の間は、桁落ちをモニターできる浮動小数システムが是非必要である。

加古・佐々木 [24] は桁落ちをモニターできる浮動小数を考案し、 NSL (Nara Standard Lisp) にインプリメントして、 NSL 上の国産数式処理システム GAL に桁落ち対策用のいくつかの機能を組み込んだ。加古・佐々木のアイデアは以下のように簡単なものである。まず、浮動小数 f を二つの浮動小数の組 (f, e)_{A} に拡張する。ここで、 e は桁落ち誤差を表し、添字 A は絶対誤差表示を意味する。 e には初期値として f に含まれる誤差を与える。たとえば、 f が整数や有理数を浮動小数近似したものであれば e = |f| × ε_{M} とする（ε_{M} はマシンイプシロン）。次に、それぞれ誤差 e_{a}, e_{b} を持つ浮動小数 f_{a}, f_{b} の加減乗除を以下の算術公式で実行する。

(f_{a}, e_{a})_{A} ± (f_{b}, e_{b})_{A} ⇒ (f_{a} ± f_{b}, max{e_{a}, e_{b}})_{A},
(f_{a}, e_{a})_{A} × (f_{b}, e_{b})_{A} ⇒ (f_{a} × f_{b}, max{|f_{b}e_{a}|, |f_{a}e_{b}|})_{A},
(f_{a}, e_{a})_{A} ÷ (f_{b}, e_{b})_{A} ⇒ (f_{a} ÷ f_{b}, max{|e_{a}/f_{b}|, |f_{a}e_{b}/f_{b}^{2}|})_{A}.

積と商の算術公式は (f, e)_{A} ⟺ (f, e/|f|)_{R} で定義される相対誤差表現で表すと

(f_{a}, r_{a})_{R} × (f_{b}, r_{b})_{R} ⇒ (f_{a} × f_{b}, max{r_{a}, r_{b}})_{R},
(f_{a}, r_{a})_{R} ÷ (f_{b}, r_{b})_{R} ⇒ (f_{a} ÷ f_{b}, max{r_{a}, r_{b}})_{R}.

となる。これらの算術公式は以下のように解釈できる。二数 f_{a}, f_{b} の和と差では、両者のいずれかに絶対誤差 max{e_{a}, e_{b}} が入っており、丸め誤差を無視すればこの誤差は演算後にもそのまま継承される。同様に、二数 f_{a}, f_{b} の積と商では、両者のいずれかに相対誤差 max{r_{a}, r_{b}} が入っており、この誤差は演算後にも継承される。誤差項の計算には丸めの影響が考慮されていないから、上述の算術式は桁落ちのみを大雑把に検出するものであるといえる。

上述の拡張浮動小数を加古・佐々木は有効浮動小数 ( effective floating-point number ) と名づけたが、区間数の算術公式と比較すると面白い。中央値が c で絶対区間幅が w の区間数を [c, w]_{A} と表し、相対区間幅にした表現を [c, r]_{R} と表す： [c, w]_{A} ⟺ [c, w/|c|]_{R}. このとき、区間数の算術公式は以下となる（次式において、 “≃” は O((r_{x}/c_{x})^{2}) の項を無視することを意味する）。

[c_{a}, w_{a}]_{A} ± [c_{b}, w_{b}]_{A} = [c_{a} ± c_{b}, w_{a} + w_{b}]_{A},
[c_{a}, r_{a}]_{R} × [c_{b}, r_{b}]_{R} ≃ [c_{a} × c_{b}, r_{a} + r_{b}]_{R},
[c_{a}, r_{a}]_{R} ÷ [c_{b}, r_{b}]_{R} ≃ [c_{a} ÷ c_{b}, r_{a} + r_{b}]_{R}.

区間数は誤差を最大限に見積もり、有効浮動小数は誤差を最小限に見積もっていることが分ろう。有効浮動小数は多くの演算でテストされたが、大抵の場合に誤差項は実際の誤差をかなりよく見積もっていることが確認された。しかし、同じ数を何度も加える場合には誤差を過小評価することが解っており、まだ改善の余地があると言える。

8 近似 Hensel 構成の桁落ち誤差解析

近似的代数算法の誤差解析は始まったばかりで、現在までの代表的成果は次の三つくらいである。１) 佐々木・佐々木：近接根をもつ１変数多項式の剰余列計算の桁落ち解析 [25]、２) 佐々木・北本・加古：記号 Newton 法による多変数代数方程式のべき級数解法の桁落ち解析 [26]、３) 佐々木・山口：特異点近傍での多変数 Hensel 構成における桁落ち解析 [28]。本章ではこれらのうち第３のものを取り上げ、近似的代数算法では凄まじい桁落ちが起こりえることを示し、誤差解析の重要性を理解してもらおう。

多変数 Hensel 構成は５章で説明したが、そこでは展開点を原点 (y,…, z) = (0,…, 0) に選んだ。因数分解などでは展開点を都合のよいように選ぶが、一般には展開点はユーザが決めるものである。本章では、与式 F (x, y,…, z) は原点に特異点を持つとし、展開点を原点の δ-近傍 (y,…, z) = (δ_{y},…, δ_{z}), (δ_{y}^{2} + ⋯ + δ_{z}^{2})^{1/2} =^{def} δ ≪ 1, に選ぶ。さて、１変数多項式 G^{(0)} と H^{(0)} は互いに素で、 F (x, δ_{y},…, δ_{z}) = G^{(0)}(x)H^{(0)}(x) を満たすとする。仮定より、 G^{(0)}, H^{(0)} は近接度 O(δ) の近接根を持つ。 Hensel 構成では次式を満たす１変数多項式 A_{i}(x), B_{i}(x) が決定的役割を演じる。

A_{i}(x)G^{(0)}(x) + B_{i}(x)H^{(0)}(x) = x^{i} (i = 0, 1,…, tdeg_{y,...,z}(F)).

G^{(0)} と H^{(0)} が近接根を持つため、 A_{i}, B_{i} の数係数は一般に δ の負べき依存性を持つ。佐々木・山口はこの負べき依存性を丁寧に調べ、例外的場合を除き、 A_{i}, B_{i} を計算する際に δ の負べきに比例する桁落ちが発生することを示した。次に、 F (x, y,…, z)

= ∑_{i=0}^{n} F_{i}(y,…, z)x^{i} とするとき、 Hensel 構成中に

(F_{i_{1}}A_{i_{1}}) (F_{j_{1}}B_{j_{1}}) ⋯ (F_{i_{l}}A_{i_{l}}) (F_{j_{l}}B_{j_{l}})

の形の多項式積が多数現れる。彼らはこれらの積の δ 依存性を丹念に調べ、次の結論を得た。展開点を特異点 (y,…, z) = (0,…, 0) に選び、５章に述べた方法で分解 F (x, y,…, z) = G_{S}(x, y,…, z)H_{S}(x, y,…, z) を行なうとき、 G_{S} と H_{S} が y,…, z の全次数 t に関して分数べきとなる場合（２変数の場合には Puiseux 級数となる）を分岐するといい、 t に関して整数べきとなる場合（２変数の場合には Taylor 級数となる）を交差するという。分岐する場合には O(δ^{−γk}) の桁落ちが発生し、交差する場合には O(δ^{−(γ+1)k}) の桁落ちが発生する。ここで、 γ は特異点の “特異度” できまる非負有理数である。すなわち、 Hensel 構成を高次まで行なえば行なうほど、展開次数に比例した桁数の誤差が発生するのである。佐々木・山口は γ の値を理論的に導き、いくつかの実験により理論どおりの桁落ちが発生することを確認している。以下に彼らの実験例の一つを示す。

例３（Hensel 構成での桁落ち） F (x, u) = x^{4} − ux^{3} − 4u^{2}x^{2} + 4u^{2}x + 3u^{3} − u^{2}.

• 実験：展開点を u = 0.001 とし（δ = 10^{−3}）、 F (x, 0.001) の４個の１次因子を二通りに組み合わせて２組の G^{(0)}, H^{(0)} を作るが、第一組は分岐、第二組は交差とする。

• 理論：分岐の場合は ∥G^{(k)}∥ = O(δ^{−k}) で、桁落ちは生じない。交差の場合は ∥G^{(k)}∥ = O(δ^{0}) で、 O(δ^{−k}) の桁落ちが生じる。

• 結果： Errmax(G^{(k)}) は G^{(k)} の係数中の最大相対誤差を表す（初期相対誤差 = 10^{−15}）。左表：分岐の場合、右表：交差の場合。右表の k ≥ 7 では有効桁数が０になった。

k Errmax(G^{(k)}) coefficient(xv^{k})
1 1.01 × 10^{−15} (+1.52 − 1.57 i ) × 10^{1}
2 2.98 × 10^{−14} (−3.95 + 3.97 i ) × 10^{3}
3 9.46 × 10^{−14} (+1.97 − 1.97 i ) × 10^{6}
4 1.32 × 10^{−13} (−1.23 + 1.23 i ) × 10^{9}
5 1.39 × 10^{−13} (+8.64 − 8.65 i ) × 10^{11}
6 1.39 × 10^{−13} (−6.48 + 6.48 i ) × 10^{14}
7 1.66 × 10^{−13} (+5.09 − 5.09 i ) × 10^{17}
8 1.96 × 10^{−13} (−4.14 + 4.14 i ) × 10^{20}

k Errmax(G^{(k)}) coefficient(xv^{k})
1 2.67 × 10^{−15} +1.50 × 10^{0}
2 6.78 × 10^{−13} +2.96 × 10^{0}
3 1.03 × 10^{−10} +9.71 × 10^{0}
4 1.44 × 10^{−8} +3.46 × 10^{1}
5 2.57 × 10^{−6} +9.75 × 10^{1}
6 2.16 × 10^{−3} +5.81 × 10^{1}
7 2.58 × 10^{−2} −2.42 × 10^{3}
8 8.20 × 10^{−2} +3.82 × 10^{5}

しかしながら、佐々木・山口の理論は Cauchy-Hadamard の定理を用いたもので、個々のどの項どうしがキャンセルするのかを解明したものではない。また、展開点を特異点近傍に限った話である。桁落ちだけに限っても、未解明の点は余りにも多いのである。

9 大きな誤差項をもつ実多項式の実根数

近似代数では入力に摂動項を許容し、出力にも摂動項を許容して代数演算を実行するとした。しかし、近似 GCD や近似因数分解では、入力における摂動項はマシンイプシロン程度で、出力における摂動項に比べて無視できるほど小さい、と暗に仮定してきた。その意味で、入力における摂動項を真正面から取り上げた議論はほとんどなされていないのが実情である。現在のところ唯一の例外といえるのが、本章に述べる照井・佐々木 [29] の最近の仕事である。照井・佐々木は、１変数実多項式の入力に大きな誤差項が含まれている場合に、それが実根の個数にどう影響するかを論じた。近似的代数計算の今後の研究の方向を示す論文なので、最後にこれを取り上げる。

大きな誤差項 Δ(x) を持つ１変数実多項式 P̃(x) を考える。

\{ \begin{matrix}P̃(x) = P (x) + Δ(x), & deg(P̃) = deg(P) = n, \\ Δ(x) = d_{n−1}x^{n−1} + ⋯ + d_{0}x^{0}, & |d_{i}| ≤ δ_{i} ≪ 1. \end{matrix}

P̃(x) は未知だが P (x) は既知で、誤差項の各係数の絶対値の上限は解っているとする。 P̃ の実根数を考えよう。 P が実重根・近接根を持つ場合には、 P の係数の微小な変動も P̃ の実根数を変える可能性が高いが、 P が単根しか持たぬ場合には、係数が少々変動しても P̃ の実根数は不変であろう。では、 P̃ の実根数を変えない範囲で P の係数はどの程度まで変動しえるのか？この問題に対して照井・佐々木は次の解答を与えた。 P̃ の終結式 res(P̃, dP̃/dx) が Δ の変動に対して０にならなければ、 P̃ の実根数は不変である。

次に、実根数を計算するために Sturm 列 (符号を逆転させた多項式剰余列) の計算を考えよう。 P の係数は浮動小数で与えられていると考えるのが当然だから、 Sturm 列を計算するとき、主係数が異常に小さい剰余 P_{i} が現れることがある。

P_{i}(x) = ε_{m}x^{m} + c_{m−1}x^{m−1} + ⋯ + c_{0}, |ε_{m}| ≪ 1.

この場合、 ε_{m} は正しくは０かも知れぬし、０でないとしても、 P_{i} で P_{i−1} を割れば以後の剰余列には大きな桁落ちが発生する。さて、どうしたものか？この問題に対して、照井・佐々木は次の解答を与えた。 P_{i} の終結式 res(P_{i}, dP_{i}/dx) が ε_{m} を連続的に０にする変動に対して０にならなければ、微小主項 ε_{m}x^{m} を０として Sturm 列を計算してよい。

以上より、問題は “終結式が与式の係数の微小変動に対してどう変動するか” に帰着された。照井・佐々木は、１) 与式の係数を区間数で表現して誤差上界を決める方法は一回の剰余計算あたり区間幅が約 2^{4} 倍も増大して全く実用にならない、２) 終結式の行列式表現に Hadamard の不等式を適用して誤差上界を決める方法は誤差上界があまりに過大評価されて意味をなさない、３) 数値計算で感度解析に用いられる方法 (以下に述べる) は実用的に使える、との結論を得ている。以下、第三の方法を簡単に説明する。

終結式計算は簡単な変形で係数に関する線形方程式に変換できる：

(A + ΔA)(x + Δx) = b + Δb.

ここで、 A と b は与式の数係数から作られる行列とベクトルで、未知ベクトル x は Ax = b を満たし、 ΔA と Δb は未知の誤差項を表す。問題は解ベクトルの誤差項 Δx の上限であるが、これについては数値解析で見事な理論が作られており、それによれば次の不等式が得られる。

\frac{∥Δx∥}{∥x∥ + ∥Δx∥} ≤ ∥A∥ ∥A^{−1}∥ \{\frac{∥ΔA∥}{∥A∥} + \frac{∥Δb∥}{∥b∥}\}.

ここで、 ∥A∥ と ∥b∥ はそれぞれ行列とベクトルに対するノルムである。この上限評価はおそらく現時点でベストのものであろう。

照井・佐々木はさらに数値解析で名高い Smith の定理を用いて、 P (x) が実重根・近接根を持つ場合の扱いと、大きな誤差項をもつ多項式の根の存在領域の決め方を論じている。いずれも、数値解析の成果を活かした研究で、今後の大進展を予感させる仕事である。

10 おわりに

以上、近似的代数算法について、これまでの研究成果を総花的に解説してきた（筆者らの仕事の解説に大きく偏ったが…）。上記より、近似代数の研究が非常に活発に行われており、なかんずく日本が非常に重要な寄与をしていることが分るだろう。しかしながら、研究はほんの序の口の段階である。これまで扱われた演算自体が限られたものであるし、誤差解析にはやっと手をつけ始めたばかりのところである。また、近似的代数算法の応用もほんの少ししか研究されていない（本稿では割愛したが、近似代数の制御工学への応用が北本卓也氏により活発に研究されている）。これらの事を考慮すると、近似代数が豊富な内容を有していることが解るだろう。

筆者の一人 (佐々木) は 1996 年秋の京都大学・数理研での研究集会で、ノセテダマスの大予言と題して「今後５年以内に近似代数は世界の数式処理研究の主流になり、有効浮動小数は世界に広まるであろう。もしもこの予言がはずれたら、頭を丸めてボウズになる」と予想した。５年を経ずして第一予想は的中したと言えるが、第二予想に関しては現状は厳しいと言わざるをえない。しかし、近似代数の概念を提唱したこと、近似因数分解算法や近似的代数計算の誤差解析などを次々と発表して、世界的に研究を先導していること、さらに桁落ちがモニターできる浮動小数を考案しインプリメントして、近似代数の研究を総合的・実証的に推進していること、を日本は大いに誇ってよいと思う。

最後に、数式処理学会名誉会長一松信先生には近似代数の成長を全面的に御支援頂いたことに対し、由緒ある数値解析シンポジウム設立者平野菅保先生には近似代数の概念を形成するに到った幾多の議論に対して、また、愛媛大学・野田松太郎氏と NTT コミュニケーション研究所・白柳潔氏に対しては各種の近似的代数算法に関する討論に対して、深い感謝の意を表します。

参考文献

[1] 佐々木建昭：近似的代数計算法, 数理解析研究所講究録, Vol. 676, pp. 307-319 (1988).

[2] 佐々木建昭他：「計算代数と計算幾何」 , 岩波講座応用数学, 岩波書店, 第７章 (1993).

[3] 特集「数式処理の最近の研究動向」 , 情報処理 (情報処理学会), Vol. 39, No. 2 (1998).

[4] 野田松太郎, 甲斐博：数式処理と数値計算 – いかに結合させるか？ , 文献 3), pp. 105-110.

[5] 白柳潔：不安定なアルゴリズムを安定化する, 文献 3), pp. 111-115.

[6] W.S.Brown and A.C.Hearn: Application of symbolic algebraic computation, Comp. Phys. Commun., Vol. 17, pp. 207-215 (1979).

[7] E.W.Ng: Symbolic-numeric interface: a review, Lect. Notes Comp. Sci., Vol. 72, pp. 330-345, Springer-Verlag (1979).

[8] A.Schönhage: Quasi-GCD computations, J. Complexity, Vol. 1, pp. 118-137 (1985).

[9] T.Sasaki and M-T.Noda: Approximate square-free decomposition and root-finding of ill-conditioned algebraic equations, J. Inform. Proces., Vol. 12, pp. 159-168 (1989).

[10] R.M.Corless, P.M.Gianni, B.M.Trager and S.M.Watt: The singular value decomposition for polynomial systems, Proc. of ISSAC’95, pp. 195-207, ACM Press (1995).

[11] N.Karmarker and Y.N.Lakshman: Approximate polynomial greatest common divisors and nearest singular polynomials, Proc. of ISSAC’96, pp. 35-39, ACM Press (1996).

[12] V.Hribernig and H.J.Stetter: Detection and validation of clusters of polynomial zeros, J. Symb. Comp., Vol. 24, pp. 667-681 (1997).

[13] T.Sasaki and M.Sasaki: Polynomial remainder sequence and approximate GCD, SIGSAM Bulletin, Vol. 31, pp. 4-10 (1997).

[14] M.Ochi, M-T.Noda and T.Sasaki: Approximate greatest common divisor of multivariate polynomials and its application to ill-conditioned systems of algebraic equations, J. Inform. Proces., Vol. 14, pp. 292-300 (1991).

[15] M-T.Noda and E.Miyahiro: A hybrid approach for the integration of a rational function, J. CAM, Vol. 40, pp. 259-268 (1992).

[16] Y.Ozaki and T.Sasaki: Univariate factor separation and its application to multiple/close root problem, 数式処理 (数式処理学会), Vol. 6, pp. 30-46 (1998).

[17] T.Sasaki, M.Suzuki, M.Kolár̆ and M.Sasaki: Approximate factorization of multivariate polynomials and absolute irreducibility testing, Japan J. Indust. Appl. Math., Vol. 8, pp. 357-375 (1991).

[18] T. Sasaki, T. Saito and T. Hilano: Analysis of approximate factorization algorithm I, Japan J. Indust. Appl. Math., Vol. 9, pp. 351-368 (1992).

[19] T.Sasaki and M.Sasaki: A unified method for multivariate polynomial factorizations, Japan J. Indust. Appl. Math., Vol. 10, pp. 21-39 (1993).

[20] A.Galligo and S.Watt: A numerical absolute primarity test for bivariate polynomials, Proc. of ISSAC’97, pp. 217-224, ACM Press (1997).

[21] K.Nagasaka and T.Sasaki: Approximate multivariate factorization and its time complexity, presented at IMACS Conference on Application of Computer Algebra, Prague, Aug. 1998.

[22] T.Sasaki and F.Kako: Solving multivariate algebraic equation by Hensel construction, Japan J. Indus. Appl. Math. (to appear). ^{1}

[23] K.Shiihara and T.Sasaki: Analytic continuation and determination of Riemann surface of algebraic function by computer, Japan J. Indus. Appl. Math., Vol. 15, pp. 107-116 (1996).

[24] F.Kako and T.Sasaki: Proposal of “effective floating-point number” for approximate algebraic computation, preprint, 10 pages (1997).

[25] T.Sasaki and M.Sasaki: Analysis of accuracy decreasing in polynomial remainder sequence with floating-point number coefficients, J. Inform. Proces., Vol. 12, pp. 394-403 (1989).

[26] T.Sasaki, T.Kitamoto and F.Kako: Error analysis of power series roots of multivariate algebraic equation, preprint, 30 pages (1994).^{2}

[27] T.Sasaki and T.Sato: Cancellation errors in multivariate resultant computation with floating-point numbers, presented at IMACS Conference on Application of Computer Algebra, Prague, Aug. 1998.

[28] T.Sasaki and S.Yamaguchi: An analysis of cancellation error in multivariate Hensel construction with floating-point number arithmetic, Proc. of ISSAC’98, pp. 1-8, ACM Press (1998).

[29] A.Terui and T.Sasaki: “Approximate zero-points” of real univariate polynomials with large error terms, presented at IMACS Conference on Application of Computer Algebra, Prague, Aug. 1998.

1本論文は 1993 年 1 月に書かれて投稿されたが、査読報告が著者らに届いたのは 1996 年 9 月で、同年 10 月に修正稿を送ったところ、受理通知が届いたのは 1998 年 6 月である。

2本論文は 1994 年 5 月に書かれて投稿されたが、いまだにまともな査読報告が届かない。