Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Existence theorems for transforms over finite rings with applications to $2$-D convolution
HTML articles powered by AMS MathViewer

by David P. Maher PDF
Math. Comp. 35 (1980), 757-765 Request permission

Abstract:

An existence theorem for Fourier-like transforms over arbitrary finite commutative rings is proven in a simple fashion. Corollaries for the case of residue class rings over the integers and extensions of those rings follow directly. The theory is applied to construct very fast algorithms for the computation of two-dimensional convolutions over the integers $\bmod M$.
References
  • Ramesh C. Agarwal and C. Sidney Burrus, Number theoretic transforms to implement fast digital convolution, Proc. IEEE 63 (1975), no. 4, 550–560. MR 0451632
  • Ramesh C. Agarwal and Charles S. Burrus, Fast convolution using Fermat number transforms with applications to digital filtering, IEEE Trans. Acoust. Speech Signal Process. ASSP- (1974), no. 2, 87–97. MR 398650
  • Ramesh C. Agarwal and Charles S. Burrus, Fast one-dimensional digital convolution by multidimensional techniques, IEEE Trans. Acoust. Speech Signal Process. ASSP- (1974), no. 1, 1–10. MR 401340
    • R. C. AGARWAL & J. W. COOLEY, "New algorithms for digital convolution," IEEE Trans. Acoust. Speech Signal Processing, v. 25, 1977, pp. 392-409.
  • Rafael C. Gonzalez and Paul Wintz, Digital image processing, Applied Mathematics and Computation, No. 13, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1977. MR 0459042
  • Jørn Justesen, On the complexity of decoding Reed-Solomon codes, IEEE Trans. Inform. Theory IT-22 (1976), no. 2, 237–238. MR 465505, DOI 10.1109/tit.1976.1055516
  • D. Kibler, Necessary and sufficient conditions for the existence of the modular Fourier transform: Comments on “Number theoretic transforms to implement fast digital convolution” (Proc. IEEE 63 (1975), no. 4, 550–560) by R. C. Agarwal and C. S. Burrus, Proc. IEEE 65 (1977), no. 2, 265–267. With a reply by the authors. MR 0490402
  • Serge Lang, Algebra, Addison-Wesley Publishing Co., Inc., Reading, Mass., 1965. MR 0197234
  • David P. Maher, Two-dimensional digital filtering using transforms over extensions of finite rings, Information linkage between applied mathematics and industry, II (Proc. Second Annual Workshop, Monterey, Calif., 1979) Academic Press, New York-London, 1980, pp. 269–278. MR 592274
    • F. J. MacWILLIAMS &. N. J. A. SLOANE, The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 1977.
  • Hideo Murakami, Irving S. Reed, and Lloyd R. Welch, A transform decoder for Reed-Solomon codes in multiple-user communication systems, IEEE Trans. Inform. Theory IT-23 (1977), no. 6, 675–683. MR 469496, DOI 10.1109/tit.1977.1055793
  • Peter J. Nicholson, Algebraic theory of finite Fourier transforms, J. Comput. System Sci. 5 (1971), 524–547. MR 286905, DOI 10.1016/S0022-0000(71)80014-4
    • H. J. NUSSBAUMER, "Digital filtering using pseudo Fermat number transforms," IEEE Trans. Acoust. Speech Signal Processing, v. 25, 1977, pp. 79-83.
  • H. J. Nussbaumer and P. Quandalle, Computation of convolutions and discrete Fourier transforms by polynomial transforms, IBM J. Res. Develop. 22 (1978), no. 2, 134–144. MR 471260, DOI 10.1147/rd.222.0134
  • J. M. Pollard, The fast Fourier transform in a finite field, Math. Comp. 25 (1971), 365–374. MR 301966, DOI 10.1090/S0025-5718-1971-0301966-0
  • Charles M. Rader, Discrete convolutions via Mersenne transforms, IEEE Trans. Comput. C-21 (1972), 1269–1273. MR 438672, DOI 10.1109/t-c.1972.223497
  • Irving S. Reed and T. K. Truong, Complex integer convolutions over a direct sum of Galois fields, IEEE Trans. Inform. Theory IT-21 (1975), no. 6, 657–661. MR 435049, DOI 10.1109/tit.1975.1055471
    • M. C. VANWORMHOUDT, "On number theoretic transforms in residue class rings," IEEE Trans. Acoust. Speech Signal Processing, v. 25, 1977, pp. 585-586. E. VEGH & L. M. LIEBOWITZ, Fast Complex Convolution Using Number Theoretic Transforms, NRL Report 7935, Naval Research Lab., Washington, D.C., 1975, pp. 1-13.
  • S. Winograd, Some bilinear forms whose multiplicative complexity depends on the field of constants, Math. Systems Theory 10 (1976/77), no. 2, 169–180. MR 468322, DOI 10.1007/BF01683270
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC: 10-04, 94B35
  • Retrieve articles in all journals with MSC: 10-04, 94B35
Additional Information
  • © Copyright 1980 American Mathematical Society
  • Journal: Math. Comp. 35 (1980), 757-765
  • MSC: Primary 10-04; Secondary 94B35
  • DOI: https://doi.org/10.1090/S0025-5718-1980-0572853-3
  • MathSciNet review: 572853