コンピュータ代数

数学とコンピュータサイエンスにおいて、^[1] コンピュータ代数は記号計算または代数計算とも呼ばれ、数式やその他の数学的オブジェクトを操作するためのアルゴリズムとソフトウェアの研究と開発を指す科学分野です。コンピュータ代数は科学計算のサブフィールドと見なすことができますが、科学計算は通常、近似浮動小数点数を使用した数値計算に基づいているのに対し、記号計算は値が与えられておらず記号として操作される 変数を含む式を使用した正確な計算を重視するため、通常は異なる分野と見なされます。

記号計算を実行するソフトウェアアプリケーションは、コンピュータ代数システムと呼ばれます。システムという用語は、少なくとも、コンピュータで数学データを表す方法、ユーザープログラミング言語(通常は実装に使用される言語とは異なります)、専用のメモリ マネージャー、数式の入出力用のユーザー インターフェイス、式の簡略化、連鎖律を使用した微分、多項式因数分解、不定積分などの 通常の操作を実行するための大量のルーチンを含む主要なアプリケーションの複雑さを暗示しています。

コンピュータ代数は、数学の実験や数値プログラムで使用される数式の設計に広く使用されています。また、公開鍵暗号化のように純粋な数値手法が失敗した場合や、一部の非線形問題 の場合など、完全な科学的計算にも使用されます。

一部の著者は、コンピュータ代数を記号計算と区別しており、後者の名称は数式を使った計算以外の種類の記号計算を指すのに使用している。一部の著者は、主題のコンピュータサイエンスの側面に記号計算を使用し、数学的な側面に「コンピュータ代数」を使用している。^{[2]一部の言語では、分野名は英語名の直接の翻訳ではない。通常、フランス語では「形式計算」を意味する}calcul formelと呼ばれている。この名前は、この分野が形式手法と結びついていることを反映している。

記号計算は、過去には、記号操作、代数操作、記号処理、記号数学、または記号代数とも呼ばれていましたが、これらの用語は非計算操作も指すため、コンピュータ代数に関しては使用されなくなりました。

コンピュータ代数に特化した学会は存在しないが、この機能は計算機協会のSIGSAM（Special Interest Group on Symbolic and Algebraic Manipulation）と呼ばれる特別興味グループによって担われている。 ^[3]

コンピュータ代数に関する年次会議はいくつかありますが、その中でも最も重要なのはISSAC（記号および代数計算に関する国際シンポジウム）で、SIGSAMが定期的に後援しています。^[4]

コンピュータ代数学を専門とするジャーナルはいくつかあるが、その中でもトップクラスは1985年にブルーノ・ブッフバーガーによって創刊された『Journal of Symbolic Computation』である。^[5]コンピュータ代数学に関する論文を定期的に掲載しているジャーナルは他にもいくつかある。^[6]

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

数値計算でよく使われる数値体系は、浮動小数点数と固定されたサイズの整数である。どちらも、表現が膨れ上がるため、コンピュータ代数には適していない。^[9]

したがって、コンピュータ代数で使用される基本数は数学者の整数であり、通常はマシンワードで許可される最大の基数である、何らかの基数による無制限の符号付き数字列で表されます。これらの整数により、2 つの整数の既約分数である有理数を定義できます。

算術演算の効率的な実装をプログラミングすることは困難な作業です。そのため、ほとんどの無料のコンピュータ代数システムと、MathematicaやMapleなどの一部の商用システム^{[10] [11]は、}事実上の標準となっているGMPライブラリを使用しています。

数値と変数を除き、すべての数式は、演算子のシンボルとそれに続く一連のオペランドとして考えることができます。コンピュータ代数ソフトウェアでは、式は通常このように表現されます。この表現は非常に柔軟で、一見すると数式ではないと思われるものも、数式として表現および操作できます。たとえば、方程式は「=」を演算子とする式であり、行列は「行列」を演算子とし、その行をオペランドとする式として表現できます。

プログラムも、演算子「プロシージャ」と、少なくとも 2 つのオペランド、パラメータのリスト、および本体を含む式として考えられ、表現されます。本体自体は、演算子として「本体」、オペランドとして命令のシーケンスを含む式です。逆に、任意の数式はプログラムとして見ることができます。たとえば、式a + bは、 aとb をパラメータとする加算のプログラムとして見ることができます。このプログラムを実行するには、aとbに指定された値に対して式を評価します。値が与えられていない場合、評価の結果は単にその入力になります。

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

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

この式にxに関する微分の基本規則をそのまま適用すると、次の結果が得られる。 ${\displaystyle 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 ⁻¹と体系的に書き直すことです。言い換えると、式の内部表現では、数値の表現以外に、減算も除算も単項マイナスもありません。

加算と乗算の可換性に関しても、別の困難が生じます。問題は、同類項を結合または相殺するために、同類項をすばやく認識することです。非常に長い和と積の場合、すべての項のペアをテストするのはコストがかかります。これに対処するために、 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.}$

コンピュータで数式を操作しようとすると、いくつかの基本的な数学的疑問が生じます。ここでは主に多変数 有理分数の場合について考えます。これは実際の制約ではありません。なぜなら、式に現れる無理関数が簡略化されると、通常は新しい不定値として扱われるからです。たとえば、

${\displaystyle (\sin(x+y)^{2}+\log(z^{2}-5))^{3}}$

は多項式としてみなされ、${\displaystyle \sin(x+y)}$${\displaystyle \log(z^{2}-5)}$

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

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

リチャードソンの定理から、指数と対数が表現に許されている場合、数値を表す 2 つの表現が意味的に等しいかどうかを判断するアルゴリズムは存在しない可能性があることが分かっています。したがって、(意味的) 等価性は、多項式や有理分数などの一部の表現クラスでのみテストできます。

2 つの式の等価性をテストするには、特定のアルゴリズムを設計するのではなく、式を何らかの標準形式にしたり、式の差を通常の形式にしたりして、結果の構文上の等価性をテストするのが一般的です。

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

コンピュータ代数では、いくつかの理由から、通常、正規形が好まれます。まず、正準形の計算コストは​​、正規形よりも高くなる場合があります。たとえば、多項式を正準形にするには、すべての積を分配法則で展開する必要がありますが、正規形ではこれは必要ありません (以下を参照)。次に、根号を含む式の場合のように、正準形が存在する場合、それが何らかの任意の選択に依存し、これらの選択が独立して計算された 2 つの式で異なる可能性がある場合があります。これにより、正準形の使用が実用的でなくなる場合があります。

ペンシルバニア大学のENIACなどの初期のコンピュータ代数システムは、計算の合間にコンピュータを再プログラムしたり、多くの物理モジュール（またはパネル）を操作したり、IBMカードリーダーにデータを入力したりするために、人間のコンピュータまたはプログラマーに依存していました。 ^[16] ENIACのプログラミングにおける人間主導の計算の大部分は女性の数学者によって処理されました。Jean Jennings、Marlyn Wescoff、Ruth Lichterman、Betty Snyder、Frances Bilas、Kay McNultyがその取り組みを主導しました。^[17]

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

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

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

• 自動定理証明器
• コンピュータ支援による証明
• 計算代数幾何学
• コンピュータ代数システム
• 微分分析装置
• 証明チェッカー
• モデルチェッカー
• 記号数値計算
• シンボリックシミュレーション
• シンボリック人工知能

主題の詳細な定義については、以下を参照してください。

• Buchberger, Bruno (1985). 「シンボリック計算（論説）」（PDF） . Journal of Symbolic Computation . 1 (1): 1–6. doi :10.1016/S0747-7171(85)80025-0.

このテーマに関する教科書の場合:

• Davenport, James H. ; Siret, Yvon; Tournier, Èvelyne (1988)。Computer Algebra: Systems and Algebra Computation。フランス語から A. Davenport および JH Davenport によって翻訳。Academic Press。ISBN 978-0-12-204230-0。
• フォン・ツア・ガテン、ヨアヒム。ゲルハルト、ユルゲン (2003)。現代のコンピューター代数(第 2 版)。ケンブリッジ大学出版局。ISBN 0-521-82646-2。
• Geddes, KO; Czapor, SR; Labahn, G. (1992).コンピュータ代数のためのアルゴリズム. Bibcode :1992afca.book.....G. doi :10.1007/b102438. ISBN 978-0-7923-9259-0。
• Buchberger, Bruno; Collins, George Edwin; Loos, Rüdiger; Albrecht, Rudolf 編 (1983)。コンピュータ代数: 記号計算と代数計算。コンピューティング補足。第 4 巻。doi :10.1007 / 978-3-7091-7551-4。ISBN 978-3-211-81776-6. S2CID  5221892。