Exact deconvolution using number-theoretic transforms (Q1123581)

Let us consider a one- (or two-) dimensional deconvolution problem \(a*x=b\) where * stands for cyclic convolution, a and b are known integer vectors (or matrices) and x is a vector (matrix) of the formal solution in the field of rational numbers \({\mathbb{Q}}\). This solution exists and is unique if and only if the circulant (block) matrix A associated with a is invertible over \({\mathbb{Q}}\), i.e. the determinant \(d=\det A\neq 0\). Using symmetric residue arithmetic modulo an odd integer \(m>1\) and number theoretic transforms (NTTs) the authors present two algorithms which yield the exact solution x without round-off errors. The first algorithm assumes \(m=m_ 1m_ 2...m_ s\) where \(m_ i\), \(i=1,2,...,s\) are relatively prime. Applying the Chinese remainder theorem (CRT) the original problem is converted to s deconvolution problems over residue rings modulo \(m_ i\), \(i=1,...,s\), which are solved in parallel by means of a set of s NTTs. Within this algorithm a new computational scheme is introduced for the CRT reconstruction of the symmetric residue modulo m from the symmetric residues modulo \(m_ i\), \(i=1,...,s\). This scheme resembles a modular analogue of the recursive computation of divided differences. The value of d is obtained as an intermediate result, allowing thus the regularity check \(d\neq 0\) as well. An example of a \(3\times 3\) deconvolution illustrates the above method. The second algorithm is a generalization of the recent result of \textit{M. Morháč} [Comput. Math. Appl. Part A 12, 319-329 (1986; Zbl 0609.65030)] to arbitrary length (not necessarily the 2-radix one), using one NTT modulo m (not necessarily the Fermat number transform) several times. This algorithm assumes the a priori knowledge of \(d\neq 0\).