📂アルゴリズム

数値アルゴリズムにおけるflop

用語 ¹

与えられた浮動小数点体系において、加算や乗算などの浮動小数点演算をflop^{floating point operation}という。アルゴリズムのflopを数えることは時間計算量を計算することと似た意味で用いられる。特に行列代数では、次のように与えられた二つの数$x, y$を掛け、エントリ$s$に加えて更新することを一回のflopとみなすことができる。 $$ s \gets s + x \cdot y $$

説明

例えば行列$A \in \mathbb{R}^{m \times n}$について$A^{\top} A$を計算するならば、長さが$m$のベクトルを$n$個内積することになり、長さが$m$の二つのベクトルの内積はそれぞれの成分を掛けて足す演算が$m$回起こることになる。ただし$A^{\top} A$は対称行列であるから、対角成分の上か下のうち一方は別途計算する必要がなく、コピーするだけでよい。内積が必要なエントリの数は$1 + 2 + \cdots + n = {\frac{ n (n+1) }{ 2 }}$であり、そのそれぞれは$m$回の演算が起こるので、$A^{\top} A$を計算するのに必要なflopの数は次の通りである。 $$ {\frac{ 1 }{ 2 }} n \left( n + 1 \right) m $$

上記のような加算やコピーのような作業はあえて演算として数えなかったが、文献によっては加算も演算に加えることができ、ビットシフト、言い換えれば二倍に掛けることも演算として数える場合もある。ただし行列代数の観点からは、先に紹介したように乗算して既存の値に足すこと、事実上乗算一回を演算として数えるのが一般的である。