{"entities":{"Q2518611":{"pageid":2529354,"ns":120,"title":"Item:Q2518611","lastrevid":78798899,"modified":"2026-05-06T12:27:59Z","type":"item","id":"Q2518611","labels":{"en":{"language":"en","value":"An improved EZ-GCD algorithm for multivariate polynomials"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5493095"}},"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":"Q2518611$0AA80912-59C0-432B-907F-BE00DB0C1EEC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3af525f5339dd3c5f4aa1bb75bb6daaf32fd8672","datavalue":{"value":{"text":"An improved EZ-GCD algorithm for multivariate polynomials","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2518611$2D009B24-8999-4739-A0EC-57985129B432","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5f259af23a3f5c308c85ea77739322ebb8870cca","datavalue":{"value":"1156.13013","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2518611$EE9768B6-434B-426F-968F-A00CBB5A4553","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"414468efa6582862c2d0926065e94c76cfc3a378","datavalue":{"value":{"entity-type":"item","numeric-id":2518610,"id":"Q2518610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2518611$98939472-81C0-46E9-A15B-B3349BA83BD9","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":"Q2518611$7DCB79FC-1248-4004-A45E-125EC55DDF54","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7e9641c3d22c083c62eb9335e1946facf29f71bc","datavalue":{"value":{"time":"+2009-01-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2518611$9F38432A-9715-4C4C-8E76-62BFC2FF14BD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fbf06beda74b3e9cfacb627e3cadcdd484cf0bf8","datavalue":{"value":"The aim of this paper is improving the EZ-GCD (and EEZ-GCD) algorithm for sparse multivariate polynomials, in order to avoid the ``bad-zero'' problem [\\textit{J. Moses} and \\textit{D. Y. Y. Yun}, in: The EZ GCD algorithm, Proceedings of ACM National Conference, 159--166 (1973); \\textit{P. S. Wang}, SIGSAM Bull. 14, No. 2, 50--60 (1980; Zbl 0445.68026); \\textit{K. O. Geddes, S. R. Czapor} and \\textit{G. Labahn}, Algorithms for computer algebra, (Dordrecht): Kluwer Academic Publishers Group. (1992; Zbl 0805.68072)]. The author introduces the use of the ``power ideal'' and ''power ideal with a prime number \\(p\\)'' (for short PI and PPI resp.) and from these the PI algorithm and PPI algorithm. In the first part of these algorithms, there is a ``specialization'' of the polynomials through a PI or a PPI; in this way the computations can be performed using the generalized Euclidean algorithm for a UFD and then the obtained result is lifted using Hensel's Lemma modulo a power ideal. With this technique, the intermediate expression growth of terms is reduced. The author also provides a study of the complexity of the new algorithms and some examples, enlightening both the cases in which the new algorithms are powerful and the cases in which EZ-GCD and EEZ-GCD still have better performances, making hypothesis about the reasons for these different behaviours.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2518611$D9140795-AB87-4B71-9DEF-DDB56CB0EB63","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7822fed1fa01e92e42ea9bf78e3f0c0fc49b9efd","datavalue":{"value":{"entity-type":"item","numeric-id":509557,"id":"Q509557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2518611$4EB5ACB6-1487-49B6-8942-745BE82C2634","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3261dadc98deaaa969a534e2a2cb92fd4aa565f7","datavalue":{"value":"13P99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2518611$1750D733-3DAA-4F51-B769-8EEE9C6C69F3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3559e4687c670753815d2433539f6d360b98a029","datavalue":{"value":"5493095","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2518611$318B3AE0-BD8F-4FF9-8D8B-6CB58A31BAEE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e866781cd504d9ea64090bf5887ad0c54a97610c","datavalue":{"value":"Ez-GCD","type":"string"},"datatype":"string"},"type":"statement","id":"Q2518611$7861D78F-9E6D-4550-95AC-9A8AACAA8B66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2dcad3baad5a30e3a9c62eb7212c63febadf4b97","datavalue":{"value":"Bad-zero problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2518611$C368A100-6B35-4B90-91E6-6465AADCD25A","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":"Q2518611$13129B24-B4FA-44B5-84C5-F74FA0767776","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d56d0d2e990c95ddb6606a4fd3d4ac70162666fc","datavalue":{"value":"https://doi.org/10.1016/j.jsc.2008.04.006","type":"string"},"datatype":"url"},"type":"statement","id":"Q2518611$C43D7EAC-F3CA-4B3F-80FF-49ADCFC770D2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fa39f77de51cc3f3c48e7379a4ddf93f30f4d533","datavalue":{"value":"W1979661203","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2518611$0C581DC6-0D42-4699-9A5F-B93072515EC7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"157a25450c93d717ff644eaa81fca2bb0d996c68","datavalue":{"value":{"entity-type":"item","numeric-id":5633584,"id":"Q5633584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2518611$402B6DB6-20A4-4054-9B4A-E87529B082C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58ddf6c15587cc8d775178ac7830ee9b5995c206","datavalue":{"value":{"entity-type":"item","numeric-id":5532045,"id":"Q5532045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2518611$248B4606-5699-417F-BA2C-62B8D0E42AB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74722ce8c5bd23b4d371999835f7ad66ae881dde","datavalue":{"value":{"entity-type":"item","numeric-id":5525472,"id":"Q5525472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2518611$C484D32B-9557-4063-BCF9-7C7E4AD4026A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8ba154389a204d2fe13cce852c6d6422d7912c2","datavalue":{"value":{"entity-type":"item","numeric-id":4023676,"id":"Q4023676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2518611$042260A9-A1D5-426D-B09E-037133F0F30C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5986cfaa59066a8e5705db43be0ad4f28d9b9db2","datavalue":{"value":{"entity-type":"item","numeric-id":4234290,"id":"Q4234290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2518611$A4A5B169-2949-4EB8-8494-8AE3D93BEF04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b524facdebb5d40fb32bc91c92ee80e5992b93c3","datavalue":{"value":{"entity-type":"item","numeric-id":3743382,"id":"Q3743382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2518611$2349811F-4D72-4C62-8420-7914F816472F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf57389b589f69d55d2a4776a2ad61fa38a303ea","datavalue":{"value":{"entity-type":"item","numeric-id":4660704,"id":"Q4660704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2518611$86CFD992-56FC-42E2-9EE2-0F3B12931057","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"149eb06f56b4525e17649c0c26d067c2168e7118","datavalue":{"value":{"entity-type":"item","numeric-id":1194336,"id":"Q1194336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2518611$63D89768-786E-4384-AED7-2B8A23FB8044","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7591c7499feea72ca729665226d1628fa8b146bc","datavalue":{"value":{"entity-type":"item","numeric-id":3890106,"id":"Q3890106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2518611$80A6B817-56B1-4F04-A1BC-50C78E3FFB1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55292685ad17575c747f5c939d84c27e57259512","datavalue":{"value":{"entity-type":"item","numeric-id":4168687,"id":"Q4168687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2518611$523FE59F-24ED-4C46-BD9E-BA5C4EBB58E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd3e45f1ac25fe5ee18020a36a350cf293ef6c92","datavalue":{"value":{"entity-type":"item","numeric-id":4274348,"id":"Q4274348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2518611$FACAFA27-3F79-44B4-84EB-FC475070CE8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d73e5fdcd2644fcf8851cd00097d32d1e30f5f00","datavalue":{"value":{"entity-type":"item","numeric-id":3851616,"id":"Q3851616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2518611$68E29A3E-3BFE-47D2-A478-73A4EA79FF6A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e846e212b479ba80e4e3a14d6f5ccc2437072f8c","datavalue":{"value":"10.1016/J.JSC.2008.04.006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2518611$D89228C6-4184-4D0B-B487-98471BE4D8B6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c7f45f8f9c86cc2b2854798ec386a63c619248a","datavalue":{"value":{"entity-type":"item","numeric-id":5880534,"id":"Q5880534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"377e86edbd22839392831cadcc84b791eef977fe","datavalue":{"value":{"amount":"+0.81770205","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2518611$C45DA1AB-7766-444D-8467-8C3624C126A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d0106fe612ca58eee55e35724acf7008372ad382","datavalue":{"value":{"entity-type":"item","numeric-id":1621170,"id":"Q1621170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e29c616991677a4fedc65c60fe71024291680f63","datavalue":{"value":{"amount":"+0.807204","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2518611$B3B9E45D-9CA6-473A-B993-8B484F4580D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1036684956339a6b96f06dac2f5f6f4c3946cd9e","datavalue":{"value":{"entity-type":"item","numeric-id":1994882,"id":"Q1994882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d52364829c7b6fdc3df8a40fa069c27aea15215","datavalue":{"value":{"amount":"+0.7954551","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2518611$4ECEE588-5B9F-4750-A4AE-B1436164F6DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe3afa1c8581fec9112f278102563f9ccaadefab","datavalue":{"value":{"entity-type":"item","numeric-id":689905,"id":"Q689905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c6357992388b5386c058fd8a23f0e0dee68aecd","datavalue":{"value":{"amount":"+0.79018354","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2518611$0BE8ABCE-EF14-4DA0-A118-4F403ABDD440","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b62447b6bd5a3cef1f9f764dd0ab0ab315e24f6","datavalue":{"value":{"entity-type":"item","numeric-id":2985837,"id":"Q2985837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4e8694f655cc0cdb1d29e315c3dc68f5bb548edd","datavalue":{"value":{"amount":"+0.7815262","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2518611$74F4AD5F-CB41-41D4-8020-517C1F556064","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0a89cbc666eac7c5b30073b8b263f93b3c9c564","datavalue":{"value":{"entity-type":"item","numeric-id":3447169,"id":"Q3447169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"248ed5d4eccdec4f43723f84a9903a1f14d792a9","datavalue":{"value":{"amount":"+0.7712796","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2518611$B53BC581-28F0-4046-821A-3DBBB9BE59DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ec8889cce86e438d9293fa217221edf1ad34575e","datavalue":{"value":{"entity-type":"item","numeric-id":1194336,"id":"Q1194336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3365759360677ceebc7605a7f96de9a5d5487dff","datavalue":{"value":{"amount":"+0.7709222","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2518611$59E73EC3-92EE-473B-B4B8-CD729EBCA41F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"03807e164cca9e8ba0a96fa1326990098288a4b0","datavalue":{"value":{"entity-type":"item","numeric-id":4657342,"id":"Q4657342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"318e9d88691e1a6138622f62da967b7ed69bf65d","datavalue":{"value":{"amount":"+0.75336605","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2518611$5778EB73-4527-4C73-BF27-453EFFD0234F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c5f9d0dddd9a1c6b490b6de1515d6ab7f1af07b","datavalue":{"value":{"entity-type":"item","numeric-id":4875225,"id":"Q4875225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"43da385b68478efa11e24050c2f26da5fe109607","datavalue":{"value":{"amount":"+0.75334775","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2518611$EE3E6C77-9121-4213-BD6C-F2091117898D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96adbc33c207984cdfefc4cf070414c7a28a9043","datavalue":{"value":{"entity-type":"item","numeric-id":3985430,"id":"Q3985430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3903e364bb5015d1d53059b29b9c3559e47f4a5e","datavalue":{"value":{"amount":"+0.75151145","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2518611$C566513C-96E3-4946-B4DC-154877DD860E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An improved EZ-GCD algorithm for multivariate polynomials","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_improved_EZ-GCD_algorithm_for_multivariate_polynomials"}}}}}