ps:convolution
합성곱 (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을 구할수 있다.
ps/convolution.txt · 마지막으로 수정됨: 2023/11/15 03:08 저자 teferi
토론