FFT

FFT的误差

问题1：已知$\mathbf{a}=\mathbf{M}^{-1}\mathbf{b}$，其中$\mathbf{M}\in \mathbb{C}^{n\times n},\mathbf{b}\in \mathbb{C}^{n}$，这里把$\mathbf{a}$看做多项式系数，$\mathbf{b}$看做n维向量，分析$e=\Vert \mathbf{b}-\mathbf{M}\mathbf{a}\Vert_\infty$的上界？

问题2：已知$\mathbf{a}_1=\mathbf{M}^{-1}\mathbf{b}_1,\mathbf{a}_2=\mathbf{M}^{-1}\mathbf{b}_2$，其中$\mathbf{M}\in \mathbb{C}^{n\times n},\mathbf{b}_1,\mathbf{}_2\in \mathbb{C}^{n}$，分析 $$ e_+=\Vert (\mathbf{b}1+{simd}\mathbf{b}_2)-\mathbf{M}(\mathbf{a}1+{poly}\mathbf{a}2)\Vert\infty\

e_\times=\Vert (\mathbf{b}1\times{simd}\mathbf{b}_2)-\mathbf{M}(\mathbf{a}1\times{poly}\mathbf{a}2)\Vert\infty $$ 两个误差的上界？

回答：显然，误差不好准确估计，但是维数越高，误差的上界应该越大。

对于双精度的FHE运算来说，FFT的运算误差应该可以控制在单精度范围内。