1
$\begingroup$

I have a 2x2 matrix of generating functions which I want to raise to a large power $m$: $$\begin{bmatrix} a(x) & b(x)\\ c(x) & d(x) \end{bmatrix}^m.$$

I then want to retrieve the first $n$ coefficients of each of the resulting generating functions. If I only keep track of the first $n$ coefficients, I can multiply together two generating functions in $O(n \log n)$ time using the fast Fourier transform. Then, with repeated squaring, I can compute the matrix power in $O(n \log n \log m)$ time.

Is it possible to compute this in time faster than $O(n \log \log m)$? For example, might $O(n (\log n + \log m)$ be possible?

The reason it is taking $O(n \log n \log m)$ time is because in each multiplication I need to switch back and forth between real space and Fourier space. But if I only need to transform to Fourier space once that wouldn't be a problem. However, when multiplying polynomials in Fourier space, if you don't have enough samples you get wraparound, and I don't know how to solve that problem.

Are there other techniques I could use?

Thanks!

Improve this question
$\endgroup$
4
  • $\begingroup$ What are the "first" coefficients? The highest order (highest power of $x$) or lowest order? $\endgroup$ Commented Apr 29 at 8:40
  • 1
    $\begingroup$ Please don't append "Edit: more stuff" at the end. Instead, revise the question so it reads well for someone who encounters it for the first time. If you asked the wrong question, delete it. If there was some aspect in the formulation that could have been better, fix it to be better. $\endgroup$ Commented Apr 29 at 8:42
  • $\begingroup$ The "first" coefficients are the lowest order. $\endgroup$ Commented Apr 29 at 22:29
  • $\begingroup$ I'll edit it to read more smoothly, too. $\endgroup$ Commented Apr 29 at 22:30

0

Reset to default

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.