{"entities":{"Q1295792":{"pageid":1306542,"ns":120,"title":"Item:Q1295792","lastrevid":43012235,"modified":"2025-07-16T21:20:14Z","type":"item","id":"Q1295792","labels":{"en":{"language":"en","value":"An algorithm for computing certified approximate GCD of \\(n\\) univariate polynomials"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1308385"}},"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":"Q1295792$988E8CF3-1E41-43CD-9142-D4209CE2D51F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"546a912e551c9addccc5ab8199d3d2ae84e6a871","datavalue":{"value":{"text":"An algorithm for computing certified approximate GCD of \\(n\\) univariate polynomials","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1295792$77F804AF-3F14-4775-B152-570B13941311","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c2adb8853f841cc33b38330ba1f2b2e42a2419b4","datavalue":{"value":"0964.12007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1295792$9CB65A79-A180-4235-A44E-08DAF82C572E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"eca9376593a688c4dd7d54768e68e85e11b0fb4f","datavalue":{"value":"10.1016/S0022-4049(99)00014-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1295792$5F2D9292-D725-4AA4-8A9B-9953A6DD6064","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"814882c486ae5317781c62b0859bc0964a154f9b","datavalue":{"value":{"entity-type":"item","numeric-id":697490,"id":"Q697490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1295792$8DF5EEE8-1153-4382-AF0D-7B6ADC3EF509","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"34a2791b3d9645796ba9cdff19dd05bcf40f0161","datavalue":{"value":{"entity-type":"item","numeric-id":168348,"id":"Q168348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1295792$31F3BD76-C751-4A21-B31F-AE885A352E1C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"76d94a7b1e587501bbc9ea43d730e11e3978e76c","datavalue":{"value":{"time":"+2000-06-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":"Q1295792$2FB7238F-D333-455B-B081-02B9A3D6FD70","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5b5b15201b494a4e8d296c84a83500b82a3e9f41","datavalue":{"value":"The paper presents two algorithms for the problem of finding approximate gcd of \\(n\\) univariate polynomials. More precisely: Given a tolerance \\(\\varepsilon\\) and polynomials \\(P1,\\ldots ,P_n\\) of degree \\(d_i\\), respectively, find perturbations \\(\\delta P_i\\) and a divisor \\(D\\) of \\(P_i+\\delta P_i\\) satisfying: (i) \\(\\deg \\delta P_i \\leq d_i\\), (ii) \\(||\\delta P_1,\\ldots ,\\delta P_n||< \\varepsilon\\), (iii) \\(D\\) has maximum degree.    The author uses generalized Sylvester matrices together with Singular Value Decomposition (allowing a numerical approach) to device both algorithms. Bounds for the degree of the approximate gcd are obtained. Moreover, the first algorithm provides a certification of the degree. New algorithms for the problem with two polynomials are suggested. Finally, numerical examples with timings are presented, illustrating his computer implementation.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1295792$D6DC04AC-A791-4011-97AE-0AF8C0FE5E7E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"661c831991cdebd51f9465b74d929024bd00f373","datavalue":{"value":"12Y05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1295792$0EEE97EF-EB82-4DBA-BB62-098FEF775E85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"72309745094959b676ca20810c7af21a33fe24b5","datavalue":{"value":"65F30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1295792$F07E4B32-2380-4382-8AE2-273FB758DE0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b353ca9fa5871b5d283994bd1f10d77c55504354","datavalue":{"value":"15A18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1295792$D730DDF5-B84A-40A4-89AF-8E70B00B2D55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"34a168fb3a5d9a7cf8cac2cdc24ae08d3f435434","datavalue":{"value":"65Y99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1295792$BD3B21B1-0E45-4582-A3FB-6B2CDD40E25D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1295792$9D7F8AA8-59D0-4978-96D5-ED16F55A685B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"597418c7340091ceee5ff6e24d2462b2ba142687","datavalue":{"value":"1308385","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1295792$87284A6A-DE04-464A-B45C-D7AF0178137C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"552468cd930553c64b4a0a92f95cce7cfd329626","datavalue":{"value":"Approximate GCD","type":"string"},"datatype":"string"},"type":"statement","id":"Q1295792$8ECAC7C3-3FCB-42A2-9F37-A8CEC6A1F956","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8d8dddb68265b6cf122a1e8ad5df14a6ac77388d","datavalue":{"value":"Sylvester matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1295792$DF26D256-03F2-4944-860B-6066AF0C94E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6b0eb84cda78c907f2761c454ef4293368d479f4","datavalue":{"value":"Singular Value Decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1295792$EBFC0407-4FE8-4630-B6BE-25239CAE3B21","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2fbaabd45ced54cadc0390bc9cd343b83bec0729","datavalue":{"value":{"entity-type":"item","numeric-id":307804,"id":"Q307804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1295792$01A5D537-A3F1-4B6B-A891-7F89819967BF","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":"Q1295792$3482EC94-CCB3-4B6E-9264-FA1688B92D8A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"440dbe2d0615a5fcca4aa68dda719baf61e366e5","datavalue":{"value":{"entity-type":"item","numeric-id":805783,"id":"Q805783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1295792$D5CD0894-09A9-4E03-9BB8-74FC5F644DEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e168dfcebeafde675333ae154971a6460f96769","datavalue":{"value":{"entity-type":"item","numeric-id":4227296,"id":"Q4227296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1295792$7CA24DF8-61E0-46A7-B398-E43FB60D6915","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"edb39679cafecd816204040dbc2a52f3775bf7e9","datavalue":{"value":{"entity-type":"item","numeric-id":4717942,"id":"Q4717942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1295792$B69C0FE7-5E7D-4F95-98F4-C28B28DAE0F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73e1dc79f3dc875c2eeea6b8127c1c35bd877811","datavalue":{"value":{"entity-type":"item","numeric-id":1358910,"id":"Q1358910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1295792$A71E1DF4-C505-4015-AE01-38A5CEA0D9AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ced5cfe1b079ebdc8de66d106a03be7ec616709a","datavalue":{"value":{"entity-type":"item","numeric-id":3359644,"id":"Q3359644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1295792$D2B187AF-0381-46BB-982D-0C6CBA873CDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ad9b2df3a83e6786ffa3d9dbc682b658369b266","datavalue":{"value":{"entity-type":"item","numeric-id":1382032,"id":"Q1382032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1295792$66AECD64-5B94-47C0-8742-ED2F0EB6B9E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c15d44de43310ad23688eeca3f93979f3ef1bdf","datavalue":{"value":{"entity-type":"item","numeric-id":4227320,"id":"Q4227320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1295792$DBBDF712-28FE-4FB8-91E1-0F54676D9BB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a4cd3de16c4efd533439b26ec2a095075dc4dc7","datavalue":{"value":{"entity-type":"item","numeric-id":3992572,"id":"Q3992572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1295792$06CDBE00-D947-4397-AD45-385525F0377F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a46bae57402850d1b09e90dfd690bf82bd74b63a","datavalue":{"value":{"entity-type":"item","numeric-id":1071503,"id":"Q1071503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1295792$99C1A00B-521F-4DEC-80B1-8C0B98AFDF1A","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"53efcb6f1a0bd691bfa4566a4ba03eb9c2ac67cd","datavalue":{"value":"Q126351598","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1295792$44373E0A-70D0-4793-AE0D-AC96895F29D3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6cca7f430d32291103e4a537735b2f4d1be2f26e","datavalue":{"value":"https://doi.org/10.1016/s0022-4049(99)00014-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1295792$0D269EBE-7580-4E81-8D4D-33C102819B48","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5166870def472d80699d12bf9da669a3b41ec314","datavalue":{"value":"W2109445883","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1295792$ED761A1A-A33D-443B-B7E2-DBE0532D710A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"678ac9c71492890ea5918048d989c3e0c6281f42","datavalue":{"value":{"entity-type":"item","numeric-id":1994881,"id":"Q1994881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b106209d5b843d7d9c9908c6531f2d9fa351aa97","datavalue":{"value":{"amount":"+0.9583468","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1295792$465B4D87-8707-4CE3-AF1A-4BD35ADCAF12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2146d5c575ea137ddf43f5ab74897ba07231cf6c","datavalue":{"value":{"entity-type":"item","numeric-id":1281842,"id":"Q1281842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"95c28a313f546871bb525527e3e2607659825d62","datavalue":{"value":{"amount":"+0.9476924","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1295792$6D5423F3-C484-460D-814C-29A4BA8F8765","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f4cc63b3a3c5feb509b67dbb3d753a53ed928f0f","datavalue":{"value":{"entity-type":"item","numeric-id":2883839,"id":"Q2883839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b4bc3e80f6262b3cf4017a089447e73473db39d","datavalue":{"value":{"amount":"+0.9413248","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1295792$A303D9EF-3834-4EE2-B870-835CCA1017E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc734f4de89cec8d60daf2ee6d7ea92606992efd","datavalue":{"value":{"entity-type":"item","numeric-id":1854432,"id":"Q1854432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ba95dc5116005bd76f32ea99520c21d0de9a08b","datavalue":{"value":{"amount":"+0.9370484","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1295792$091FA6A5-4706-4B53-A2CB-CEC192CB96E8","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":"2b20737a67861b0287116bfc3203a2cbae6c6816","datavalue":{"value":{"amount":"+0.93603057","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1295792$5A22AE6D-44C5-4067-9E70-19E30FB2AE33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77268c52d7799dc196ab05106c8cd9d2332a33a0","datavalue":{"value":{"entity-type":"item","numeric-id":385007,"id":"Q385007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05638ebe100608d6deae787e4e9798a376b51f65","datavalue":{"value":{"amount":"+0.93341416","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1295792$62F6EF71-B7B6-421A-8066-696D494CE410","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e1120f3988a0184d02aa74234302c5aef4103a8","datavalue":{"value":{"entity-type":"item","numeric-id":412204,"id":"Q412204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c7c8cfdd78b1cab61057fce85b9395c2d584bb9","datavalue":{"value":{"amount":"+0.93197346","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1295792$21CBFF25-84ED-41B7-9EA1-97E84E2F7AF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1e649243a3e3848dc4299517bffe549860fd72b","datavalue":{"value":{"entity-type":"item","numeric-id":466858,"id":"Q466858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"262cba456eb30991d7d1175072730c5f3a5c53da","datavalue":{"value":{"amount":"+0.9251517","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1295792$FC6CCAA3-3ED9-49A9-B03A-47A6CFE1DBB4","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":"f74818d7c2fa475a5aca4985f83937c9266c0ae3","datavalue":{"value":{"amount":"+0.924576","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1295792$2E123F0F-9CD2-4BEA-A3C0-3D93AD4D498F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d99d2a15166e92ce3a7a7dd6d0290ecc894f5b1","datavalue":{"value":{"entity-type":"item","numeric-id":1358910,"id":"Q1358910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d373aaf604177b0e633ee04e6ebadcb4d31e07e1","datavalue":{"value":{"amount":"+0.9234959","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1295792$7EE3801B-6E5C-4D5D-B6EB-9B31CC640CC4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1295792","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1295792"}}}}}