{"entities":{"Q540329":{"pageid":542096,"ns":120,"title":"Item:Q540329","lastrevid":62606586,"modified":"2026-04-11T07:13:55Z","type":"item","id":"Q540329","labels":{"en":{"language":"en","value":"Chunky and equal-spaced polynomial multiplication"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5903425"}},"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":"Q540329$E2F17D63-0495-4097-9689-6F2658F23F69","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c5f101fce04be556acb09b778a4f6ee95d7c9625","datavalue":{"value":{"text":"Chunky and equal-spaced polynomial multiplication","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q540329$52509435-19BC-46EC-A446-8ADB032DB981","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"db32d6ad11f76c754262e51e70a2406b2e2a4042","datavalue":{"value":"1217.65038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540329$C43A741D-1550-4B7C-A522-523A35AADA58","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9b3d3076c6184bffa802df34211b7e27fba3b970","datavalue":{"value":{"entity-type":"item","numeric-id":540328,"id":"Q540328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q540329$6B6DFEE2-7AB1-4CFB-9815-A5C6FDA4FE64","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ea72303f92787da89554ee5fa15621068821a762","datavalue":{"value":{"entity-type":"item","numeric-id":99061,"id":"Q99061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q540329$6AE33CD6-733B-4542-ABBA-0E9BEDCADCE4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ca412915d48bc02df19cbc26b81271d64e23ee32","datavalue":{"value":{"time":"+2011-06-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q540329$4C1A9BA9-0F4B-49EB-8786-D0CF1250DC22","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"efa45730378ce64018453cb159647155cf575e7f","datavalue":{"value":"A typical problem of computer algebra is addressed in this paper, namely the efficient multiplication of large polynomials. Here, a certain type of polynomials, called chunky, is considered, where there are chunks of nonvanishing coefficients near to each other (i.e., with similar powers or indices). This does not allow a worst-case analysis as is usual, but a new fairly efficient way to analyse the problem of multiplication. Algorithms are given for this new approach and it is proved that they are still of the same efficiency in the worst case as the previous methods, but are better in many other cases. (The first algorithm is about chunky multiplication, and the second algorithm about optimal chunk size computation.) The optimal chunk size is studied as well as the case when the coefficients of the polynomial are not chunky but are spaced at equal distances apart (again, from the exponent or index point of view; algorithms for equal-spaced multiplication and conversion).","type":"string"},"datatype":"string"},"type":"statement","id":"Q540329$9E4E802C-958A-4353-BB34-C4CD5D344BF1","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"57517494b25f5328eb9a6d2c44038a6d20040d33","datavalue":{"value":{"entity-type":"item","numeric-id":504888,"id":"Q504888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q540329$2F7F3EEB-8581-46DE-A83F-DED201F05A61","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2afc8b14470e661c10725547661d94fa1583b792","datavalue":{"value":"65D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540329$2A980E82-E4C7-4E9F-90EA-E07C7573E980","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540329$5D5F7C65-2392-4D48-8B51-E6E6D9DEB20B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"661c831991cdebd51f9465b74d929024bd00f373","datavalue":{"value":"12Y05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540329$3BCA0469-8692-4325-82EB-05862F3D382C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0c641605c81c1f56a9ea4f78da65504cd836e458","datavalue":{"value":"5903425","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540329$D6E41E5F-5D19-4A5C-88AA-9990C54E6DF3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a5ba416b3228e58d69cc95841fcf815946973061","datavalue":{"value":"polynomial multiplication","type":"string"},"datatype":"string"},"type":"statement","id":"Q540329$CDC1D9FB-9069-4919-AEDF-1743B1C7430B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d6690f138360261f589949cb24c0b670b5e8d9b9","datavalue":{"value":"adaptive algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q540329$4C4D3707-1973-4490-A258-AE289D5FB539","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8581a4fe4c0d3571122fc96549003538cce73aa","datavalue":{"value":"sparse polynomials","type":"string"},"datatype":"string"},"type":"statement","id":"Q540329$A7F0195C-B3B5-4BC9-BAAD-85C4FAA7C163","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d09055554eb4609eeaa91197a57cb48cecbacb55","datavalue":{"value":"chunky multiplication","type":"string"},"datatype":"string"},"type":"statement","id":"Q540329$25C59E63-96C5-491C-B812-3B897102BCBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0ae54f7b5652123e26fa8d2c0c956e0b87fd63a4","datavalue":{"value":"optimal chunk size","type":"string"},"datatype":"string"},"type":"statement","id":"Q540329$61BD917B-B011-4B87-ADBB-7B41D086F725","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":"Q540329$22427825-7183-4C68-81F2-79DB1E99EFE7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0dd41f46729b4de1804e58a13ca514516ec77398","datavalue":{"value":"https://doi.org/10.1016/j.jsc.2010.08.013","type":"string"},"datatype":"url"},"type":"statement","id":"Q540329$9BA711F2-5F7C-4079-AA63-B800AA5F26B2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"39a38d70592b7de34532ab062f256676fe7ec15c","datavalue":{"value":"W1655250744","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540329$6F891FE6-EA57-45A7-8778-3D6EC2128C5B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"356f33dddb9638087fb97e96ade9a65b62e404ec","datavalue":{"value":{"entity-type":"item","numeric-id":1186518,"id":"Q1186518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q540329$8335D204-3B0B-4C08-BF2D-D5370F3DB02D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0deaab079114fc0b1e4204792efe23c9a99893cc","datavalue":{"value":{"entity-type":"item","numeric-id":4810194,"id":"Q4810194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q540329$C00D2D56-EBE1-45A0-BFB4-6ADC46C2CD43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fed9a53f7afaa8a323d3b620da790e67c16a9fa3","datavalue":{"value":{"entity-type":"item","numeric-id":1878478,"id":"Q1878478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q540329$4C7E214B-2CA2-4B83-BF4E-F7CEB5DEC8CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c330e9364d470d585edc11e60135f5ae14baf37","datavalue":{"value":{"entity-type":"item","numeric-id":3508493,"id":"Q3508493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q540329$2C653D1F-422B-485F-A84A-5E3B58199D57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05a0e95ba2f51e20118accbfa856ec9d101fcc31","datavalue":{"value":{"entity-type":"item","numeric-id":1891925,"id":"Q1891925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q540329$72CE3302-B43D-4771-88E1-8026624F1657","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d864ecf0887e3285d5a657ecba76076407dae52","datavalue":{"value":{"entity-type":"item","numeric-id":2548172,"id":"Q2548172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q540329$275B8895-86C4-4348-9E8B-90967F4AC82B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0618290a7b629940c987789b6eb12858fbd01f56","datavalue":{"value":{"entity-type":"item","numeric-id":5601777,"id":"Q5601777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q540329$D4FA1114-12F1-435F-BBF5-CE21C43C0415","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"036596f0d350812e61dbec211ba3b26f1481f8b3","datavalue":{"value":{"entity-type":"item","numeric-id":1264445,"id":"Q1264445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q540329$2D777A83-FDFC-42D2-84CD-1FF6DBB9668C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"df74a7b42983027148299e9fb985f242eef17c62","datavalue":{"value":"10.1016/J.JSC.2010.08.013","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540329$58F3A10A-6E25-430E-B40C-A05E5A817909","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ae1bde3c1cac2968e2bdba1dec842794013c12a2","datavalue":{"value":{"entity-type":"item","numeric-id":3334076,"id":"Q3334076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e98e8102702db870bdbd9dadbd9f1aa64bc54ed4","datavalue":{"value":{"amount":"+0.8298642039299011","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":"Q540329$EC9D9D26-9996-4BC2-95F0-29202689D660","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24c180d93b27f6aa27f6144e8af33e8c7c9fc0d6","datavalue":{"value":{"entity-type":"item","numeric-id":2452938,"id":"Q2452938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b106f22c69ae31b1c89c53652c0fec30c477da9","datavalue":{"value":{"amount":"+0.7866234183311462","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":"Q540329$72C80F76-E4C5-4A71-99A2-76D4B2D14491","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d4273629e00b0f0237a8fe5f222c7682f9f3411","datavalue":{"value":{"entity-type":"item","numeric-id":808710,"id":"Q808710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"43e57b2d01bcdbc3ff2fc9b300594cdf4fa3699f","datavalue":{"value":{"amount":"+0.7716787457466125","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":"Q540329$0AAC0823-496E-402E-A323-4CDD09D78493","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e31dbb9cc88ed43af4c5c761c70ca685f3e6d1ae","datavalue":{"value":{"entity-type":"item","numeric-id":1186518,"id":"Q1186518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed29c3b8c98759e0aacdd4622fe9fdb58de7003e","datavalue":{"value":{"amount":"+0.7682409286499023","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":"Q540329$4E0D0612-CA65-461F-BCEA-8F69D81C98F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3545e94215d488953d25c9f01ea35d1701adeac8","datavalue":{"value":{"entity-type":"item","numeric-id":3325040,"id":"Q3325040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed29c3b8c98759e0aacdd4622fe9fdb58de7003e","datavalue":{"value":{"amount":"+0.7682409286499023","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":"Q540329$32963C73-E95A-4FD1-BB17-F807F63248F9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Chunky and equal-spaced polynomial multiplication","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Chunky_and_equal-spaced_polynomial_multiplication"}}}}}