article

Free access

Array Permutation by Index-Digit Permutation

Author:

Donald FraserAuthors Info & Claims

Journal of the ACM (JACM), Volume 23, Issue 2

Pages 298 - 309

https://doi.org/10.1145/321941.321949

Published: 01 April 1976 Publication History

PDF eReader

Abstract

An array may be reordered according to a common permutation of the digits of each of its element indices. The digit-reversed reordering which results from common fast Fourier transform (FFT) algorithms is an example. By examination of this class of permutation in detail, very efficient algorithms for transforming very long arrays are developed.

References

[1]

COOl, RAN, W.T., ET XL. What is the fast Fourier transform? IEEE T~ans. or~ Audio and Electro. acoustics A U-15, 2 (1967), 45-55.

Google Scholar

[2]

COOLEY, J.W., XND TUKEY, J.W. An algorithm for the machine calculation of the complex Fourier series. Math. Comput. 19 (1965), 297-301.

Google Scholar

[3]

FaxsEa, D. Incrementing a bit-reversed integer. IEEE Trans. on Computers C-18, 1 (1969), 74.

Google Scholar

[4]

FRASER, D. Array permutation by index-digit permutation. TN-F20, Dep. of Mech. Eng., U. of Sydney, Sydney, Australia, Charles Kolling Res. Lab., 1970.

Google Scholar

[5]

SINGLETON, R.C. A method for computing the fast Fourier transform with auxiliary memory and limited high-speed storage. 1EEE Trans. on Audio and Electroacoustics A U-15, 2 (1967), 91-98.

Google Scholar

Cited By

View all

Liu KXue W(2023)A Novel Compute-Efficient Tridiagonal Solver for Many-Core ArchitecturesIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2022.321476234:1(195-206)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TPDS.2022.3214762
Garrido MGrajal JGustafsson O(2019)Optimum Circuits for Bit-Dimension PermutationsIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2019.289232227:5(1148-1160)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1109/TVLSI.2019.2892322
Garrido M(2018)Multiplexer and Memory-Efficient Circuits for Parallel Bit ReversalIEEE Transactions on Circuits and Systems II: Express Briefs10.1109/TCSII.2018.2880921(1-1)Online publication date: 2018
https://doi.org/10.1109/TCSII.2018.2880921
Show More Cited By

Index Terms

Array Permutation by Index-Digit Permutation
1. Information systems
  1. Information storage systems
    1. Record storage systems
2. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Permutations and combinations

Recommendations

The sorting index and permutation codes

In the combinatorial study of the coefficients of a bivariate polynomial that generalizes both the length and the reflection length generating functions for finite Coxeter groups, Petersen introduced a new Mahonian statistic sor, called the sorting ...
Permutation tableaux and permutation patterns

In this paper we introduce and study a class of tableaux which we call permutation tableaux; these tableaux are naturally in bijection with permutations, and they are a distinguished subset of the -diagrams of Alex Postnikov [A. Postnikov, Webs in ...
On the sign-imbalance of permutation tableaux

Permutation tableaux were introduced by Steingrmsson and Williams. Corteel and Kim defined the sign of a permutation tableau in terms of the number of unrestricted columns. The sign-imbalance of permutation tableaux of length n is the sum of signs over ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 23, Issue 2

April 1976

176 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321941

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1976

Published in JACM Volume 23, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

56
Total Citations
View Citations
1,007
Total Downloads

Downloads (Last 12 months)82
Downloads (Last 6 weeks)13

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Liu KXue W(2023)A Novel Compute-Efficient Tridiagonal Solver for Many-Core ArchitecturesIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2022.321476234:1(195-206)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TPDS.2022.3214762
Garrido MGrajal JGustafsson O(2019)Optimum Circuits for Bit-Dimension PermutationsIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2019.289232227:5(1148-1160)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1109/TVLSI.2019.2892322
Garrido M(2018)Multiplexer and Memory-Efficient Circuits for Parallel Bit ReversalIEEE Transactions on Circuits and Systems II: Express Briefs10.1109/TCSII.2018.2880921(1-1)Online publication date: 2018
https://doi.org/10.1109/TCSII.2018.2880921
Dieguez AAmor MLobeiras JDoallo R(2018)Solving Large Problem Sizes of Index-Digit Algorithms on GPUIEEE Transactions on Computers10.1109/TC.2017.272387967:1(86-101)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1109/TC.2017.2723879
Garrido MQureshi FTakala JGustafsson O(2018)Hardware architectures for the fast Fourier transformHandbook of Signal Processing Systems10.1007/978-3-319-91734-4_17(613-647)Online publication date: 14-Oct-2018
https://doi.org/10.1007/978-3-319-91734-4_17
Kim MNigam APaul GFlynn RRodrigue G(2016)Disk Interleaving and Very Large Fast Fourier TransformsThe International Journal of Supercomputing Applications10.1177/1094342087001003071:3(75-96)Online publication date: 16-Sep-2016
https://doi.org/10.1177/109434208700100307
Lobeiras JAmor MDoallo R(2016)Designing Efficient Index-Digit Algorithms for CUDA GPU ArchitecturesIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2015.245071827:5(1331-1343)Online publication date: 1-May-2016
https://dl.acm.org/doi/10.1109/TPDS.2015.2450718
Geraci JSacco S(2012)A transpose-free in-place SIMD optimized FFTACM Transactions on Architecture and Code Optimization10.1145/2355585.23555969:3(1-21)Online publication date: 5-Oct-2012
https://dl.acm.org/doi/10.1145/2355585.2355596
Gustavson FKarlsson LKågström B(2012)Parallel and Cache-Efficient In-Place Matrix Storage Format ConversionACM Transactions on Mathematical Software10.1145/2168773.216877538:3(1-32)Online publication date: 1-Apr-2012
https://dl.acm.org/doi/10.1145/2168773.2168775
Karas PSvoboda DZemčík P(2012)GPU optimization of convolution for large 3-d real imagesProceedings of the 14th international conference on Advanced Concepts for Intelligent Vision Systems10.1007/978-3-642-33140-4_6(59-71)Online publication date: 4-Sep-2012
https://dl.acm.org/doi/10.1007/978-3-642-33140-4_6
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

The sorting index and permutation codes

Permutation tableaux and permutation patterns

On the sign-imbalance of permutation tableaux

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations