数値および関連関数

Documentation MathematicaMathematicaブック Mathematicaリファレンスガイド内部実装に関する注意

A.9.4 数値および関連関数

数表現と数値評価

大きな整数および高精度近似数は，機械整数の長さに応じて，または桁を基底とした配列として保存される．

精度は内部で浮動小数点数として保存されている．

IntegerDigits，RealDigitsおよび関連する基底変換関数は，帰納的分割統治アルゴリズムを使用する．これと同様のアルゴリズムが数値の入出力に使われる．

Nは，要求された全体の精度を得るため，内部作業精度の増加に適応型手続きを使用する．

Floor，Ceilingおよび関連する関数は，厳密な入力から厳密な出力を生成するために，Nと同様に適応型手続きを使用する．

基本算法

大きな整数および高精度近似数の積はインターリーブされた基礎的な法，カラツバ(Karatsuba)法，3ウェイToom-Cook法，および数論変換法を使用している．

特定のアーキテクチャのための機械語の最適化はGMPを使って行う．

整数のベキは左右二進法分解によるアルゴリズムを使用している．

近似数の逆数および有理ベキは，ニュートン法を使用する．

厳密な根は数値近似から始めている．

有意算法がマシン精度を越える近似数値を使う算法で使用されている．

擬似乱数

Random（整数乱数）はウルフラム則30セルラーオートマトンジェネレータを使用している．

実数乱数に関してはマーサグリア・ザマン(Marsaglia-Zaman)借り減算ジェネレータを使用している．

数論関数

GCDはHGCD法，ジェベリーン・ソレンソン・ウェーバー(Jebelean-Sorenson-Weber)加速GCD法，それにユークリッド法および2のベキ乗逐次除去に基づくアルゴリズムを組み合せて使用している．

PrimeQは最初に小さい素数を使用して除算可能かを試し，次にミラー・ラビン(Miller-Rabin)強擬似素数テストベース2およびベース3を使用し，次にルーカス(Lucas)テストを試みる．

1997年現在，この方式はでのみ正しいことがわかっており，がこれより大きいとき複合数を素数であると判断することもあり得る．

パッケージNumberTheory`PrimeQ`はすべてので正しいことが証明されている．アルゴリズム自体はかなり遅いものであるが素数かどうかを確認できる．

FactorIntegerは小さな素数を試験的に除算してみる方法とポラード(Pollard)，ポラード・ローおよび二次ふるい法を交互に試す．

パッケージNumberTheory`FactorIntegerECM`は非常に大きい整数の素因数分解に適した楕円曲線アルゴリズムを含んでいる．

Primeおよび PrimePiは疎キャッシングおよびふるいを使用する．が大のときは，素数密度の漸近推定に基づきPrimePiでラガリアス・ミラー・オドリスコ(Lagarias-Miller-Odlyzko)アルゴリズムが使用され，反転してPrimeを求める．

LatticeReduceはレンストラ・レンストラ・ロヴァッツ(Lenstra-Lenstra-Lovasz)の格子算法アルゴリズムを使用する．

要求された項数を得るため，ContinuedFractionは自己再開始分割統治アルゴリズムを用いた修正レーメー(Lehmer)の間接法を使用して，各ステップで要求される数値精度を削減する．

ContinuedFractionは，再帰関係を使用して2次無理数の周期連分数を得る．

FromContinuedFractionは，分割統治アルゴリズムで最適化された反復行列乗法を使用する．

組合せ関数

ほとんどの組合せ関数は疎キャッシングおよび繰返し計算を使用する．

Factorial，Binomialおよび関連する関数は，分割統治アルゴリズムを使用して，部分積の桁数を調整する．

Fibonacci[n]はnの2進数列に基づく反復法を使用する．

PartitionsP[n]はnが小さいときはオイラー(Euler)の五角式を使用し，nが大きいときは直接的なハーディ・ラマヌジャン・ラーデマッハー(Hardy-Ramanujan-Rademacher)法を使用する．

ClebschGordanおよび関連する関数は一般超幾何級数を使用する．

初等超越関数

指数および三角関数はテイラー級数，引数を倍にする安定な反復法および種々の関数公式を使用する．

対数および逆三角関数はテイラー級数と関数公式を使用する．

数学定数

定数の値は一度計算されるとキャッシュされる．

2進分割は定数の計算の部分分割に使用される．

Piは，チュドノフスキー(Chudnovsky)式を使用して計算される．

Eは級数展開から計算される．

EulerGammaは，ブレント・マクミラン(Brent-McMillan)アルゴリズムを使用する．

Catalanは，線形収束するラマヌジャン総和から計算される．

特殊関数

マシン精度を考慮して，ほとんどの特殊関数はMathematicaにより導かれた有理ミニマックス近似を使用する．以下の注は主に任意精度に適用される．

直交多項式は多項式では安定反復式，一般には超幾何関数を使用する．

Gammaは漸化式，関数方程式およびビネット(Binet)漸近式を使用する．

不完全ガンマおよびベータ関数は超幾何級数および連分数を使用する．

PolyGammaはオイラー・マクローリン(Euler-Maclaurin)総和，関数方程式および漸化式を使用する．

PolyLogはオイラー・マクローリン総和，不完全ガンマ関数での展開および数値積分を使用する．

Zetaおよび関連する関数はオイラー・マクローリン総和および関数方程式を使用する．臨界辺ではリーマン・ジーゲル(Riemann-Siegel)式も使用される．

StieltjesGammaはゼータ関数積分表現の数値積分に基づいたカイパー(Keiper)のアルゴリズムを使用する．

誤差関数および指数積分に関連した関数はすべて不完全ガンマ関数を使用して評価される．

逆誤差関数は2項検索および高次一般化ニュートン(Newton)法を使用する．

ベッセル(Bessel)関数は級数および漸近展開を使用する．整数次に関しては安定な前進漸化式を使用することもある．

超幾何関数は関数方程式，安定な漸化式，級数展開および漸近級数を使用する．NSumおよび NIntegrateによる方法を使用することもある．

ProductLogは有理近似および漸近展開から始まる高次ニュートン法を使用する．

楕円積分は下降ガウス(Gauss)変換を使用して評価される．

楕円シータ関数は級数項の反復評価による級数総和を使用する．

他のほとんどの楕円関数は算術幾何平均法を使用する．

マシュー(Mathieu)関数はフーリエ級数を使用する．マシュー特性関数はブランク(Blanch)のニュートン法の一般化形式を使用する．

数値積分

Method->Automaticにより1次元ではNIntegrateはGaussKronrodを使用し，それ以外ではMultiDimensionalを使用する．

もしMaxPointsの設定が明示的に与えられている場合はNIntegrateはデフォルト値ではMethod->QuasiMonteCarloを使用する．

GaussKronrod : クロンロッド(Kronrod)点での評価に基づく誤差評価適応型ガウス積分．

DoubleExponential : 非適応型2重指数数値積分．

Trapezoidal : 初等台形法．

Oscillatory : 三角関数およびベッセル関数を含む積分処理のための変換．

MultiDimensional : 適応型ゲンツ・マリック(Genz-Malik)アルゴリズム．

MonteCarlo : 非適応型モンテカルロ．

QuasiMonteCarlo : 非適応型ハルトン・ハマーズリー・ウォズニアコスキー(Halton-Hammersley-Wozniakowski)アルゴリズム．

数値総和および乗積

もしレシオテストの結果が1に等しくない場合は，ウィン(Wynn)・イプシロン法が数列の部分和または部分積に適用される．

それ以外はオイラー・マクローリン(Euler-Maclaurin)総和がIntegrateまたは NIntegrateとともに使用される．

微分方程式数値解法

常微分方程式には，NDSolveはデフォルトでLSODA手法を用い，NDSolveは非剛性アダムズ(Adams)法と剛性ギア(Gear)後退微分法とを交互に切り換える．

線形境界値問題ではゲルファンド・ロクチェフスキー(Gel'fand-Lokutsiyevskii)追跡法が使用される．

微分代数方程式では反復BDF（後退微分式）とニュートン反復法に基づいたIDAが使われる．

次元の偏微分方程式では線分法が使用される．

NDSolveは文献に載っているほとんどの既知のアルゴリズムを網羅する明示的Method設定をサポートする．

NDSolveとその関連関数のコードは約1400ページに及ぶ．

近似方程式の解法および最適化

多項式の根はジェンキンス・トラウブ(Jenkins-Traub)アルゴリズムに基づく．

疎な線形システムではSolveおよび NSolveはほとんどの場合はマルコウィツ(Markowitz)積とガウス分解に基づいて複数の効果的数値解法を使用する．(約250ページのコード)．

代数方程式系では，NSolveは効率的な単項式の順序付けを用いて数値グレブナー(Gröbner)基底を計算し，固有系法で数値根を抽出する．

FindRootは減衰ニュートン法，割線法およびブレント(Brent)法を使用する．

Method->Automaticで初期値が2つの場合は，FindMinimumはブレントの主軸法を使う．各変数に初期値がそれぞれ1つときは，FindMinimumは大きな系用にメモリ変形を限定したBFGS擬似ニュートン法を使う．

もし最小化する関数が平方和である場合は， FindMinimumはレベンベルグ・マルカン(Levenberg-Marquant)法(Method->LevenbergMarquant)を使用する．

LinearProgrammingはシンプレックス法と改良シンプレックス法を，またMethod->"InteriorPoint"では主双対内点法を使う．

線形の場合は，NMinimizeとNMaximizeはLinearProgrammingと同じ方法を使う．非線形の場合は，特に整数変数が存在するときは，微分進化法で補強されたネルダー・ミード(Nelder-Mead)法が用いられる.

データ処理

Fourierはデータ長を素因数分解するFFT法を使用する．素因数が大きい場合，漸近複雑度の維持のため高速たたみ込み法が使用される．

実数入力に対してはFourierは実変換法を使用する．

ListConvolveおよびListCorrelateは，可能な限り，FFT法を使用する．厳密な整数入力に対しては，厳密な整数結果の演繹のため十分な桁数が計算される．

InterpolatingFunctionはラグランジュ(Lagrange)またはエルミート(Hermite)補間多項式を構成する分割差分を使用する．

Fitは特異値分解を使う．FindFitは線形最小二乗法には同じく特異値分解を，非線形最小二乗にはLevenberg-Marquardt法を，その他のノルムには一般的なFindMinimum法を使う．

CellularAutomatonはビットパック並行操作をビットスライスで使う．基本的な規則として，絶対的に最適化されたブーリアン関数が使われる．また，全体的な規則としてはジャストインタイムコンパイルのビットパック表が使われる．2次元では可能な場合は疎なビットパック配列がアクティブなクラスタだけをアップデートして使われる．

近似数値線形代数

機会精度行列の処理は，通常は特殊内部表現に変換される．

パターンを含む規則を持つSparseArrayは，連結した配列要素を見付けるために円筒代数分解を使う．疎な配列は，任意のランクのテンソル用に一般化された圧縮された疎な行の形式を使って内部的に保存される．

密な配列の場合は，適当であれば任意精度に拡張されたLAPACK法が使われる．

特定の機械アーキテクチャの最適化にはBLAS（基礎線形代数サブルーチン）技術が使われる．

LUDecomposition，Inverse，RowReduceおよび Detは部分ピボッティングによるガウス消去法を使用する．LinearSolveも同じ方法を使用し，高精度を得るため反復計算させる．

疎な配列の場合は，LinearSolveはUMFPACKマルチフロンタル直接ソルバ法を使い，Method->"Krylov"は不完全なLU因数分解で前提条件を付けられたクリロフ(Krylov)の反復法を使う．EigenvaluesとEigenvectorsはARPACKアーノルディ(Arnoldi)法を使う．