{"entities":{"Q1094136":{"pageid":1104888,"ns":120,"title":"Item:Q1094136","lastrevid":66121473,"modified":"2026-04-12T07:41:28Z","type":"item","id":"Q1094136","labels":{"en":{"language":"en","value":"On the computational complexity of the general discrete Fourier transform"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4024782"}},"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":"Q1094136$65BAD8ED-67BC-48A4-98CB-51EC97782A78","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0dbba5aa83d14efc1ecf40b5608f673f2f9b5db7","datavalue":{"value":{"text":"On the computational complexity of the general discrete Fourier transform","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1094136$4BF18D07-C806-41AF-ADB1-7D635ADF2ABE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"23c1662c51c05f32ee2a07b30b7c8e49f0aa29a8","datavalue":{"value":"0629.68041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094136$9F0A523D-5EE2-4D08-B1E3-0BEF17434D3C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4358a024aa7f31edc01b9c345ca7ffcde3c664f9","datavalue":{"value":"10.1016/0304-3975(87)90041-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094136$D1919D82-CE23-4CD3-9D20-27C116389BAE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1eec2d0381468f1cb2d6c386ed67f3c85574c42e","datavalue":{"value":{"entity-type":"item","numeric-id":677161,"id":"Q677161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094136$E174409D-A5AE-4FAB-8D93-0E514A6F7C7C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094136$34946DA9-CF2D-485E-88C5-0F1BCF4D554D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1094136$905507E4-6211-40FB-BBD5-CD000A70981A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5937ad0681cb0fe730cecd37079ee200604a3c3a","datavalue":{"value":"The complexity of computing the General Discrete Fourier Transform over group algebras of finite groups is studied. Starting with a short introduction to known results, the complexity gains of a new algorithm derived from Clifford's theorem are discussed. Applying these results to the class of finite solvable groups, new upper bounds, also for the complexity of the underlying group algebras, are derived. The main result on the asymptotic complexities is stated as follows: Theorem: Let M be a finite set of primes. Let G be a solvable group, the order n of which contains only primes in M. Let \\({\\mathbb{F}}\\) be a splitting field for G fulfilling Maschke's condition. Then the complexity of computing the Generalized Discrete Fourier Transform of \\({\\mathbb{F}}G\\) and its inverse is in \\(O(n^{u/2})\\) where u is an exponent for matrix multiplication. The same order statement therefore holds for the complexity of computations in the group algebra \\({\\mathbb{F}}G.\\)    Based on the present knowledge about u the result of the main theorem implies that, asymptotically, the linear complexity L(\\({\\mathbb{F}}G)\\) of the group algebra of solvable groups of order n can be reduced from \\(O(n^ 2)\\) to \\(O(n^{1.19})\\). For specific computations in group rings of `moderate' size it can easily be shown that by using the straightforward matrix-multiplication the proposed algorithm requires at most \\(3.5\\times n^{1.5}\\) steps.    It should also be mentioned that the proposed algorithm also covers the much simpler case of abelian groups, thus producting the known FFT- algorithms of reduced \\({\\mathbb{F}}\\)-linear complexity. In these cases, multidimensional representations do not occur. Thus the known bound O(n log n), where the \\(p_ i\\) have to be bounded, are reproduced.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1094136$34C16841-DC7E-4F57-AC25-D67A14484B17","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094136$5D14C328-CDD6-405C-A2E2-7E44A288C0E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094136$3F5658A7-D656-4AC3-9727-3F3CC00763A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"588be99e69a86bc02ca9cc8ddd46725bc447e370","datavalue":{"value":"65T40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094136$3DE82151-096D-4491-B248-64D82C3DB182","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7a3d27bc03be9e9caf6ec45e868ab92372de8539","datavalue":{"value":"4024782","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094136$B98C73BE-ABB1-4C07-8CE3-95F6C72A76B9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"760b84b94b97c000f10e278f2ac866294c728151","datavalue":{"value":"General Discrete Fourier Transform","type":"string"},"datatype":"string"},"type":"statement","id":"Q1094136$AC7D7AB3-EA73-4BEF-A5CE-FA68B29FF653","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"03a7c111ae7d54dee2d137bae6bed61f73a46c07","datavalue":{"value":"group algebras of finite groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q1094136$540BA0BA-6FED-45AE-ACC5-E67AD0A3AB0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e7106364ed3a9631e5a87e3ba73dcdb0eeb8506c","datavalue":{"value":"asymptotic complexities","type":"string"},"datatype":"string"},"type":"statement","id":"Q1094136$1C71AA2B-E53E-4EAA-8278-0FA8689D748C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ca3dc19caa30b31e4b79ce30cc37d4023db492d1","datavalue":{"value":"solvable group","type":"string"},"datatype":"string"},"type":"statement","id":"Q1094136$460EF883-40A2-479E-918B-EA134947EB90","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"add0f035b354f3549a926a6ae3566f77b062bdd7","datavalue":{"value":{"entity-type":"item","numeric-id":13548,"id":"Q13548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094136$D76A1EFE-19DA-4498-A588-9700370421B1","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":"Q1094136$101DAC58-91A2-45AE-8402-4393B6E366B9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b76de42136767b1563c8d417e7378d0bcd5149cf","datavalue":{"value":"https://doi.org/10.1016/0304-3975(87)90041-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1094136$A152EE5C-6C59-4483-9B47-808F6E800490","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e2fef1634885d6ff315fcb78761204c59a3e03e8","datavalue":{"value":"W1964153492","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094136$E185E101-2039-4C05-8931-9677D8CF420D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"28c05df67d1ee9ff455357c4b4dee5c514898b05","datavalue":{"value":{"entity-type":"item","numeric-id":1242989,"id":"Q1242989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094136$71532646-9100-4697-AA80-B81CB23D9B7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb299fc84af117e6a11ab19f118a6bfa5a0a8043","datavalue":{"value":{"entity-type":"item","numeric-id":3692857,"id":"Q3692857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094136$578ACFDD-861C-4E8F-83B1-EB96801C48F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e9b27161264795810181a327403214f853d901a","datavalue":{"value":{"entity-type":"item","numeric-id":3321411,"id":"Q3321411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094136$F40791DD-F71C-4CC4-8726-04CB10360EEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd868ce1dbfc4d6f38bfad66c445685c537ca87b","datavalue":{"value":{"entity-type":"item","numeric-id":5332499,"id":"Q5332499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094136$48EC4B06-7674-4ED3-8F75-45D8A3B36EE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"afd51cbfd126e5ce8b424152bc94e2831fb35716","datavalue":{"value":{"entity-type":"item","numeric-id":3922829,"id":"Q3922829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094136$BC01902A-AB05-496D-A59D-43FC9F288F4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"efcc08bcc639721f2085dd6c33802fd980717d8a","datavalue":{"value":{"entity-type":"item","numeric-id":5634146,"id":"Q5634146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094136$7F5670F3-5393-48EF-A228-10D5D588A277","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"431eb0c8bb9d1e0bd378f077ac5e97e5f99a08db","datavalue":{"value":{"entity-type":"item","numeric-id":3894101,"id":"Q3894101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094136$70744338-A878-4417-8AF0-608DFB8DCD90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07db5d9d443b5d4b2edd7761e49422c74809a4b4","datavalue":{"value":{"entity-type":"item","numeric-id":5620726,"id":"Q5620726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094136$B0936F4A-0DA6-4D73-8563-EFE414DF990E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74fcc431830683aabfa39495cf0be8adcfe9b3ea","datavalue":{"value":{"entity-type":"item","numeric-id":4103728,"id":"Q4103728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094136$831423A4-D250-4467-A389-40B11832DFEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c07501db2f7258e5eee47a95568992dfd07896e","datavalue":{"value":{"entity-type":"item","numeric-id":4147573,"id":"Q4147573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094136$F3BD6E2D-C177-4696-83A0-6F7E7413F0EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6899b40a48bb6dd55553fc9b55d2ab3a1166c63","datavalue":{"value":{"entity-type":"item","numeric-id":5588717,"id":"Q5588717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094136$2577E10A-1017-451E-B202-D7B53CABE752","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d27ae0c06b28e6be5ae4b470d7fdb6aba03f14f4","datavalue":{"value":{"entity-type":"item","numeric-id":5674381,"id":"Q5674381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094136$C3E78D61-51B7-49E0-BA63-6A9FE114B16E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"507334689f347ba0c77cd4f96c1ae97d2e084806","datavalue":{"value":{"entity-type":"item","numeric-id":3735040,"id":"Q3735040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094136$05771317-5B94-4503-9495-6910D5377982","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9d8c350949a1756c139d37f2d6a15448293320c","datavalue":{"value":{"entity-type":"item","numeric-id":5120695,"id":"Q5120695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094136$F3B8CDCC-C8D6-4065-9D87-0BFC23A30709","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c60ed57ff0fef494cfbd38ae6a3aa32f3416d6d1","datavalue":{"value":{"entity-type":"item","numeric-id":4126536,"id":"Q4126536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094136$18E5F647-671C-4AAC-B3AF-1B3EB037182E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f1746c0002a982167f6b872896509d0ce78aa9e","datavalue":{"value":{"entity-type":"item","numeric-id":2536323,"id":"Q2536323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1094136$34741E86-B0FF-4EC3-93F6-986673934D6D","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"18440dc2953447a6a7c7ccd39a6b7b2886cde82d","datavalue":{"value":"Q127676224","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1094136$59567FC6-FC25-468E-A3F7-AD808A30F252","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"67b892c3eb94344a062f461a370d479587d0fb77","datavalue":{"value":{"entity-type":"item","numeric-id":685713,"id":"Q685713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"548f22ae284dae87c033b01f2a4eabff53e7ae91","datavalue":{"value":{"amount":"+0.8257886171340942","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":"Q1094136$5E0EFA44-E17C-4E6E-B095-47A367878B6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7239cb8aef3368f0e5b9f5973cc4fb5e6d8da4e","datavalue":{"value":{"entity-type":"item","numeric-id":4502609,"id":"Q4502609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d80874c6402e0202fee1753c9d0f244eaf7216b3","datavalue":{"value":{"amount":"+0.8229956030845642","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":"Q1094136$BFBF0885-F204-4500-96B4-603FADFCD1D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4866a3c1030252adaaeeac4818579081980b5d0c","datavalue":{"value":{"entity-type":"item","numeric-id":4973053,"id":"Q4973053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bcf9a3252f2ad596fe20e7f515a4719a1ae175bd","datavalue":{"value":{"amount":"+0.8226092457771301","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":"Q1094136$7C20A8BC-DCEA-4597-8D4F-1EC96B6316F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"010468382740c12657d0579aebc3f37b1d8dd20d","datavalue":{"value":{"entity-type":"item","numeric-id":597054,"id":"Q597054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"64185b1e47d0cd381dd8b0d6be8c4b035260b02f","datavalue":{"value":{"amount":"+0.820688784122467","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":"Q1094136$80F06B40-63DE-4551-9F2A-D6D56A42DF4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"44bb42d1aec1c8942d379e1df1c627d3ffc473ce","datavalue":{"value":{"entity-type":"item","numeric-id":3355210,"id":"Q3355210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c30e498acd349c7281a7684f90e579c728a92f42","datavalue":{"value":{"amount":"+0.8200475573539734","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":"Q1094136$7D133AAB-A3FB-4359-8738-65F3E78C3146","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the computational complexity of the general discrete Fourier transform","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_computational_complexity_of_the_general_discrete_Fourier_transform"}}}}}