algorithm - M2(R) 中的多项式乘法？

Question

我试图在 M2(R) 中实现基于 FFT 的乘法算法。基本上是一种算法，它将两个多项式作为输入，元素作为矩阵给出，并构建乘积多项式。然而，即使该算法应该有效，因为它看起来与我之前在常规数字上编写的版本完全相同，但它却没有。系数总是有一点偏差。

我没有找到任何关于 M2(C) 统一性根源的文章，但我发现(在纸上)选择 eps = ((cos(2PI/n) , i sin(2PI/n)) ， ( i sin(2PI/n) , cos(2PI/n)))，我得到了一个很好的循环。

我的方法有问题吗？

代码如下:

struct FFT {

    PolyC To, Aux[17][2], Res[17][2], AC, BC, ResC, ResD, ArgA, ArgB;

    void fft(PolyC V, var depth, var n, PolyC To, MatC step) {
        if(n == 1) {
            To[0] = V[0];
        } else {

            MatC eps = matCHelper.I2;

            //We "split" the poly in 2
            for(var i=0; i<n; i++)
                Aux[depth+1][i&1][i>>1] = V[i];

            //We recursively apply FFT to the components
            fft(Aux[depth+1][0], depth+1, n/2, Res[depth+1][0], step*step);
            fft(Aux[depth+1][1], depth+1, n/2, Res[depth+1][1], step*step);

            //We compute the result for the n roots
            for(var i=0; i<n/2; i++) {
                To[i] = Res[depth+1][0][i] + eps * Res[depth+1][1][i];
                To[n/2+i] = Res[depth+1][0][i] - eps * Res[depth+1][1][i];
                eps = eps * step;
            }
        }
    }

    void FFTMultiply(Poly Res, Poly A, Poly B, var n1, var n2) {

        var M;
        for(M = 1; M <= 2*n1 || M <= 2*n2; M <<= 1);

        for(var i=0; i<n1; i++) ArgA[i] = A[i];
        for(var i=n1; i<M; i++) ArgA[i] = matCHelper.O2;

        for(var i=0; i<n2; i++) ArgB[i] = B[i];
        for(var i=n2; i<M; i++) ArgB[i] = matCHelper.O2;

        MatC step( Complex(cos(2*PI/M), 0) , Complex(0, sin(2*PI/M)),
                   Complex(0, sin(2*PI/M)) , Complex(cos(2*PI/M), 0) );

        fft(ArgA, 0, M, AC, step);
        fft(ArgB, 0, M, BC, step);

        for(var i=0; i<M; i++) {
            RezC[i] = AC[i] * BC[i];
        }

        step.b = -step.b;
        step.c = -step.c;

        fft(RezC, 0, M, RezD, step);

        for(var i=0; i<M; i++) {
            // Now I divided everything by M and copied every element of ResD to Res modulo some number
        }
    }
};

Answer 1

如果您的系数矩阵不与您的矩阵 step 互换，则您不能指望此方法有效。要使其正常工作，请使用与标量 exp(i*2*PI/M) 相乘的对角矩阵。