コンピュータ代数

数値計算ソフトウェアは近似数値計算に非常に効率的であるため、コンピュータ代数では、正確に表現されたデータを用いた正確な計算を重視するのが一般的です。このような正確な表現は、出力のサイズが小さい場合でも、計算中に生成される中間データが予測不可能な方法で増加する可能性があることを意味します。この挙動は式膨張と呼ばれます。^{[ 7 ]}この問題を軽減するために、データの表現方法や、データを操作するアルゴリズムにおいてさまざまな方法が使用されています。^{[ 8 ]}

表現

数値と変数を除き、すべての数式は、演算子の記号とそれに続く一連の被演算子として考えることができます。数式処理ソフトウェアでは、通常、数式はこのように表現されます。この表現方法は非常に柔軟性があり、一見すると数式ではないように見えるものでも、数式として表現したり操作したりすることができます。例えば、方程式は先頭の演算子が「="」である式として考えることができ、行列は演算子が「matrix」で、その行が被演算子である式として表現することができます。

プログラムも、演算子「手続き」と、少なくとも2つのオペランド（パラメータのリストと本体）を持つ式として考え、表現することができます。本体自体も、演算子「本体」とオペランドの命令シーケンスを持つ式です。逆に、あらゆる数式をプログラムと見なすことができます。例えば、式a + bは、 aとbをパラメータとする加算プログラムと見なすことができます。このプログラムを実行するには、aとbの値が与えられた場合に式を評価します。値が与えられていない場合は、評価結果がそのまま入力値となります。

この遅延評価のプロセスは、コンピュータ代数において基本的です。例えば、ほとんどのコンピュータ代数システムでは、等式の演算子「="」は等価性テストのプログラム名でもあります。通常、等式の評価結果は等式になりますが、ユーザーが「ブール値への評価」コマンドで明示的に要求した場合、またはプログラム内のテストの場合にシステムによって自動的に開始された場合など、等価性テストが必要な場合は、ブール値への評価が実行されます。

式のオペランドのサイズは予測不可能で、作業セッション中に変化する可能性があるため、オペランドのシーケンスは通常、ポインタのシーケンス（ Macsymaなど）^{[ 13 ]}またはハッシュテーブルのエントリのシーケンス（Mapleなど）として表現されます。

xに関する微分法の基本規則を式a ^xにそのまま適用すると、次の結果が得られます。

${\displaystyle x\cdot a^{x-1}\cdot 0+a^{x}\cdot \left(1\cdot \log a+x\cdot {\frac {0}{a}}\right).}$

一般的にはこれよりも単純な表現が望まれ、一般的な表現を扱う際には簡略化が必要です。この簡略化は通常、書き換え規則によって行われます。^{[ 14 ]}考慮すべき書き換え規則にはいくつかの種類があります。最も単純なのは、 E − E → 0やsin(0) → 0のように、常に式のサイズを小さくする規則です。これらはコンピュータ代数システムで体系的に適用されています。

加算や乗算のような結合法則が成り立つ演算では、困難が生じます。結合法則を扱う標準的な方法は、加算と乗算には任意の数の被演算項があると考えることです。つまり、a + b + cは"+"( a , b , c )と表されます。したがって、a + ( b + c )と( a + b ) + cはどちらも"+"( a , b , c )に簡略化され、 a + b + cと表示されます。a − b + cのような式の場合、最も簡単な方法は、− E、E − F、E / Fをそれぞれ( − 1)⋅ E、E + ( − 1)⋅ F、E ⋅ F ^{− 1}と体系的に書き換えることです。言い換えれば、式の内部表現では、数値の表現の外側に減算も除算も単項マイナスもありません。

もう一つの難点は、加算と乗算の可換性です。問題は、同類項を素早く認識して結合または相殺することです。非常に長い和や積の場合、すべての項のペアをテストするのはコストがかかります。この問題を解決するために、Macsyma は和と積のオペランドを、同類項が連続する位置に配置されるようにソートし、容易に検出できるようにします。Maple では、同類項が入力されたときに衝突を生成するハッシュ関数が設計されており、導入されるとすぐに結合できます。これにより、計算中に複数回出現する部分式を即座に認識し、一度だけ保存できます。これにより、メモリを節約し、同一の式に対して同じ操作を繰り返すことを避けることで計算を高速化できます。

書き換え規則の中には、適用される式のサイズを増やす場合もあれば減らす場合もあるものがあります。分配法則や三角関数の恒等式がまさにその例です。例えば、分配法則は書き換えを可能にします。${\displaystyle (x+1)^{4}\rightarrow x^{4}+4x^{3}+6x^{2}+4x+1}$そして${\displaystyle (x-1)(x^{4}+x^{3}+x^{2}+x+1)\rightarrow x^{5}-1.}$このような書き換え規則を適用するか否かを適切に判断する方法がないため、このような書き換えはユーザーが明示的に呼び出した場合にのみ実行されます。分配法則の場合、この書き換え規則を適用するコンピュータ関数は通常「expand」と呼ばれます。逆の書き換え規則である「factor」は、複雑なアルゴリズムを必要とするため、数式処理システムにおける重要な機能となっています（多項式の因数分解を参照）。

数式には、等価性の概念が2つあります。構文的等価性とは、コンピュータ上での表現の等価性です。これはプログラムで簡単にテストできます。意味的等価性とは、2つの式が同じ数学的対象を表す場合です。

${\displaystyle (x+y)^{2}=x^{2}+2xy+y^{2}.}$

リチャードソンの定理によれば、指数関数や対数関数が式に含まれる場合、数値を表す2つの式が意味的に等しいかどうかを判定するアルゴリズムは存在しない可能性がある。したがって、（意味的な）等価性は、多項式や有理分数などの特定の種類の式に対してのみ判定できる。

2つの式の等価性をテストする場合、特定のアルゴリズムを設計する代わりに、式を何らかの標準形にするか、それらの差を正規形にし、結果の構文的等価性をテストするのが一般的です。

コンピュータ代数では、「標準形」と「正規形」は同義ではありません。^{[ 15 ]}標準形とは、2 つの式が構文的に等しい場合に限り、意味的に等しいという形式です。一方、正規形とは、式が構文的にゼロである場合に限り、意味的にゼロになるという形式です。言い換えれば、ゼロは正規形の式として一意に表現されます。

コンピュータ代数では、いくつかの理由から通常、標準形が好まれます。第一に、標準形は標準形よりも計算コストが高くなる場合があります。例えば、多項式を標準形にするには、すべての積を分配法則で展開する必要がありますが、標準形ではそのような必要はありません（後述）。第二に、根号を含む式のように、標準形が存在する場合、それが何らかの恣意的な選択に依存し、独立して計算された2つの式でこれらの選択が異なる場合がある場合があります。このため、標準形の使用が非現実的になる場合があります。

ペンシルベニア大学のENIACのような初期のコンピュータ代数システムは、計算の合間に再プログラミングしたり、多数の物理モジュール（またはパネル）を操作したり、IBMカードリーダーにデータを供給したりするために、人間のコンピュータまたはプログラマに依存していた。^{[ 16 ]} ENIACのプログラミングにおける人間による計算の大部分は、女性数学者によって行われた。ジーン・ジェニングス、マーリン・ウェスコフ、ルース・リヒターマン、ベティ・スナイダー、フランシス・ビラス、ケイ・マクナルティがこれらの取り組みを主導した。^{[ 17 ]}

1960年、ジョン・マッカーシーはマサチューセッツ工科大学在籍中に、 Lispプログラミング言語を用いて記号式を計算するための原始的な再帰関数の拡張を研究した。^{[ 18 ]}彼の「記号式の再帰関数とその機械による計算」に関する一連の研究は未完のままであったが、^{[ 19 ]}マッカーシーとLispを介した人工知能プログラミングとコンピュータ代数への彼の貢献は、マサチューセッツ工科大学のプロジェクトMACと、後にスタンフォード大学のスタンフォードAI研究所（SAIL）となる組織の設立に貢献し、その競争は20世紀後半を通じてコン​​ピュータ代数の著しい発展を促進した。

1960年代と1970年代の初期の記号計算の取り組みでは、コンピュータ代数システムに移植された長年知られているアルゴリズムの非効率性に関する課題に直面した。^{[ 20 ]} ALTRANなどのProject MACの前身は、ハードウェアとインタプリタの進歩によってアルゴリズムの限界を克服しようとしたが、後の取り組みはソフトウェアの最適化に向けられた。^{[ 21 ]}

この分野の研究者の仕事の大部分は、コンピュータ代数で使用するための効率的なアルゴリズムを開発しながら、古典代数を再検討してその有効性を高めることでした。この種の仕事の一例として、分数を簡略化するために必要なタスクであり、コンピュータ代数の重要な構成要素である多項式の最大公約数の計算があります。この計算のための古典的なアルゴリズム、例えばユークリッドの互除法は、無限体上では非効率的であることが判明しました。線形代数のアルゴリズムも同様の困難に直面しました。^{[ 22 ]}そこで研究者たちは、多項式（整数環や一意の因数分解領域上のものなど）をユークリッドの互除法で効率的に計算できる変種に還元する方法を発見することに目を向けました。