📂알고리즘

수치적 알고리즘에서의 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 $$

위와 같은 덧셈이나 복사와 같은 작업은 굳이 연산으로 세지 않았으나, 문헌에 따라서는 덧셈도 연산에 추가할 수 있고 비트 쉬프팅, 다시 말해 두 배로 곱하는 것도 연산으로 세는 경우도 있다. 다만 행렬대수의 관점에서는 앞서 소개했듯이 곱셈해서 기존 값에 더하는 것, 사실상 곱셈 한 번을 연산으로 세는 것이 일반적이다.