A.9.5 代数と解析

多項式処理

単変数多項式ではFactorは変形カントール・ザッセンハウス(Cantor-Zassenhaus)法を使用して素数を法として分解し，ヘンゼル(Hensel)構成と試し割りにより整数上の因子を決定する．

代数的数体上の因数分解は有理数上の原始関数を見付け，トレーガー(Trager)法を使用することにより実現される．

多変数多項式ではFactorは適度に選択された整数を1変数を除いて代入し，結果の1変数多項式を分解し，ワン(Wang)法の使用で多変数因子を構成することにより実行される．

一般多項式処理だけを扱うFactorの内部コードは約250ページにわたる．

FactorSquareFreeはまず微分を実行し，GCDを逐次的に計算することにより実行される．

Resultantは明示的部分終結式多項式剰余列または中国剰余定理に伴うモジュラ列を使用する．

Apartはパデ(Padé)法または未定係数法を使用する．

PolynomialGCDとTogetherは通常はズィッペル(Zippel)の疎モジュラ法を含むモジュラ法を使用するが，部分終結式多項式剰余列を使用することもある．

多変数多項式の場合は中国剰余定理が疎な補間法とともに用いられる．

記号線形代数

RowReduce，LinearSolve，NullSpaceおよび MatrixRankはガウスの消去法に基づいている．

Inverseは小行列式展開と行消去を使用する．ピボットは単純な式を目標として発見的に選ばれる．

Detは小規模行列には直接小行列式展開を，大規模行列にはガウスの消去法を使用する．

MatrixExpはまず固有値を求め，それからピュッツァー(Putzer)法を使用する．

さまざまな関数のゼロテストは，数式変換および乱数値を変数に代入した後に区間数値近似を使用して実行される．

方程式の厳密解法と簡約

線形方程式ではガウスの消去法および他の線形代数での方法が使用されている．

代数的数値を表すRootオブジェクトは通常は孤立していて，実証されている数値解法により処理される．ExactRootIsolation->Trueにより， Rootは実根ではデカルトの符号規則に基づいた連分数のアルゴリズムが使用され，複素根ではコリンズ・クランディック(Collins-Krandick)法が使用される．

多項式からなる単一の方程式ではSolveは4次までは明示的式を使用して，多項式をFactorおよびDecomposeで簡約化を試み，巡回および他の特殊多項式を見出す．

多項式からなる連立方程式ではSolveはグレブナー(Gröbner)基底を構成する．

Solveおよび GroebnerBasisは改良ブッフバーガー(Buchberger)法を使用する．

非多項式からなる方程式ではSolveは変数変換および多項式条件の付加を試みる．

Solveと関連関数のコードは約500ページにわたる．

多項式系には，Reduceは実数領域には円筒代数分解を，複素数領域にはグレブナー(Gröbner)基底法を使う．

Reduceは代数関数を使って同値純多項式系を構築する．また，超越関数を用いて，超越条件を持つ多項式系を生成し，次に関数関係と逆画像情報のデータベースを用いてこれを簡素化する．

CylindricalDecompositionは，有向系に関してはコリンズ・フォング(Collins-Hong)法とブラウン・マッカラム(Brown-McCallum)射影法を用い，その他のものにはフォング(Hong)射影法を用いる．CADの構築は，厳密な代数的数の計算によって裏付けられた有効性が証明されている数値を使った，ストゼボンスキー(Strzebonski)の系図に基づいたアルゴリズムが用いられる．零次元の系にはグレブナー(Gröbner)基底法が用いられる．

ディオファンタス(Diophantus)系に関しては，Reduceはエルミートの正規形を用いて線形方程式を解き，線形不等式に関してはContejean-Devie法を用いる．また，単変数整方程式には改良型のCucker-Koiran-Smale法を，二変数二次方程式にはHardy-Muskat-Williams法を楕円に，ペル(Pell)その他の事例には古典的手法を用いる．Reduceは，トゥエ(Thue)方程式のためのTzanakis-de Weger法を含むおよそ25のクラスのディオファンタス方程式のための特化したアルゴリズムを含む．

素数モジュラスでは，Reduceは線形方程式には線形代数を，整方程式には素体上のグレブナー(Gröbner)基底を用いる．複合モジュラスでは，整数に対してエルミートの正規形とグレブナー(Gröbner)基底を用いる．

Resolveは主としてReduceからのアルゴリズムの最適化されたサブセットを用いる．

Reduceと関連関数には，およそ350ページのMathematicaコードとおよそ1400ページのCコードが使われている．

厳密な最適化

線形の場合，MinimizeとMaximizeは厳密な線形計画法を用いる．多項式の場合は，円筒代数分解が用いられる．

簡約化

FullSimplify は，自動的に約40種類の一般代数変換および約400種類の特定の関数規則を適用する．

一般超幾何関数は約70ページのMathematica変換則を使用して簡約される．これらの関数はMathematicaでの多くの解析演算の基礎となる．

FunctionExpandは拡張ガウス法を使用して，引数がの有理数倍であるような三角関数を展開する．

SimplifyおよびFullSimplifyは，必要に応じて結果をキャッシュする．

仮定によって変数が実数に指定されると，多項式制約条件は円筒代数分解によって処理される．一方線形制約条件には，シンプレックス法またはLoos-Weispfenningによる線形限定子消去法が用いられる．厳密な多項不等式にはStrzebonskiの一般的なCAD法が用いられる．

仮定として多項式間の方程式が含まれる場合，グレブナー(Gröbner)基底が使用される．

非代数的関数では，関係データベースが使用され，関数値の領域を引数の領域から決定する．結果の領域が半代数集合に対応する場合は，常に多項式指向のアルゴリズムが使用される．

整数関数では，数百に及ぶ数論の定理がMathematicaの規則の形式で使用される．

微積分

微分は，キャッシ ングを使用して部分的な結果が再びコンパイルされることを避ける．

不定積分では被積分関数と積分ともに初等関数，指数積分関数，多対数および他の関連した関数で表される場合には拡張リシュ(Risch)法が使用される．

他の不定積分には発見的簡約化およびそれに続くパターンマッチングが使用される．

Mathematicaで使用されているアルゴリズムは例えばグラドシュテーン・ライジック(Gradshteyn-Ryzhik)のような標準的参考書に掲載されている不定積分はすべてカバーしている．

特異点を含まない定積分は通常は不定積分の極限を取ることにより評価される．

他の多くの定積分はマリチェフ・アダムチック・メリン(Marichev-Adamchik-Mellin)変換法により処理される．その結果は多くの場合，マイヤー(Meijer)G関数で表され，スレーター(Slater)の定理により超幾何関数に変換される．

Integrateは約500ページのMathematicaコード，約600ページの Cコードからなる．

微分方程式

定数係数の線形方程式システムは行列指数化により解かれる．

係数変数を持ち，解が基本関数とその積分で表せる2階線形方程式はコバシック(Kovacis)法を用いて解かれる．

高階線形方程式はAbramovおよびBronsteinのアルゴリズムで解く．

有理関数の係数を持つ，解が有理関数として与えられる線形方程式の系はAbramov-Bronstein消去法で解く．

多項式係数を持つ線形方程式はメリン(Mellin)変換法を用いて特殊関数によって解く．

可能ならば，非線形方程式は変数の変換，シンメトリー消去法によって解かれる．1階方程式には従来の技術が用いられる．2階方程式と系には因子積分とBocharov法が使われる．

MathematicaのアルゴリズムはKamkeのような標準的な参考書にある一般的な微分方程式のほとんどをカバーしている．

偏微分方程式では変数分離および対称消去法が使用される．

微分代数方程式では，核ベキ零分解により特異部分を分離することに基づいたアルゴリズムを使う．

DSolveは約300ページのMathematicaコードと約200ページのCコードからなる．

総和と乗積

多項式級数はベルヌーイ(Bernoulli)およびオイラー多項式を使用して総和が取られる．

有理関数および階乗関数を含む級数はアダムチック法を使用して一般化超幾何関数により総和が取られ，簡約される．

多ガンマ関数を含む級数は積分表現を用いて総和が取られる．

ディリクレ(Dirichlet)および関連する級数はパターンマッチングにより総和が取られる．

無限級数ではダランベール(d'Alembert)およびラーベ(Raabe)収束テストが使用される．

Mathematicaで使用されているアルゴリズムは，例えばグラドシュテーン・ライジック(Gradshteyn-Ryzhik)のような標準的参考書に掲載されている総和の少なくとも90%をカバーしている．

乗積は主にパターンマッチングを使用して行われる．

Sumおよび Productは約100ページのMathematicaコードからなる．

級数および極限

Seriesは引数を級数展開した関数を反復的に級数展開して評価される．

極限は級数や他の方法を使用して求める．

再帰方程式

RSolveは定数係数を持つ線形方程式系を行列のベキ乗を使って解く．

多項式係数を持つ，解が超幾何的に与えられる線形方程式はvan Hoeij法で解く．

有理関数の係数を持つ，解が有理関数として与えられる線形方程式の系はAbramov-Bronstein消去法で解く．

非線形方程式は変数の変換，Göktasシンメトリー消去法，あるいはGermundsson三角ベキ法が使われる．

Mathematicaのアルゴリズムは，数学の文献でこれまでに論じられたほとんどの一般的な方程式と階の差分方程式をカバーしている．

差分代数方程式では，核ベキ零分解による特異部分の分離に基づく方法が使われる．