{"entities":{"Q1179208":{"pageid":1189957,"ns":120,"title":"Item:Q1179208","lastrevid":69811959,"modified":"2026-04-13T09:33:25Z","type":"item","id":"Q1179208","labels":{"en":{"language":"en","value":"Bluestein's FFT for arbitrary \\(N\\) on the hypercube"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 24124"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179208$6A02F81D-96F0-4465-B676-154616EFE9CA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bfe31f7500b00d2b520d5952574b5eb10dc2a1fa","datavalue":{"value":{"text":"Bluestein's FFT for arbitrary \\(N\\) on the hypercube","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1179208$5BB2811C-29BF-47D6-B7E8-F62A332B0FAD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8bcfc91f1ae7daf53f9bcb2f49e2bf2578a3f9d6","datavalue":{"value":"0739.65117","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179208$9B0F0611-36C7-47B8-A23A-3D985D65D79F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4ed4ab7a98f3bd2853cd22f604f5f58f5f3ea203","datavalue":{"value":"10.1016/S0167-8191(05)80051-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179208$A059072E-B170-4D7F-93CE-F8F8E56BB343","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"00ae60230d4807f93106d49ac7cc11ba4764b6ee","datavalue":{"value":{"entity-type":"item","numeric-id":187184,"id":"Q187184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179208$FC7D41E5-309B-4313-9308-7C5A1534C6CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"de15b462730bdfb74ce854f637930b057b2cd351","datavalue":{"value":{"entity-type":"item","numeric-id":1101190,"id":"Q1101190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179208$9CD33AA9-83C0-46A7-A1B4-9B4C2D7023F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"625754c58387494e6cba581285a4da28fde496c9","datavalue":{"value":{"entity-type":"item","numeric-id":1050098,"id":"Q1050098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179208$9982DD81-C27C-42CE-9406-ADBBEEFAD967","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"72c46ecbd6d23df7fafe1454f43d35cea10e1ba5","datavalue":{"value":{"entity-type":"item","numeric-id":1179206,"id":"Q1179206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179208$B2021916-2304-428C-906E-96EB260DC979","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"98fa9f5d1cbf39bd049c03486f805e0c0e4480a3","datavalue":{"value":{"entity-type":"item","numeric-id":686368,"id":"Q686368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179208$5FD8E32B-F77F-4F62-8B54-1E0176DDF615","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"eeac13f60c55bdb04ecb49274cc7b24a1688345d","datavalue":{"value":{"entity-type":"item","numeric-id":71527,"id":"Q71527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179208$88BE838E-1457-4F46-81D0-D2545679FFDB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1422b5e3113eee9dc98f0455d275631058399b8b","datavalue":{"value":{"time":"+1992-06-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1179208$A9E9C027-E420-4883-BCB0-8B038F52C1AF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c5c21bc6578f93ff9a9d30d1c36c85f23255dd1e","datavalue":{"value":"Let \\(N>1\\) be an arbitrary integer, not necessarily a power of 2. The algorithm of \\textit{L. I. Bluestein} [A linear filtering approach to the computation of the discrete Fourier transform, 1968 NEREM Record, Boston, MA, Nov. 6-8, 218-219 (1968). Reprinted in: Papers on Digital Signal Processing, ed. A. V. Oppenheim, M.I.T. Press, Cambridge, MA, 171-172 (1969)] for the discrete Fourier transform of length \\(N\\) (\\(DFT(N)\\)) consists the following steps:   1. The \\(DFT(N)\\) is expressed as a Toeplitz matrix-vector-product. 2. This product is imbedded in a cyclic convolution of length \\(2^ r \\geq 2N-2\\). 3. The cyclic convolution is evaluated using \\(DFT(2^ r)\\).   Because of its minimal communication requirements, Bluestein's fast Fourier transformation (\\(FFT\\)) is realized as an algorithm on hypercube architecture. With \\(2^ d\\) processors, an ordered Bluestein \\(FFT\\) requires \\(2d\\) communication cycles with packet length \\(N/2^{d+1}\\). For fine-grain computations, Bluestein's \\(FFT\\) requires \\(20\\log_ 2N\\) computational cycles.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179208$BB19B86C-CE1C-4B30-9071-CAFEF9385C93","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"c4603c40f3b09770fdbb70ee2650f252415f25c5","datavalue":{"value":"65T50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179208$BF6BAA00-D06B-48A3-836B-E195BC8395C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e804577640ebb408257a4a017aaf6a013220e36f","datavalue":{"value":"65Y10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179208$7E306870-FB36-43BE-9506-B498564021A5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e86be34174294608544a1182da5f467ebec211a7","datavalue":{"value":"24124","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179208$DA1F7864-2B73-43E3-BBBB-9768744B7660","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1328eccdc9de6f1faba0b59107ec6c81584a0b77","datavalue":{"value":"fast Fourier transform","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179208$086C7A04-B39C-4A8A-AE6E-405D4BBD8BD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"861e477912a2f75b76d4a0f9628e09b530824106","datavalue":{"value":"discrete Fourier transform","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179208$75265452-1470-4C5D-85B7-2FDD34F70C77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d7e13171f0e301f9a7c03d8101ccbe541e557886","datavalue":{"value":"cyclic convolution","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179208$577DB0B9-1E75-43BD-920A-A57222A5C37A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dbf67db1a10483a090aa8bee6ae2eaaf49d90ac6","datavalue":{"value":"algorithm on hypercube architecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179208$CC359AEF-78F8-4D85-998A-93C45E777C6D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4d0054cc3a88c2f8acf9b2fb2e5da6ab56697903","datavalue":{"value":{"entity-type":"item","numeric-id":222546,"id":"Q222546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179208$BF3DDBF0-35C9-4B73-B1A1-6EEA6B59209C","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179208$6F082274-8470-43CF-8496-0B33DEC53347","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"710709da0a305a8022f12bed52f14bd73a729899","datavalue":{"value":"https://doi.org/10.1016/s0167-8191(05)80051-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1179208$2C2390CD-6DD7-4629-B3C6-05F28C7463C5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7abe11352a5431f7f9f0315f681604be1b7d0bbb","datavalue":{"value":"W2004315237","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179208$27588B5A-7FD4-4BA3-B69B-61F5F2745281","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9aa005cdeda8acb8242f6c2894198da58f2a189","datavalue":{"value":{"entity-type":"item","numeric-id":1195705,"id":"Q1195705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c46fca9266ada7132c9f36ade1e7ee0dc88ef9f","datavalue":{"value":{"amount":"+0.7436445951461792","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1179208$FF38ED54-9382-4EDD-8959-9914D1FA9EB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ac158816bf969ea74047a53337f577f0a6a1695","datavalue":{"value":{"entity-type":"item","numeric-id":3124734,"id":"Q3124734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f6944199a00ded51f08a568c284dff69165b674e","datavalue":{"value":{"amount":"+0.7420626282691956","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1179208$A582E548-CE11-4EE4-B2C3-92FC03F8303D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ced7ec53e612b02a302d6722ea68b898441b6774","datavalue":{"value":{"entity-type":"item","numeric-id":3691042,"id":"Q3691042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ea0fa954a006e747e745c506b1744216c81c8ea","datavalue":{"value":{"amount":"+0.7407545447349548","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1179208$89A2D94A-37F8-4AE1-8BA9-625F40BD7EAE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Bluestein's FFT for arbitrary \\(N\\) on the hypercube","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Bluestein%27s_FFT_for_arbitrary_%5C(N%5C)_on_the_hypercube"}}}}}