📂Algorithm

Flop in Numerical Algorithms

Terminology ¹

In a given floating point system, a floating point operation such as addition or multiplication is called a flop. Counting the flops of an algorithm is used in a sense similar to computing time complexity. In particular, in matrix algebra, the following operation of multiplying two given numbers $x, y$ and adding it to an entry $s$ to update it can be regarded as a single flop. $$ s \gets s + x \cdot y $$

Explanation

For example, if we compute $A^{\top} A$ for a matrix $A \in \mathbb{R}^{m \times n}$, we take the inner product of $n$ vectors of length $m$, and the inner product of two vectors of length $m$ requires $m$ operations of multiplying and adding each component. However, since $A^{\top} A$ is a symmetric matrix, one of the parts above or below the diagonal need not be computed separately and only needs to be copied. The number of entries requiring an inner product is $1 + 2 + \cdots + n = {\frac{ n (n+1) }{ 2 }}$, and each requires $m$ operations, so the number of flops needed to compute $A^{\top} A$ is as follows. $$ {\frac{ 1 }{ 2 }} n \left( n + 1 \right) m $$

Operations such as the additions or copies above were not counted as operations, but depending on the literature, addition may also be added to the count, and bit shifting, that is, multiplying by two, may also be counted as an operation. However, from the perspective of matrix algebra, as introduced earlier, it is common to count multiplying and adding to the existing value, in effect a single multiplication, as an operation.