FHE之NTT（）Matrix-based NTT

Four-step NTT 推导

我们知道，在具体的硬件实现中，我们往往把大规模的数据存储为矩阵的形式，因为这样既方便索引，也方便并行计算。因此我们可以考虑将最初的N个采样值存储为矩阵形式，矩阵大小为N1×N2  (N1,N2∈Z+且N1×N2=N)N_1\times N_2\ \ (N_1,N_2\in Z^+且N_1\times N_2=N)，这样我们就可以多行并行计算。

以16 point NTT为例，如图，我们可以将16 point NTT分解为4个4 point NTT并行计算，提高效率。

image-20230814222749024

PWC NTT

原始公式

z[k]=∑i=0N−1x(i)ωNik mod  p(1)z[k]=\sum^{N-1}_{i=0}x(i)\omega^{ik}_N\ \mod p \tag{1}

where ωN=gp−1Nmod  q\omega_N=g^{\frac{p-1}{N}}\mod q

矩阵分解

现对NN进行如下分解：

N=N1×N2, N1,N2∈Z+(2)N = N_1\times N_2,\ N_1,N_2\in Z^+ \tag{2}

此时输入向量xx可排列为N2×N1N_2\times N_1矩阵，我们采用XX来表示；输出向量zz可排列为N1×N2N_1\times N_2矩阵，我们采用ZZ来表示。

规定下标

将向量转化为矩阵后，我们需要对(1)(1)下标重新规定(reindexing)：

{k=k1+N2k2,  k1∈[0,N2−1]   k2∈[0,N1−1]i =i1+N1i2,   i1∈[0,N1−1]   i2∈[0,N2−1](3)\begin{cases}k=k_1+N_2k_2,\ \ k_1\in[0,N_2-1]\ \ \ k_2\in[0,N_1-1]\\ i\ =i_1+N_1i_2,\ \ \ i_1\in[0,N_1-1]\ \ \ i_2\in[0,N_2-1]\end{cases} \tag{3}

此时输入矩阵可索引为X[i2,i1]X[i_2,i_1]，输出矩阵可索引为Z[k2,k1]Z[k_2,k_1]

注：此处XX和ZZ形状不同，是因为中间需要进行一次转置。

推导

注：为了推导方便，以下公式将省略mod  q\mod q

将(3)(3)式代入(1)(1)式，可得

z[k1+N2k2]=∑i1=0N1−1∑i2=0N2−1x(i1+N1i2)ωN(i1+N1i2)(k1+N2k2)=∑i1=0N1−1∑i2=0N2−1x(i1+N1i2)ωNi1k1ωNi1N2k2ωNi2N1k1ωNi2k2N1N2(4)\begin{align} z[k_1+N_2k_2]&=\sum^{N_1-1}_{i_1=0}\sum^{N_2-1}_{i_2=0}x(i_1+N_1i_2)\omega_N^{(i_1+N_1i_2)(k_1+N_2k_2)}\\&=\sum^{N_1-1}_{i_1=0}\sum^{N_2-1}_{i_2=0}x(i_1+N_1i_2)\omega_N^{i_1k_1}\omega_N^{i_1N_2k_2}\omega_N^{i_2N_1k_1}\omega_N^{i_2k_2N_1N_2} \end{align} \tag{4}

注意到{N=N1×N2,ωN=gp−1N=gp−1N1×N2\begin{cases}N=N_1\times N_2,\\ \omega_N=g^{\frac{p-1}{N}}=g^{\frac{p-1}{N_1\times N_2}}\end{cases}，所以(4)(4)式中的各个ω\omega可化简为

{ωNi1k1=ωN1N2i1k1ωni1N2k2=ωN1i1k2ωni2N1k1=ωN2i2k1ωNi2k2N1N2=g(p−1)i2k2≡1(5)\begin{cases}\omega_N^{i_1k_1}=\omega^{i_1k_1}_{N_1N_2}\\\omega^{i_1N_2k_2}_{n}=\omega^{i_1k_2}_{N_1}\\\omega^{i_2N_1k_1}_{n}=\omega^{i_2k_1}_{N_2}\\\omega^{i_2k_2N_1N_2}_N=g^{(p-1)i_2k_2}\equiv1\end{cases} \tag{5}

将(5)(5)代入(4)(4)可得

z[k1+N2k2]=∑i1=0N1−1∑i2=0N2−1x(i1+N1i2)ωN1N2i1k1ωN1i1k2ωN2i2k1=∑i1=0N1−1[ωN1N2i1k1⏟dot product⋅∑i2=0N2−1x(i1+N1i2)ωN2i2k1⏟N2-point PWC NTT]ωN1i1k2⏟N1-point PWC NTT(6)\begin{align} z[k_1+N_2k_2]&=\sum^{N_1-1}_{i_1=0}\sum^{N_2-1}_{i_2=0}x(i_1+N_1i_2)\omega_{N_1N_2}^{i_1k_1}\omega^{i_1k_2}_{N_1}\omega^{i_2k_1}_{N_2}\\ &=\underbrace{\sum^{N_1-1}_{i_1=0}[\underbrace{\omega_{N_1N_2}^{i_1k_1}}_{\text{dot product}}\cdot\underbrace{\sum^{N_2-1}_{i_2=0}x(i_1+N_1i_2)\omega^{i_2k_1}_{N_2}}_{N_2\text{-point PWC NTT}}]\omega^{i_1k_2}_{N_1}}_{N_1\text{-point PWC NTT}} \end{align} \tag{6}

观察

  • 逐列进行PWC NTT

    注意到(6)(6)式中的∑i2=0N2−1x(i1+N1i2)ωN2i2k1\sum^{N_2-1}_{i_2=0}x(i_1+N_1i_2)\omega^{i_2k_1}_{N_2}即为对N2× N1N_2\times\ N_1矩阵XX的第i1i_1列进行PWC NTT变换

    记变换后的矩阵为YY（YY亦为N2×N1N_2\times N_1矩阵）

  • 点乘旋转因子(twisting factors)

    而后矩阵YY逐个元素乘上旋转因子ωN1N2i1k1\omega^{i_1k_1}_{N_1N_2}

    Y′[k1,i1]=ωN1N2i1k1Y[k1,i1] (7)Y'[k_1,i_1]=\omega^{i_1k_1}_{N_1N_2}Y[k_1,i_1]\ \tag{7}

  • 逐行进行PWC NTT

    将(7)(7)代入(6)(6)式可得

    z[k1+N2k2]=∑i1=0N1−1Y′[k1,i1]ωN1i1k2(8)z[k_1+N_2k_2]=\sum^{N_1-1}_{i_1=0}Y'[k_1,i_1]\omega^{i_1k_2}_{N_1} \tag{8}

    该式实为对矩阵Y′Y'的第k1k_1行进行PWC NTT变换。

  • 转置
    注意到(8)(8)中等号右边得到的矩阵形状为N2×N1N_2\times N_1，要想得到最终的输出矩阵Z(N1×N2)Z(N_1\times N_2)，我们需要再对等号右边的矩阵进行转置，得到N1×N2N_1\times N_2矩阵。

总结

PWC NTT的矩阵分解版本步骤如下：

  • 将NN维向量排成N2×N1N_2\times N_1矩阵

  • 逐列执行PWC NTT

  • 点乘twisting factors

  • 逐行执行PWC NTT

  • 转置

PWC INTT

原始公式

z[k]=N−1∑i=0N−1x(i)ωN−ik mod  p(1)z[k]=N^{-1}\sum^{N-1}_{i=0}x(i)\omega^{-ik}_N\ \mod p \tag{1}

where ωN=gp−1Nmod  q\omega_N=g^{\frac{p-1}{N}}\mod q

注：N−1N^{-1}指的是NN在mod  q\mod q意义下的乘法逆元。

推导

注意到PWC INTT和PWC NTT的公式基本无异，只不过NN次单位根取的是ωN\omega_{N}的乘法逆元ωN−1\omega_{N}^{-1}，以及最后需要和NN的乘法逆元相乘。由于求乘法逆元的运算性质和求-1次方相同，于是

N−1=(N1N2)−1=N1−1N2−1(2)N^{-1}=(N_1N_2)^{-1}=N_1^{-1}N_2^{-1} \tag{2}

最终(1)(1)式可化为

z[k1+N2k2]=N1−1N2−1∑i1=0N1−1∑i2=0N2−1x(i1+N1i2)ωN1N2−i1k1ωN1−i1k2ωN2−i2k1=N1−1∑i1=0N1−1[ωN1N2−i1k1⏟dot product⋅N2−1∑i2=0N2−1x(i1+N1i2)ωN2−i2k1⏟N2-point PWC INTT]ωN1−i1k2⏟N1-point PWC INTT(3)\begin{align} z[k_1+N_2k_2]&= N_1^{-1}N_2^{-1}\sum^{N_1-1}_{i_1=0}\sum^{N_2-1}_{i_2=0}x(i_1+N_1i_2)\omega_{N_1N_2}^{-i_1k_1}\omega^{-i_1k_2}_{N_1}\omega^{-i_2k_1}_{N_2}\\&= \underbrace{N_1^{-1}\sum^{N_1-1}_{i_1=0}[\underbrace{\omega_{N_1N_2}^{-i_1k_1}}_{\text{dot product}}\cdot\underbrace{N_2^{-1}\sum^{N_2-1}_{i_2=0}x(i_1+N_1i_2)\omega^{-i_2k_1}_{N_2}}_{N_2\text{-point PWC INTT}}]\omega^{-i_1k_2}_{N_1}}_{N_1\text{-point PWC INTT}} \end{align} \tag{3}

观察与总结

我们进行与PWC NTT类似的观察，可得PWC INTT的矩阵分解版本步骤如下：

  • 将NN维向量排成N2×N1N_2\times N_1矩阵

  • 逐列执行PWC INTT

  • 点乘twisting factors

  • 逐行执行PWC INTT

  • 转置

NWC NTT

原始公式

z[k]=∑i=0N−1x(i)γ2NiωNik mod  p(1)z[k]=\sum^{N-1}_{i=0}x(i)\gamma_{2N}^i\omega^{ik}_N\ \mod p \tag{1}

where

{ωN=gp−1Nmod  pγ2N=ωNmod  p=gp−12Nmod  p\begin{cases}\omega_N=g^{\frac{p-1}{N}}\mod p\\ \gamma_{2N}=\sqrt{\omega_N} \mod p=g^{\frac{p-1}{2N}}\mod p\end{cases}

矩阵分解

现对NN进行如下分解：

N=N1×N2, N1,N2∈Z+(2)N = N_1\times N_2,\ N_1,N_2\in Z^+ \tag{2}

此时输入向量xx可排列为N2×N1N_2\times N_1矩阵，我们采用XX来表示；输出向量zz可排列为N1×N2N_1\times N_2矩阵，我们采用ZZ来表示。

规定下标

将向量转化为矩阵后，我们需要对(1)(1)下标重新规定(reindexing)：

{k=k1+N2k2,  k1∈[0,N2−1]   k2∈[0,N1−1]i =i1+N1i2,   i1∈[0,N1−1]   i2∈[0,N2−1](3)\begin{cases}k=k_1+N_2k_2,\ \ k_1\in[0,N_2-1]\ \ \ k_2\in[0,N_1-1]\\ i\ =i_1+N_1i_2,\ \ \ i_1\in[0,N_1-1]\ \ \ i_2\in[0,N_2-1]\end{cases} \tag{3}

此时输入矩阵可索引为X[i2,i1]X[i_2,i_1]，输出矩阵可索引为Z[k2,k1]Z[k_2,k_1]

注：此处XX和ZZ形状不同，是因为中间需要进行一次转置。

推导

注：为了推导方便，以下公式将省略mod  q\mod q

将(3)(3)式代入(1)(1)式，可得

z[k1+N2k2]=∑i1=0N1−1∑i2=0N2−1x(i1+N1i2)γ2Ni1+N1i2ωN(i1+N1i2)(k1+N2k2)=∑i1=0N1−1∑i2=0N2−1x(i1+N1i2)γ2Ni1γ2NN1i2ωNi1k1ωNi1N2k2ωNi2N1k1ωNi2k2N1N2(4)\begin{align} z[k_1+N_2k_2]&=\sum^{N_1-1}_{i_1=0}\sum^{N_2-1}_{i_2=0}x(i_1+N_1i_2)\gamma_{2N}^{i_1+N_1i_2}\omega_N^{(i_1+N_1i_2)(k_1+N_2k_2)}\\&=\sum^{N_1-1}_{i_1=0}\sum^{N_2-1}_{i_2=0}x(i_1+N_1i_2)\gamma^{i_1}_{2N}\gamma^{N_1i_2}_{2N}\omega_N^{i_1k_1}\omega_N^{i_1N_2k_2}\omega_N^{i_2N_1k_1}\omega_N^{i_2k_2N_1N_2} \end{align} \tag{4}

注意到{N=N1×N2,ωN=gp−1N=gp−1N1×N2γ2N=gp−12N1×2N2\begin{cases}N=N_1\times N_2,\\ \omega_N=g^{\frac{p-1}{N}}=g^{\frac{p-1}{N_1\times N_2}}\\\gamma_{2N}=g^{\frac{p-1}{2N_1\times2N_2}}\end{cases}，所以(4)(4)式中的各个ω\omega可化简为

{ωNi1k1=ωN1N2i1k1ωni1N2k2=ωN1i1k2ωni2N1k1=ωN2i2k1ωNi2k2N1N2=g(p−1)i2k2≡1{γ2Ni1=γ2Ni1γ2NN1i2=γ2N2i2(5)\begin{cases}\omega_N^{i_1k_1}=\omega^{i_1k_1}_{N_1N_2}\\\omega^{i_1N_2k_2}_{n}=\omega^{i_1k_2}_{N_1}\\\omega^{i_2N_1k_1}_{n}=\omega^{i_2k_1}_{N_2}\\\omega^{i_2k_2N_1N_2}_N=g^{(p-1)i_2k_2}\equiv1\end{cases}\begin{cases}\gamma^{i_1}_{2N}=\gamma^{i_1}_{2N}\\\gamma^{N_1i_2}_{2N}=\gamma^{i_2}_{2N_2}\end{cases} \tag{5}

将(5)(5)代入(6)(6)可得

z[k1+N2k2]=∑i1=0N1−1∑i2=0N2−1x(i1+N1i2)γ2Ni1γ2N2i2ωN1N2i1k1ωN1i1k2ωN2i2k1=∑i1=0N1−1[ωN1N2i1k1γ2Ni1⏟dot product⋅∑i2=0N2−1x(i1+N1i2)γ2N2i2ωN2i2k1⏟N2-point NWC NTT]ωN1i1k2⏟N1-point PWC NTT(6)\begin{align} z[k_1+N_2k_2]&=\sum^{N_1-1}_{i_1=0}\sum^{N_2-1}_{i_2=0}x(i_1+N_1i_2)\gamma^{i_1}_{2N}\gamma^{i_2}_{2N_2}\omega_{N_1N_2}^{i_1k_1}\omega^{i_1k_2}_{N_1}\omega^{i_2k_1}_{N_2}\\ &=\underbrace{\sum^{N_1-1}_{i_1=0}[\underbrace{\omega_{N_1N_2}^{i_1k_1}\gamma^{i_1}_{2N}}_{\text{dot product}}\cdot\underbrace{\sum^{N_2-1}_{i_2=0}x(i_1+N_1i_2)\gamma^{i_2}_{2N_2}\omega^{i_2k_1}_{N_2}}_{N_2\text{-point NWC NTT}}]\omega^{i_1k_2}_{N_1}}_{N_1\text{-point PWC NTT}} \end{align} \tag{6}

观察

  • 逐列进行NWC NTT

    注意到(6)(6)式中的∑i2=0N2−1x(i1+N1i2)γ2N2i2ωN2i2k1\sum^{N_2-1}_{i_2=0}x(i_1+N_1i_2)\gamma^{i_2}_{2N_2}\omega^{i_2k_1}_{N_2}即为对N2× N1N_2\times\ N_1矩阵XX的第i1i_1列进行NWC NTT变换

    记变换后的矩阵为YY（YY亦为N2×N1N_2\times N_1矩阵）

  • 点乘旋转因子(twisting factors)

    而后矩阵YY逐个元素乘上旋转因子ωN1N2i1k1γ2Ni1\omega^{i_1k_1}_{N_1N_2}\gamma^{i_1}_{2N}

    Y′[k1,i1]=ωN1N2i1k1γ2Ni1Y[k1,i1] (7)Y'[k_1,i_1]=\omega^{i_1k_1}_{N_1N_2}\gamma^{i_1}_{2N}Y[k_1,i_1]\ \tag{7}

  • 逐行进行PWC NTT

    将(7)(7)代入(8)(8)式可得

    z[k1+N2k2]=∑i1=0N1−1Y′[k1,i1]ωN1i1k2(8)z[k_1+N_2k_2]=\sum^{N_1-1}_{i_1=0}Y'[k_1,i_1]\omega^{i_1k_2}_{N_1} \tag{8}

    该式实为对矩阵Y′Y'的第k1k_1行进行PWC NTT变换。

  • 转置
    注意到(8)(8)中等号右边得到的矩阵形状为N2×N1N_2\times N_1，要想得到最终的输出矩阵Z(N1×N2)Z(N_1\times N_2)，我们需要再对等号右边的矩阵进行转置，得到N1×N2N_1\times N_2矩阵。

总结

NWC NTT的矩阵分解版本步骤如下：

  • 将NN维向量排成N2×N1N_2\times N_1矩阵

  • 逐列执行NWC NTT

  • 点乘twisting factors

  • 逐行执行PWC NTT

  • 转置

NWC INTT

原始公式

z[k]=N−1γ2N−k∑i=0N−1x(i)ωN−ik mod  p(1)z[k]=N^{-1}\gamma_{2N}^{-k}\sum^{N-1}_{i=0}x(i)\omega^{-ik}_N\ \mod p \tag{1}

where

{ωN=gp−1Nmod  pγ2N=ωNmod  p=gp−12Nmod  p\begin{cases}\omega_N=g^{\frac{p-1}{N}}\mod p\\ \gamma_{2N}=\sqrt{\omega_N} \mod p=g^{\frac{p-1}{2N}}\mod p\end{cases}

注：

  • N−1N^{-1}指的是NN在mod  q\mod q意义下的乘法逆元。

  • 与NWC NTT不同，NWC INTT的γ\gamma系数是在执行INTT之后再乘上去的，属于post processing，而不是对输入进行pre processing。

矩阵分解

现对NN进行如下分解：

N=N1×N2, N1,N2∈Z+(2)N = N_1\times N_2,\ N_1,N_2\in Z^+ \tag{2}

此时输入向量xx可排列为N2×N1N_2\times N_1矩阵，我们采用XX来表示；输出向量zz可排列为N1×N2N_1\times N_2矩阵，我们采用ZZ来表示。

规定下标

将向量转化为矩阵后，我们需要对(1)(1)下标重新规定(reindexing)：

{k=k1+N2k2,  k1∈[0,N2−1]   k2∈[0,N1−1]i =i1+N1i2,   i1∈[0,N1−1]   i2∈[0,N2−1](3)\begin{cases}k=k_1+N_2k_2,\ \ k_1\in[0,N_2-1]\ \ \ k_2\in[0,N_1-1]\\ i\ =i_1+N_1i_2,\ \ \ i_1\in[0,N_1-1]\ \ \ i_2\in[0,N_2-1]\end{cases} \tag{3}

此时输入矩阵可索引为X[i2,i1]X[i_2,i_1]，输出矩阵可索引为Z[k2,k1]Z[k_2,k_1]

注：此处XX和ZZ形状不同，是因为中间需要进行一次转置。

推导

注：为了推导方便，以下公式将省略mod  q\mod q

将(3)(3)式代入(1)(1)式，可得

z[k1+N2k2]=N−1γ2N−(k1+N2k2)∑i1=0N1−1∑i2=0N2−1x(i1+N1i2)ωN−(i1+N1i2)(k1+N2k2)=N−1∑i1=0N1−1∑i2=0N2−1x(i1+N1i2)γ2N−k1γ2N−N2k2ωN−i1k1ωN−i1N2k2ωN−i2N1k1ωN−i2k2N1N2(4)\begin{align} z[k_1+N_2k_2]&=N^{-1}\gamma_{2N}^{-(k_1+N_2k_2)}\sum^{N_1-1}_{i_1=0}\sum^{N_2-1}_{i_2=0}x(i_1+N_1i_2)\omega_N^{-(i_1+N_1i_2)(k_1+N_2k_2)}\\ &=N^{-1}\sum^{N_1-1}_{i_1=0}\sum^{N_2-1}_{i_2=0}x(i_1+N_1i_2)\gamma^{-k_1}_{2N}\gamma^{-N_2k_2}_{2N}\omega_N^{-i_1k_1}\omega_N^{-i_1N_2k_2}\omega_N^{-i_2N_1k_1}\omega_N^{-i_2k_2N_1N_2} \end{align} \tag{4}

注意到{N=N1×N2,ωN−1=g−p−1N=g−p−1N1×N2γ2N−1=g−p−12N1×2N2\begin{cases}N=N_1\times N_2,\\ \omega_N^{-1}=g^{-\frac{p-1}{N}}=g^{-\frac{p-1}{N_1\times N_2}}\\\gamma_{2N}^{-1}=g^{-\frac{p-1}{2N_1\times2N_2}}\end{cases}，所以(4)(4)式中的各个ω\omega可化简为

{ωN−i1k1=ωN1N2−i1k1ωn−i1N2k2=ωN1−i1k2ωn−i2N1k1=ωN2−i2k1ωN−i2k2N1N2=g−(p−1)i2k2≡1{γ2N−i1=γ2N−k1γ2N−N2k2=γ2N1−k2(5)\begin{cases}\omega_N^{-i_1k_1}=\omega^{-i_1k_1}_{N_1N_2}\\\omega^{-i_1N_2k_2}_{n}=\omega^{-i_1k_2}_{N_1}\\\omega^{-i_2N_1k_1}_{n}=\omega^{-i_2k_1}_{N_2}\\\omega^{-i_2k_2N_1N_2}_N=g^{-(p-1)i_2k_2}\equiv1\end{cases}\begin{cases}\gamma^{-i_1}_{2N}=\gamma^{-k_1}_{2N}\\\gamma^{-N_2k_2}_{2N}=\gamma^{-k_2}_{2N_1}\end{cases} \tag{5}

另外，正如其数学表示，求乘法逆元的运算性质和求−1-1次方是一样的。这意味着

N−1=(N1N2)−1=N1−1N2−1(6)N^{-1}=(N_1N_2)^{-1}=N_1^{-1}N_2^{-1} \tag{6}

将(5)(5)和(6)(6)代入(4)(4)可得

z[k1+N2k2]=N1−1N2−1γ2N−k1γ2N1−k2∑i1=0N1−1∑i2=0N2−1x(i1+N1i2)ωN1N2−i1k1ωN1−i1k2ωN2−i2k1=N1−1∑i1=0N1−1[ωN1N2−i1k1γ2N−k1⏟dot product⋅N2−1∑i2=0N2−1x(i1+N1i2)ωN2−i2k1⏟N2-point PWC INTT]ωN1−i1k2γ2N1−k2⏟N1-point NWC INTT(7)\begin{align} z[k_1+N_2k_2]&=N_1^{-1}N_2^{-1}\gamma^{-k_1}_{2N}\gamma^{-k_2}_{2N_1}\sum^{N_1-1}_{i_1=0}\sum^{N_2-1}_{i_2=0}x(i_1+N_1i_2)\omega_{N_1N_2}^{-i_1k_1}\omega^{-i_1k_2}_{N_1}\omega^{-i_2k_1}_{N_2}\\ &=\underbrace{N_1^{-1}\sum^{N_1-1}_{i_1=0}[\underbrace{\omega_{N_1N_2}^{-i_1k_1}\gamma^{-k_1}_{2N}}_{\text{dot product}}\cdot \underbrace{N_2^{-1}\sum^{N_2-1}_{i_2=0}x(i_1+N_1i_2)\omega^{-i_2k_1}_{N_2}}_{N_2\text{-point PWC INTT}}]\omega^{-i_1k_2}_{N_1}\gamma^{-k_2}_{2N_1}}_{N_1\text{-point NWC INTT}} \end{align} \tag{7}

观察与总结

我们进行与NWC NTT类似的观察，可以发现NWC INTT的矩阵分解步骤为：

  • 将NN维向量排成N2×N1N_2\times N_1矩阵

  • 逐列执行PWC INTT

  • 点乘twisting factors

  • 逐行执行NWC INTT

  • 转置

总结

在将NN维向量排成N2×N1N_2\times N_1矩阵后，各个版本的NTT、INTT运算步骤如下：

  • PWC NTT：逐列PWC NTT→点乘→逐行PWC NTT→转置
  • PWC INTT：逐列PWC INTT→点乘→逐行PWC INTT→转置
  • NWC NTT：逐列NWC NTT→点乘→逐行PWC INTT→转置
  • NWC INTT：逐列PWC INTT→点乘→逐行NWC INTT→转置

注意NWC矩阵分解后的子运算中既有NWC，又有PWC。