{"entities":{"Q677546":{"pageid":679395,"ns":120,"title":"Item:Q677546","lastrevid":63518076,"modified":"2026-04-11T13:42:50Z","type":"item","id":"Q677546","labels":{"en":{"language":"en","value":"Fast algorithms for computing one- and two-dimensional convolution in integer polynomial rings"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 997765"}},"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":"Q677546$006C8AAF-7D76-473C-BA7B-786A6F3CF816","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a17fcf605a147e77842df568c484bdde801e1ed8","datavalue":{"value":{"text":"Fast algorithms for computing one- and two-dimensional convolution in integer polynomial rings","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q677546$FEFE844B-670D-4EF6-BC59-B4512B20D303","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4243e90ab1b0e3ac18c0195fd986d4d7acff7d1c","datavalue":{"value":"0885.68069","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q677546$47F0B538-39D3-4BAE-8C2A-7360B2CBD333","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e2e3752565227dd6037e9cd76b1ac9f4c47f3610","datavalue":{"value":"10.1007/BF01183180","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q677546$3515C8B0-40C2-45CD-9D00-2A72E7D8BF1F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"03146bb8e17b3d6cc14817a371f8c48ba30cf452","datavalue":{"value":{"entity-type":"item","numeric-id":624377,"id":"Q624377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677546$CFDE4C1D-91D8-4724-9B3B-CF53409B7D2A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"25364cb6f58b827e4119f8c3b4fe4fd58b63c477","datavalue":{"value":{"entity-type":"item","numeric-id":163034,"id":"Q163034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677546$0CD03028-1392-46CA-BEC8-5614FCA0C7B9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"adb15fff212634ed49f2d35e429dbbe9bdd3c551","datavalue":{"value":{"time":"+1997-05-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":"Q677546$53E96A5B-F89B-4D1A-84B0-B257045EB469","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4165e74f33a2e08b75df1344606adee8a18dd36b","datavalue":{"value":"The aim of the paper is to give new computationally efficient algorithms for compute discrete convolution of data sequences in rings of the form: \\(\\mathbb{Z}/(m),\\mathbb{Z}[i]/(m), \\mathbb{Z}[\\theta]/(m), \\mathbb{Z}[i,\\theta]/(m)\\) (where \\(m \\in \\mathbb{Z}\\) and \\(\\theta\\) is algebraic over \\(\\mathbb{Z}\\)), and polynomial extensions of these rings. The algorithms are based on the possibility of decomposing the above rings into direct sums of components (obtained from the factorization of \\(m\\)), hence a large size problem is expressed as a sum of a number of smaller size problems that are then computed in parallel. In order to obtain the desired solution, suitable formulations of the Chinese remainder theorem are used. The algorithms described regard the computation of one and two dimensional convolution of data sequences. Both cyclic and acyclic convolution algorithms are derived for the one dimensional case, whereas only cyclic convolution algorithms are developed for the two dimensional case.","type":"string"},"datatype":"string"},"type":"statement","id":"Q677546$EE23E3C1-2EB2-4D56-B758-BA1CE0E8AE9A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de3565cfd3393000dd87ca545f95ff84d4c1446","datavalue":{"value":"68W10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q677546$1F5BDDB4-EF59-4C79-8586-140FBC389899","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"134db59e1dd21b74810139030592980e5f363e0f","datavalue":{"value":"13P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q677546$90180DBC-3832-43E8-B5B1-08036194E4C4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9958b988cba903d5a0700505654d0b24e60ae37e","datavalue":{"value":"997765","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q677546$1AC78D16-A441-4AF2-B499-DB6BA01A882B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a9e6db67c1f44b4c0c8f9356d9b08bc1a933f6f","datavalue":{"value":"convolution of data sequences one-dimensional convolution","type":"string"},"datatype":"string"},"type":"statement","id":"Q677546$D2AD7119-71E3-4132-A7FB-9DB85E20D5BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"83e55213500f628d68cd79ceeb89ebe863c944d8","datavalue":{"value":"two-dimensional convolution","type":"string"},"datatype":"string"},"type":"statement","id":"Q677546$5F438EC6-3B9A-4E51-89AB-9D7FD92AD21F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"80f116a1cdb08066811a19630fb4c8beca038913","datavalue":{"value":{"entity-type":"item","numeric-id":321274,"id":"Q321274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677546$55192DDC-F5B6-4602-98DF-10F4545D304B","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":"Q677546$2BB1B338-1111-48F6-BC98-6963C4C784F3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f562e6ebcfc5783d3f79bc8961bd312053603e47","datavalue":{"value":{"entity-type":"item","numeric-id":3674010,"id":"Q3674010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677546$1A74D74C-48D4-4350-B4B5-F5CF5E6C4A57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39ce4c94bc1d9ea210a0754cd517772c85ab3712","datavalue":{"value":{"entity-type":"item","numeric-id":3050271,"id":"Q3050271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677546$DFC86B88-5FB6-461D-A40A-F58CAA990322","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25825d1329db187a07dea124f5458227d759e59e","datavalue":{"value":{"entity-type":"item","numeric-id":4174615,"id":"Q4174615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677546$58CDC478-A36E-4E28-B8E0-9B479FE66EB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0be0e4421b4834ab7b4d4d09fcdb5d2b5786f112","datavalue":{"value":{"entity-type":"item","numeric-id":3339231,"id":"Q3339231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677546$01BBC8D0-8069-4D72-86D8-7495DFF0A43F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a52246bb7701cb703f4e131bfc8e0937c922ce50","datavalue":{"value":{"entity-type":"item","numeric-id":1922613,"id":"Q1922613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677546$4A3C1424-A81A-49D9-8D1E-00FAC6E3CCA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef9b105e7d42b33c075d65f90d7f4babb5d49265","datavalue":{"value":{"entity-type":"item","numeric-id":1345182,"id":"Q1345182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677546$3AAE6B44-0C2F-4C33-AA4B-711F1398A29C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09f0031f973ae0b13acb69e0cd0d11c5f2670a98","datavalue":{"value":{"entity-type":"item","numeric-id":4849365,"id":"Q4849365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677546$93B893C5-6333-454A-BF43-266017887015","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d93d72f1db5ad72c77301419795edea0bfc9be47","datavalue":{"value":{"entity-type":"item","numeric-id":4849366,"id":"Q4849366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677546$1DE3EA83-F060-4EE8-8733-270F0E410F96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c186f111e8c92af536845d6c6c690a25f0a0276","datavalue":{"value":{"entity-type":"item","numeric-id":3680230,"id":"Q3680230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677546$506E0C7B-F9B9-49F4-8DE3-800B70943B03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62d699c3effcf0c2e57c491867055fc3dfde3383","datavalue":{"value":{"entity-type":"item","numeric-id":3698249,"id":"Q3698249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677546$C9B62959-13B8-4A60-9785-A1A64D2EFBE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7f341f6e4cf05a830e7c1a37d5e60b0bdfc4a5e","datavalue":{"value":{"entity-type":"item","numeric-id":3680231,"id":"Q3680231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677546$E6EE43A1-321B-4783-A66E-E4269BEE817F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8453e3464418a49f0273bfb2acaf42a011835bfd","datavalue":{"value":{"entity-type":"item","numeric-id":3680232,"id":"Q3680232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677546$A0B83FBE-B241-4CC8-B9BC-1B488E4B005D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b3ee8e8b33df93030dc0257d837d486cf9df8d7","datavalue":{"value":{"entity-type":"item","numeric-id":4152130,"id":"Q4152130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677546$B6581182-97D1-48DF-8C74-20F1C856E6EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4babe5acd379f1156b6a418112f1afab4a8c795b","datavalue":{"value":{"entity-type":"item","numeric-id":5664781,"id":"Q5664781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677546$F0DC3396-8BB1-4005-855B-3D31AE804039","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c168d98695f309fcf4cdb0b2fb904e46823ad488","datavalue":{"value":{"entity-type":"item","numeric-id":3867129,"id":"Q3867129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q677546$1684A876-AA21-4A7B-A516-2A31A4C82AA6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8144e05daf64120e0ab283b49de91cd3dcbc8cc9","datavalue":{"value":{"entity-type":"item","numeric-id":1922614,"id":"Q1922614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a40edd1f14e40f2749f5031524a2bca36f01bd2b","datavalue":{"value":{"amount":"+0.861257791519165","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":"Q677546$D24DB7FB-0B8B-4F61-A2BE-78BFE84EDCDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"acfaed8651b1dca8476189f7845ef442b513102e","datavalue":{"value":{"entity-type":"item","numeric-id":1190157,"id":"Q1190157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"095db7e21e50a65f1cbdaf376b5652cdd439aeec","datavalue":{"value":{"amount":"+0.8400493264198303","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":"Q677546$B6641E4E-0843-48CB-B787-1BA8B8B86C93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fabf605dd31ea17d84ab2e087be96cbbd73f00d","datavalue":{"value":{"entity-type":"item","numeric-id":3698249,"id":"Q3698249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dadebeae94421042dbf9155558c8e5db68641d85","datavalue":{"value":{"amount":"+0.8345782160758972","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":"Q677546$182F095D-0E75-4019-9473-4B2AF875EC53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16fcc141d1012846c5fe56f37d47e3ebb2945dfd","datavalue":{"value":{"entity-type":"item","numeric-id":3773182,"id":"Q3773182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a2d2b03723d6a2aa496aa98e4484634b8b5b4ea","datavalue":{"value":{"amount":"+0.8193840980529785","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":"Q677546$DFAB5470-9B3E-410D-BB4D-3837C7E05567","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Fast algorithms for computing one- and two-dimensional convolution in integer polynomial rings","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Fast_algorithms_for_computing_one-_and_two-dimensional_convolution_in_integer_polynomial_rings"}}}}}