Power Projection Algorithm

2024-05-10) 초안 작성

 

수열 \(w_0, \cdots, w_{n-1}\) 및 FPS(다항식) \(f(x)\)가 주어져 있습니다. \(i=0,\cdots,m-1\)에 대하여, 다음을 전부 계산하시오:

\[ \sum_{j=0}^{n-1} w_j \times [x^j]f(x)^i \]

 

이런게 왜 필요할까요? 어떻게 구할 수 있을까요?

 

1) 사전지식

2) Power Projection \(\mathcal{O}(n \log^2 n + m \log m) \)

3) 두 다항식 \(f,g\)의 합성 \(f(g(x))\) 계산하기 \(\mathcal{O}(n \log^2 n)\)

 

1) 사전지식

 

다음과 같은 내용들을 필요로 합니다.

 

(1) 다항식 및 FPS에 관한 내용들

(2) 다차원 FFT

(3) 생성함수

(4) Bostan-Mori algorithm

 

2) Power Projection \(\mathcal{O}(n \log^2 n + m \log m) \)

 

수열 \(w_0, \cdots, w_{n-1}\) 및 FPS(다항식) \(f(x)\)가 주어져 있다고 가정합시다. 편의를 위하여, \(n\)을 \(2\)의 거듭제곱이라고 가정합시다.

 

\(g(x) = w_{n-1} + w_{n-2} x + \cdots + w_0 x^{n-1}\)라는 다항식을 정의해봅시다. 그렇다면, 저희가 구하려고 하는 값을 다음처럼 적을 수 있습니다.

\[ \sum_{j=0}^{n-1} w_j \times [x^j]f(x)^i = [x^{n-1}]g(x)f(x)^i \]

 

변수가 2개인 FPS를 생각하면 \( g(x)f(x)^i = [y^i] \frac{g(x)}{1-f(x)y} \)가 성립합니다. 왜냐하면, \( \frac{1}{1-cy} = 1 + cy + c^2y^2 + \cdots \)가 성립하기 때문에, 비슷하게 \( \frac{1}{1-f(x)y} = 1 + f(x)y + f(x)^2 y^2 + \cdots \)가 성립하기 때문입니다. 더 나아가서, 다음이 성립합니다.

 

\[ [x^{n-1}]g(x)f(x)^i = [x^{n-1}] [y^i] \frac{g(x)}{1-f(x)y} =[y^i][x^{n-1}]\frac{g(x)}{1-f(x)y} \]

 

\(h(y) = [x^{n-1}]\frac{g(x)}{1-f(x)y} \)로 정의합시다. 저희가 원하는 것은 \(h(y)\)의 \(0,1,\cdots, m-1\)차항의 계수이며, 즉 이는 FPS \( h(y) \) mod \( y^m\) 자체를 구하라는 것과 같게 됩니다. \(P(x,y) = g(x) = w_{n-1} + w_{n-2} x + \cdots + w_0 x^{n-1} , Q(x,y) = 1-f(x)y\)라고 정의합시다. 최종적으로, 저희가 구하고자 하는 것은 다음과 같습니다.

 

\[ h(y) = [x^{n-1}] \frac{P(x,y)}{Q(x,y)} \]

 

유리식의 \(n-1\)번째 계수를 구하는 방법...? 어디서 많이 들어보셨을겁니다. 네, Bostan-Mori algorithm입니다. 그러므로 Power Projection을 계산할때도 Bostan-Mori algorithm을 증명할때 사용한 방법과 유사한 방법을 사용하게 됩니다. 만약 이 밑에 알고리즘 전개과정이 이해가 되지 않으시면 먼저 Bostan-Mori를 숙지하신 후 읽으시는걸 권장드립니다.

 

\[ h(y) = [x^{n-1}] \frac{P(x,y)}{Q(x,y)} = [x^{n-1}] \frac{P(x,y)Q(-x,y)}{Q(x,y)Q(-x,y)} \]

 

\(Q(x,y)Q(-x,y)\)는 \(x\)에 대해서 even function입니다. 왜냐하면, \(Q((-x),y)Q(-(-x),y) = Q(-x,y)Q(x,y) = Q(x,y)Q(-x,y)\)가 성립하기 때문입니다. 다시 말해서, \(x\)의 차수가 홀수라면 그에 대응하는 계수는 무조건 0이 되므로, 적당한 FPS \( Q_{\text{even}} \)이 존재하여 다음이 성립합니다.

\[ Q(x,y)Q(-x,y) = Q_{\text{even}}(x^2,y) \]

마찬가지로 적당한 다항식 \(P_{\text{odd}}, P_{\text{even}}\)이 존재하여 다음이 성립합니다.

\[ P(x,y)Q(-x,y) = x P_{\text{odd}}(x^2,y) + P_{\text{even}}(x^2,y) \]

\[ [x^{n-1}] \frac{P(x,y)Q(-x,y)}{Q(x,y)Q(-x,y)} = [x^{n-1}] x\frac{P_{\text{odd}}(x^2,y)}{ Q_{\text{even}}(x^2,y) } + [x^{n-1}] \frac{P_{\text{even}}(x^2,y)}{ Q_{\text{even}}(x^2,y) } \]

 

\(n\)이 2의 거듭제곱인걸 상기해주세요. \( \frac{P_{\text{even}}(x^2,y)}{ Q_{\text{even}}(x^2,y) } \)는 \(x\)에 대해서 even function이기 때문에 홀수차항의 계수는 무조건 \(0\)이며, \(x^{n-1}\)은 홀수차항입니다. 따라서, 덧셈의 뒷부분값은 무조건 \(0\)이 되어 삭제되고, 다음과 같은 결과를 얻을 수 있습니다.

 

\[ h(y) = [x^{n-1}] \frac{P(x,y)}{Q(x,y)} = [x^{n-1}] x\frac{P_{\text{odd}}(x^2,y)}{ Q_{\text{even}}(x^2,y) } = [x^{n-2}] \frac{P_{\text{odd}}(x^2,y)}{ Q_{\text{even}}(x^2,y)} = [x^{n/2-1}] \frac{P_{\text{odd}}(x,y)}{ Q_{\text{even}}(x,y) } \]

 

한번의 시행을 할때마다 \(n\)이 반으로 줄어들것이고, Bostan-Mori때와 비슷한 이유로 대충 \( \mathcal{O}(n \log n)\)시간에 되겠네요? 와아ㅏㅏㅏㅏ 라고 말하기에는 이릅니다. 다음 부분을 다시 확인해주세요.

 

\[ Q(x,y)Q(-x,y) = Q_{\text{even}}(x^2,y), P(x,y)Q(-x,y) = x P_{\text{odd}}(x^2,y) + P_{\text{even}}(x^2,y) \]

 

두 식 모두 좌변의 식에 대해서, 어떤 두 다항식이 곱해집니다. 만약 두 다항식 모두 \(y\)의 최고차수가 \(c\)라면, 곱해진 결과의 \(y\)의 최고차수는 약 \(2c\)가 되겠지요? 네, 이 방법은 한번의 시행을 할때마다 \(n\)(\(x\)의 최고차수)이 반으로 줄지만, 그와 동시에 \(y\)의 최고차수가 2배로 늘어납니다. 다행인점은, \(x\)의 최고차수 \( \times \) \(y\)의 최고차수가 \(n\)으로 일정하게 유지된다는 점이며, 따라서 한번의 2변수 FPS의 곱셈에는 일정하게 \( \mathcal{O} (n \log n) \)의 시간이 걸립니다(FPS 2개를 곱할때 2차원 FFT가 필요합니다). 한번 할때마다 연산량이 반으로 줄어드는 Bostan-Mori와는 약간 다릅니다. 이러한 iteration을 총 \( \log n\)번 반복하게 되니, 모든 iteration을 도는데 \( \mathcal{O} (n \log^2 n) \)의 시간이 걸립니다.

 

iteration을 전부 돌면 적당한 다항식 \(P^{\prime}(x,y),Q^{\prime}(x,y)\)가 존재하여 다음이 성립하게 됩니다.

\[ h(y) = [x^0] \frac{ P^{\prime}(x,y) }{ Q^{\prime}(x,y) } \]

사실, iteration을 전부 끝냈다면 \(P^{\prime},Q^{\prime}\)는 \(x\)와 독립이 됩니다. 그러므로 그냥 \(P^{\prime}(y), Q^{\prime}(y)\)로 적을 수 있고, 다음이 성립합니다.

\[ h(y) = [x^0] \frac{P^{\prime}(y) }{ Q^{\prime}(y) } = \frac{P^{\prime}(y) }{ Q^{\prime}(y) } \]

저희가 \(h\)에서 필요한 부분은 초기 \(m\)개의 계수일 뿐이므로, \(P^{\prime},Q^{\prime}\)을 mod \(y^m\)을 한 후에 FPS 나눗셈을 적용하면 끝납니다. 당연하지만 여기에는 \(\mathcal{O}(m \log m)\)의 시간이 소모됩니다.

 

결론적으로, Power Projection 알고리즘은 \(\mathcal{O}(n \log^2 n + m \log m) \)에 동작합니다.

 

3) 두 다항식 \(f,g\)의 합성 \(f(g(x))\) 계산하기 \(\mathcal{O}(n \log^2 n)\)

 

먼저 \(f(g(x))\)를 풀어서 적어봅시다. 일반성을 잃지 않고 \(f,g\) 모두 \(n-1\)차 다항식이고 \(n\)이 \(2\)의 거듭제곱이라고 가정합시다. 또한, 적절한 상수 \(c_0,\cdots,c_{n-1}\)이 존재하여 \(f(x) = c_0 + c_1 x + \cdots + c_{n-1} x^{n-1}\)이 성립한다고 가정합시다. 다음이 성립합니다.

\[ \begin{align*} f(g(x)) &= c_0 + c_1 \times g(x) + c_2 \times g(x)^2 + \cdots \\ &= \sum_{i=0}^{n-1} c_i \times g(x)^i \\ &= [y^{n-1}] \sum_{i=0}^{n-1} (c_{n-1} + c_{n-2} y + \cdots + c_0 y^{n-1}) \times (g(x) y)^i   \\ &= [y^{n-1}](c_{n-1} + c_{n-2} y + \cdots + c_0 y^{n-1}) \times \sum_{i=0}^{n-1} (g(x) y)^i \\ &= [y^{n-1}](c_{n-1} + c_{n-2} y + \cdots + c_0 y^{n-1}) \times \sum_{i=0}^{\infty} (g(x) y)^i \\ &= [y^{n-1}] \frac{ c_{n-1} + c_{n-2} y + \cdots + c_0 y^{n-1} }{1-g(x)y} \end{align*}\]

 

이제 Power Projection에서 했었던것을 그대로 하면 됩니다....라고 말하고 싶지만 묘하게 Power Projection때와는 식이 다르기 때문에 그대로 할 수 없습니다. 정확히는, 똑같이 하였을때 시간복잡도가 \(\mathcal{O}(n \log^2 n)\)이 나온다는걸 보장할 수 없습니다. 그래서 다른 방법으로 접근해야합니다.

 

\[ \begin{align*}  f(g(x)) &= f(g(x)) \text{ mod } x^n \\ &= [y^{n-1}] \frac{c_{n-1} + c_{n-2} y + \cdots + c_0 y^{n-1} }{G(x,y)}  \text{ mod } x^n \\ &= [y^{n-1}] \frac{(c_{n-1} + c_{n-2} y + \cdots + c_0 y^{n-1}) G(-x,y) }{ G(x,y) G(-x,y) } \text{ mod } x^n \\ &= [y^{n-1}] \left( \frac{c_{n-1} + c_{n-2} y + \cdots + c_0 y^{n-1}}{g_{\text{even}}(x^2,y)} \right) G(-x,y) \text{ mod } x^n \\ &= [y^{n-1}] \left( \frac{c_{n-1} + c_{n-2} y + \cdots + c_0 y^{n-1}}{g_{\text{even}}(x,y)} \text{ mod } x^{\frac{n}{2}} \right)_{x=x^2} G(-x,y) \text{ mod } x^n \end{align*}\]

 

여기서 \( G(x,y) = 1-g(x)y\), \( g_{\text{even}}(x,y) =G(x,y)G(-x,y) \) 입니다. \(G(x,y)\)를 잘 보면, iteration을 할때마다 \(x\)의 최고차수는 절반으로 줄고, \(y\)의 최고차수는 2배로 늘어납니다. mod \(x^n\)에 대해서 소모되는 시간을 \(T(n)\)이라고 정의하면, 총 소모되는 시간은 \(T(n) = T(n/2) + \mathcal{O}(n \log n) \)이 되며, 따라서 두 함수의 composition을 \(\mathcal{O}(n \log^2 n)\)시간에 계산할 수 있습니다.

 

마치며

 

Power Projection과 두 FPS의 composition이 내용이 따로노는것 같은데 왜 같이 넣었는지 의문을 가지시는 분도 있을것 같습니다. 참고한 논문에 따르면 두 FPS의 composition은 Power Projection의 transposition이라고 하는데, 제가 잘 이해를 못해서 내용이 붕떠버렸습니다(...) 실제로는 두개가 깊게 연관되어 있지만 역자의 얕은 지식으로 어떻게 연관되어 있는지 잘 설명 못한거라고 봐주시면 감사하겠습니다. 미숙해서 죄송합니다.

 

출처는 Codeforces noshi91, Elegia님이 적으신 논문 Power Series Composition in Near-Linear Time(https://arxiv.org/pdf/2404.05177)과 Codeforces maspy님의 블로그 글(https://maspypy.com/fps-%e5%90%88%e6%88%90%e3%83%bb%e9%80%86%e9%96%a2%e6%95%b0%e3%81%ae%e8%a7%a3%e8%aa%ac-1-%e9%80%86%e9%96%a2%e6%95%b0%e3%81%a8-power-projection) 입니다. arxiv에 업로드 된지 한달밖에 안된 따끈따끈한 알고리즘입니다.