{"entities":{"Q2369946":{"pageid":2380689,"ns":120,"title":"Item:Q2369946","lastrevid":50119703,"modified":"2026-01-13T05:08:30Z","type":"item","id":"Q2369946","labels":{"en":{"language":"en","value":"A new matrix approach to real FFTs and convolutions of length \\(2^k\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5166275"}},"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":"Q2369946$6E10CC3B-BA5F-4A29-8D02-608E620E61BB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"793c37ce1ededd7a3dc58f806cb8891aabfdd05e","datavalue":{"value":{"text":"A new matrix approach to real FFTs and convolutions of length \\(2^k\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2369946$2D861D9C-2DE3-4E95-A26F-11FD708A9594","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fb3c6ce576b3d4803b16bb1bea51f9603d3f25e6","datavalue":{"value":"1138.65112","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2369946$5A3EDD80-E477-41E7-AB4A-C923089DC5DC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b79ece58f33b59758a066cb6b9ee149bab3a2c9a","datavalue":{"value":{"entity-type":"item","numeric-id":167642,"id":"Q167642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2369946$E66DB572-FA4C-4F90-B82A-3E9C0647A1F4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"091c76b3262577e7d9236eade659189d2a570886","datavalue":{"value":{"time":"+2007-06-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2369946$6C583057-884E-4F65-86FA-D71688A86D2F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"66c60145b12801700c38c38d8abf389b1c576880","datavalue":{"value":"With these very interesting results, the authors have broken the record set by \\textit{R. Yavne} [Proc. AFIPS Fall Joint Comput. Conf. 33, 115--125 (1968)] for the lowest exact count of real additions and multiplications to compute a discrete Fourier transform (DFT) of order \\(2^k\\) with \\(k\\geq 8\\). Nowaday, the fast Fourier transform (FFT) of R. Yavne is called split-radix FFT. Using recursive matrix factorization, the authors present modified split-radix FFTs that compute DFTs with real input vectors with about 6\\(\\;(SOT)\\), a new trigonometric matrix for efficient computing of real FFTs and real convolutions of order \\(2^k\\). The new method for computing of real FFTs of order \\(2^k\\) depends on a recursive matrix factorization of SOT and attains fewer arithmetic operations. As an application, these results are used for efficient computation of real convolutions. Finally, it is shown that DFTs of Fermat prime order can be computed in fewer additions than previously available algorithms. Numerical tests show the high performance and numerical stability of these new modified split-radix FFTs. Fortran programs of these FFTs and convolutions are available via internet. Remark of the reviewer: A different approach to these modified split-radix FFTs can be found in \\textit{S. G. Johnson} and \\textit{M. Frigo} [IEEE Trans. Signal Process. 55, No. 1, 111--119 (2007)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2369946$CCA34EF4-235A-443F-B778-61623E7FA863","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":"Q2369946$1EC8A381-3AF0-453F-9FF0-D6D2F443CEDC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"c4603c40f3b09770fdbb70ee2650f252415f25c5","datavalue":{"value":"65T50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2369946$90D8E475-5D8D-47F3-8FA6-16D954B03262","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9ece9bc63b7314d725c9be7c351612e465cf9932","datavalue":{"value":"42A38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2369946$44B90FEE-29B0-41C5-ACE0-EC4A71B9F636","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"108999326dc6f36e1c11c009df4a2db0ee5e60cb","datavalue":{"value":"42A85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2369946$01F1C53D-9866-4066-9B6D-9FF16A01F131","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2369946$C1050A5F-B49A-4682-8FE8-EF84EF0AA8D6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8e504e544c44c34ff022143b2c1e3ba43f355457","datavalue":{"value":"5166275","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2369946$5D0912B9-BD7E-4E16-8702-AD4F647F5EF7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1328eccdc9de6f1faba0b59107ec6c81584a0b77","datavalue":{"value":"fast Fourier transform","type":"string"},"datatype":"string"},"type":"statement","id":"Q2369946$CBBA10EC-6606-4FFE-9462-349C141329E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7279f32753484b45c644c09c3b3d6e0b6215852c","datavalue":{"value":"real FFT","type":"string"},"datatype":"string"},"type":"statement","id":"Q2369946$E6F2EDF5-1C59-4BFB-8834-9C5A143584B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8fa50c59ee0c2a1b14e4f4b7e9b86f659735ab89","datavalue":{"value":"split-radix FFT","type":"string"},"datatype":"string"},"type":"statement","id":"Q2369946$D81B6F62-C591-4D43-A2FD-918808B2EE76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a88cc157a80f8b8ce8c347bc16f938caa4987021","datavalue":{"value":"matrix factorization","type":"string"},"datatype":"string"},"type":"statement","id":"Q2369946$333D1CFD-92DF-4AF7-8C28-35187249A320","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"343cd6c84735ac61fe9ddaac5c5cfd8b39f72966","datavalue":{"value":"scaled odd tail","type":"string"},"datatype":"string"},"type":"statement","id":"Q2369946$09D2660F-1EA1-458B-A89A-50BFE5C1F747","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac9585c445b6bc92d765acb42bc0302ffb8406c0","datavalue":{"value":"real convolution","type":"string"},"datatype":"string"},"type":"statement","id":"Q2369946$2476DFA2-5093-45D0-A2BD-EF08631207EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7866b2af944fdb48911874ce128bd801ef84fc70","datavalue":{"value":"Fermat prime order","type":"string"},"datatype":"string"},"type":"statement","id":"Q2369946$E047AF64-5A1E-43CE-8F23-110D94DCAD50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a3187abf7fcfd78aca7f269c22d8ed890adb5bd4","datavalue":{"value":"Rader's method","type":"string"},"datatype":"string"},"type":"statement","id":"Q2369946$7939E52C-8169-46D6-9E02-1E5AF9C7FEFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"827bf39df11a501dc0ea1c974c51c3e54cab4e4d","datavalue":{"value":"minimum arithmetic costs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2369946$C2437CC7-D1A6-47A4-BDB2-F3F43A76936D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f3db469ab2d1ceb198af89d84b5ed432c2d3383e","datavalue":{"value":"fewer arithmetic operations","type":"string"},"datatype":"string"},"type":"statement","id":"Q2369946$1B12D280-8CF4-411A-A3FB-EFDD628FBDF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"722e1fbede0da0faa925882ef00baf92113cc592","datavalue":{"value":"Fortran program","type":"string"},"datatype":"string"},"type":"statement","id":"Q2369946$263A0005-2DB7-4E0C-8BB6-ACA48A60C148","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f1be2841f447732553799af74771f551196f143e","datavalue":{"value":{"entity-type":"item","numeric-id":221675,"id":"Q221675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2369946$19B98DD0-967D-4BA1-A00A-082D3F132774","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"58cd7f44f3a5f4be71dfb3dc568d15ca128568de","datavalue":{"value":{"entity-type":"item","numeric-id":794022,"id":"Q794022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2369946$0279C62D-0103-40BF-BC51-A4C76956D2A9","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"082d1508f9b60f0ed950294b06ee865c363ff3e5","datavalue":{"value":{"entity-type":"item","numeric-id":23467,"id":"Q23467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2369946$1BA0C5D4-9673-46BF-A85C-8D98B1F7DD37","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":"Q2369946$340D88A5-82BB-41B7-8E33-9769C1B9A24E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"90f122e2e166692d304ae1235317a0bc9522e12a","datavalue":{"value":"https://doi.org/10.1007/s00607-007-0222-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q2369946$643F9107-B4FC-4589-A69A-DAD6D830B24E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d4760d2c2308608d428f408820e13445ea321662","datavalue":{"value":"W2000181170","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2369946$01525367-8CAC-40E4-9D15-9196F41B8B54","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"0879eeb173355f8939987dc1c1e881cac07078ad","datavalue":{"value":"Q56048275","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2369946$B12E9443-7745-469A-9A31-9AFBD348BE02","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"355ccfd4fc5560a7638ba2d83cd10a645c651521","datavalue":{"value":{"entity-type":"item","numeric-id":917259,"id":"Q917259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2369946$E0536284-7233-48B1-81BC-3211BFD1CFDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cf96a3313400849d1a8bb7159d3bc201e46fe6e","datavalue":{"value":{"entity-type":"item","numeric-id":3986791,"id":"Q3986791"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2369946$ED0B58DB-73E7-4F29-B20E-1E09B26F24C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ffc4474a277e346e2e0d7523c6a722cf4b3aa2d5","datavalue":{"value":{"entity-type":"item","numeric-id":3678627,"id":"Q3678627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2369946$1BD83800-D29E-411D-AF7E-9D10E4F32AF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50d2d5e6129dc659d9f97f9fc5c18e80b173a2a2","datavalue":{"value":{"entity-type":"item","numeric-id":4849363,"id":"Q4849363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2369946$7B72EC00-0311-4ADB-AE07-5C9A5CCA2AB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f613bdc44d6bfbbef30f2efae42f928cd494e67c","datavalue":{"value":{"entity-type":"item","numeric-id":1050758,"id":"Q1050758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2369946$8E7F7C2E-3E5A-4E7C-9391-B49FB5DF1B14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6384b4ac3e607d7e436e4b89278d816cfbe26868","datavalue":{"value":{"entity-type":"item","numeric-id":1098609,"id":"Q1098609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2369946$D3134256-8E9A-40BD-B2B1-22BC3B3001E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8db9bef81ade6a0f0e0f5fb17e9c53690728398b","datavalue":{"value":{"entity-type":"item","numeric-id":3823113,"id":"Q3823113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2369946$0DF4ADD7-5AA6-4748-9C50-8A1D718B8065","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6b5418d36862dc3f1376a27cc9805555e07f6c1","datavalue":{"value":{"entity-type":"item","numeric-id":554691,"id":"Q554691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2369946$69596E32-C88E-4C24-ACE3-EE54203898AF","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"f9d77528525ec87a6f1c3f969d807bd8d09eb8d6","datavalue":{"value":"journals/computing/LundyB07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2369946$D1967D30-AD84-4661-9B1F-53F12D309AEC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"05f3b627ea82422f1d3799c1d65d32e26c142364","datavalue":{"value":"10.1007/S00607-007-0222-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2369946$1F49B084-7DAE-46E2-8A0C-A95794951DC9","rank":"normal"}],"P1643":[{"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":"9632230b9f26565303767a13bb88f289551b7f22","datavalue":{"value":{"amount":"+0.8132748007774353","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":"Q2369946$72DA3C48-7029-41F5-8700-22CDDE1DAD19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b8e9da203e08314538f790c1bafd4c8a454b1dd8","datavalue":{"value":{"entity-type":"item","numeric-id":4293974,"id":"Q4293974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c698ec13b152a1a296be96c04dd268fa4ddcd056","datavalue":{"value":{"amount":"+0.8131017684936523","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":"Q2369946$9475F7AF-7A0D-4633-926A-843B3A42E99D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cdd5438b027e4877955269ab2657be89f9a4bf39","datavalue":{"value":{"entity-type":"item","numeric-id":4397979,"id":"Q4397979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a0e67935e0bcbb5a60015d21b20be279d905cd7","datavalue":{"value":{"amount":"+0.8101611733436584","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":"Q2369946$E2EBC5EB-561A-429C-8E34-817E6091E303","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6caa704f0732176a2e98a7e1807e3d1d1841b8cd","datavalue":{"value":{"entity-type":"item","numeric-id":3701321,"id":"Q3701321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d15d3c458a9d7c917e80c406bcb813682ee2ee2a","datavalue":{"value":{"amount":"+0.7962338924407959","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":"Q2369946$25058F4E-B1FC-48C6-8691-BD8F628DE29E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"71accfc810804eff144b7c4b6793f7990ce43462","datavalue":{"value":{"entity-type":"item","numeric-id":4849363,"id":"Q4849363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"47446f264ffa91b744439ab5825fe09cfe275114","datavalue":{"value":{"amount":"+0.7929995059967041","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":"Q2369946$C5C2D70A-3A44-4373-B812-F9ADC0B11B2A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2369946","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2369946"}}}}}