×

Exact deconvolution using number-theoretic transforms. (English) Zbl 0677.65145

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 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\).
Reviewer: V.Veselý

MSC:

65T40 Numerical methods for trigonometric approximation and interpolation
65F30 Other matrix algorithms (MSC2010)
65K10 Numerical optimization and variational techniques
93B15 Realizations from input-output data

Citations:

Zbl 0609.65030
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Howell, J. A., Exact solution of linear equations using residue arithmetic. Algorithm 406, Commun. ACM, 14, 180-184 (1971)
[2] Cabay, S.; Lam, T. P.L., Algorithm 522 ESOLVE, Congruence techniques for the exact solution of integer systems of linear equations, ACM Trans. math. Software, 3, 404-410 (1977) · Zbl 0374.68035
[3] Szabó, N. S.; Tanaka, R. I., Residue Arithmetic and Its Applications to Computer Technology (1967), McGraw-Hill: McGraw-Hill New York · Zbl 0168.15303
[4] Howell, J. A.; Gregory, R. T., An algorithm for solving linear algebraic equations using residue arithmetic. I, II, BIT, 9, 324-337 (1969) · Zbl 0194.18104
[5] Creutzburg, R.; Tasche, M., Number-theoretic transforms of prescribed length, Math. Comput., 47, 693-701 (1986) · Zbl 0612.10001
[6] Nicholson, P. J., Algebraic theory of finite Fourier transforms, J. Comput. System Sci., 5, 524-547 (1971) · Zbl 0222.42012
[7] Pollard, J. M., The fast Fourier transform in a finite field, Math. Comput., 25, 365-374 (1971) · Zbl 0221.12015
[8] Nussbaumer, H. J., Fast Fourier Transform and Convolution Algorithms (1981), Springer: Springer Berlin · Zbl 0599.65098
[9] Morháč, M., Precise deconvolution using the Fermat number transform, Comput. Math. Applic., 12A, 319-329 (1986) · Zbl 0609.65030
[10] Davis, P. J., Circulant Matrices (1979), Wiley: Wiley New York · Zbl 0418.15017
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.