{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:35:52Z","timestamp":1787333752999,"version":"3.56.0"},"reference-count":26,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","funder":[{"DOI":"10.13039\/501100003246","name":"Dutch Research Council","doi-asserted-by":"crossref","award":["EINF-1158"],"award-info":[{"award-number":["EINF-1158"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2023,12,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We present a parallel algorithm for the fast Fourier transform (FFT) in higher dimensions. This algorithm generalizes the cyclic-to-cyclic one-dimensional parallel algorithm to a cyclic-to-cyclic multidimensional parallel algorithm while retaining the property of needing only a single all-to-all communication step. This is under the constraint that we use at most [Formula: see text] processors for an FFT on an array with a total of [Formula: see text] elements, irrespective of the dimension [Formula: see text] or the shape of the array. The only assumption we make is that [Formula: see text] is sufficiently composite. Our algorithm starts and ends in the same data distribution. We present our multidimensional implementation FFTU which utilizes the sequential FFTW program for its local FFTs, and which can handle any dimension [Formula: see text]. We obtain experimental results for [Formula: see text] using MPI on up to 4096 cores of the supercomputer Snellius, comparing FFTU with the parallel FFTW program and with PFFT and heFFTe. These results show that FFTU is competitive with the state of the art and that it allows one to use a larger number of processors, while keeping communication limited to a single all-to-all operation. For arrays of size [Formula: see text] and [Formula: see text], FFTU achieves a speedup of a factor 149 and 176, respectively, on 4096 processors.<\/jats:p>","DOI":"10.1137\/22m1487242","type":"journal-article","created":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T04:20:21Z","timestamp":1702009221000},"page":"C330-C347","source":"Crossref","is-referenced-by-count":4,"title":["Minimizing Communication in the Multidimensional FFT"],"prefix":"10.1137","volume":"45","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-1031-7226","authenticated-orcid":true,"given":"Thomas","family":"Koopman","sequence":"first","affiliation":[{"name":"Software Science, Radboud University, P.O. Box 9010, 6500 GL Nijmegen, The Netherlands."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9854-4481","authenticated-orcid":true,"given":"Rob H.","family":"Bisseling","sequence":"additional","affiliation":[{"name":"Mathematical Institute, Utrecht University, P.O. Box 80010, 3508 TA Utrecht, The Netherlands."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2023,12,8]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-50371-0_19"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780198788348.001.0001"},{"key":"ref3","doi-asserted-by":"crossref","unstructured":"L. S. Blackford , \nJ. Choi , \nA. Cleary , \nE. D\u2019Azevedo , \nJ. Demmel , \nI. Dhillon , \nJ. Dongarra , \nS. Hammarling , \nG. Henry , \nA. Petitet , \nK. Stanley , \nD. Walker , and \nR. C. Whaley  , ScaLAPACK Users\u2019 Guide, SIAM, Philadelphia, 1997, https:\/\/doi.org\/10.1137\/1.9780898719642.","DOI":"10.1137\/1.9780898719642"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.chemphys.2004.06.012"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1965-0178586-1"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2019.02.006"},{"key":"ref7","unstructured":"C. H. Q. Ding , \nR. D. Ferraro , and \nD. B. Gennery  , A portable 3D FFT package for distributed-memory parallel architectures, in Proceedings of the Seventh SIAM Conference on Parallel Processing for Scientific Computing, SIAM, Philadelphia, 1995, pp. 70\u201371."},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827594266891"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2004.840301"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(01)00118-1"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827599355864"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.cpc.2015.10.024"},{"key":"ref13","unstructured":"T. Koopman  , The Tensor Product of Bulk Synchronous Parallel Algorithms, master\u2019s thesis, Utrecht University, Utrecht, The Netherlands, 2022."},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1021\/j100319a003"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(91)90137-A"},{"key":"ref16","unstructured":"N. Li  and \nS. Laizet  , A highly scalable 2D decomposition library and FFT interface, in Proceedings of the Cray User Group 2010 Conference, 2010, pp. 1\u201313."},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1137\/11082748X"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1137\/120885887"},{"key":"ref19","unstructured":"S. Plimpton , \nA. Kohlmeyer , \nP. Coffman , and \nP. Blood  , fftMPI, a library for performing 2d and 3d FFTs in parallel, USDOE, 2018, https:\/\/doi.org\/10.11578\/dc.20201001.68."},{"key":"ref20","unstructured":"S. Plimpton , \nR. Pollock , and \nM. Stevens  , Particle-mesh Ewald and rRESPA for parallel molecular dynamics simulations, in Proceedings of the Eighth SIAM Conference on Parallel Processing for Scientific Computing, SIAM, Philadelphia, 1997."},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1137\/19M1288401"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1038\/s41598-017-09847-1"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2004.840306"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"},{"key":"ref25","doi-asserted-by":"crossref","unstructured":"C. Van Loan  , Computational Frameworks for the Fast Fourier Transform, SIAM, Philadelphia, 1992, https:\/\/doi.org\/10.1137\/1.9781611970999.","DOI":"10.1137\/1.9781611970999"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-013-0262-9"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/22M1487242","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:20:59Z","timestamp":1787332859000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/22M1487242"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,8]]},"references-count":26,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,12,31]]}},"alternative-id":["10.1137\/22M1487242"],"URL":"https:\/\/doi.org\/10.1137\/22m1487242","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,8]]}}}