합성곱 (Convolution)

위키피디아에 있는 합성곱에 대한 요약설명은 “하나의 함수와 또 다른 함수를 반전 이동한 값을 곱한 다음, 구간에 대해 적분하여 새로운 함수를 구하는 수학 연산자” 이다.
이것을 식으로 정의하면, 함수 f와 g의 합성곱 f*g는 $ (f * g )(t) = \int_{-\infty}^\infty f(\tau) g(t - \tau)\, d\tau $ 으로 쓸수 있다.
하지만 이렇게 연속함수를 대상으로 하는 것은 수학이나 신호처리에서 주로 쓰이는 형태이고, PS에서 필요한 것은 이산함수 또는 수열간의 합성곱이다. 다음처럼 표기할수 있다
- $ (f * g)(m) = \sum_n {f(n) g(m - n)} $
- 수열의 경우는 f(i)를 수열의 i번째 항을 나타내는 이산함수가 된다고 생각하면 된다.
이러한 이산합성곱을 구하는 것은 이산 푸리에 변환을 이용해서 효율적으로 구할수 있다. 고속 푸리에 변환 (Fast Fourier Transform, FFT)를 사용하면 길이가 n인 두개의 수열에 대해서 O(nlogn)에 합성곱을 구할수 있다.
- 이것의 응용은 고속 푸리에 변환 (Fast Fourier Transform, FFT)를 참고. 대표적으로는 두개의 다항식을 곱한 결과식의 계수, 큰수의 곱셈, 두 수열의 원소들의 모든 pairwise sum 등등이 있다.
이제 원래의 합성곱에서 중간에 들어가는 연산자를 일반화해서 확장시켜보자.
- 원래 식을 바꿔쓰면, $(f * g)(m) = \sum_n{f(n) g(m-n)} = \sum_{i+j=m} {f(i) g(j)} $ 이 되는데, i+j=m 부분에서 +를 다른 연산자로 치환해서 $(f * g)(m) = \sum_{i★j=m} {f(i) g(j)}$ 으로 확장하는 것이다.
- 보통은 사용되는 연산자 이름을 넣어서 XXX convollution 이라고 부른다. 예를 들어 ★ 에 xor 연산자가 들어가는 경우는 xor convolution, GCD 가 들어가는 경우는 GCD convolution 등으로 부른다. (PS분야 밖에서 이렇게 부르는 것을 잘 보지는 못했다.. PS에서만 쓰이는 용어일수도 있다)
비트 연산자를 사용하는 컨볼루션 (xor/or/and convolution) 의 경우는 Walsh-Hadamard transform을 이용해서 효율적으로 구할수 있다.
- Fast Walsh Hadamard Transform (FWHT)를 사용하면 길이가 n인 두개의 수열에 대해서 O(nlogn)에 convolution을 구할수 있다.
- FFT와 같은 방식으로 이것을 활용하면 두 수열의 원소들에 대한 모든 pairwise xor/or/and 의 합을 구할 수 있다
연산 결과가, 어떤 Poset에서의 least common ancestor나 highest common descendent 로 정의될수 있는 연산자에 대해서는, Zeta transform / Mobius transform 을 이용해서 효율적으로 구할수 있다.
- or, and, gcd, lcm 등의 연산자가 여기에 해당된다
- SOS DP 를 이용해서 zeta/mobius transform을 계산하면, 길이가 n인 두개의 수열에 대해서 O(nlogn)에 convolution을 구할수 있다.