{"entities":{"Q1186699":{"pageid":1197448,"ns":120,"title":"Item:Q1186699","lastrevid":66799788,"modified":"2026-04-12T12:56:37Z","type":"item","id":"Q1186699","labels":{"en":{"language":"en","value":"An extended polynomial GCD algorithm using Hankel matrices"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 36996"}},"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":"Q1186699$48C5D1FF-3FE2-4A1C-9408-A04D713D0631","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2163169018fd2b588c543bec7f2b6a393df4abac","datavalue":{"value":{"text":"An extended polynomial GCD algorithm using Hankel matrices","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1186699$40CEA141-51AF-48DA-97C5-A76A1231E01B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"85f7d9e9c4e0d424658a9a8c1652aa0741c1a8f4","datavalue":{"value":"0771.15005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186699$F44F0BB1-FE41-4715-8620-94F0D78AFC44","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f6baa5150da96a05bdb2f5a1fb38b0b7d56f3cc0","datavalue":{"value":"10.1016/0747-7171(92)90003-M","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186699$06F4F9C7-571C-41A1-A87B-3EDC4373569A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"207754837a54bbce9b8ebd1d988db3244eb9e100","datavalue":{"value":{"entity-type":"item","numeric-id":1186698,"id":"Q1186698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186699$94D1AEA0-F09E-4683-88EA-8341F55B8BFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3a3ac4f08115a217f5cf89d92ce4fb17fd06164b","datavalue":{"value":{"entity-type":"item","numeric-id":1037649,"id":"Q1037649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186699$8CC90F85-8C30-43B8-BF54-5C09AA5D8889","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":"Q1186699$BF8DA9A1-D81F-47DF-8942-40A5B7E372E4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1186699$18848994-C842-4D68-8DC5-0C9AF7A0C611","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0ea2c4fcf046e1ca76aa52ae675ae6a83d727acc","datavalue":{"value":"For \\(F\\) a field consider univariate polynomials \\(f=f_ nx^ n+\\dots,\\) and \\(g\\in F[x]\\), with \\(\\deg(g)\\leq\\deg(f)=n\\). The sequence \\((d_ i)_{i\\geq 0}\\) defined by \\(g(x)/f(x)=\\sum_{i\\geq 0}d_ ix^{-i}\\) gives rise to a Hankel matrix \\(H_ \\infty=(d_{i+j-1})_{i,j\\geq 1}\\) with \\(r\\times r\\) left upper pricipal submatrices \\(H_ r\\). If \\(H_ m\\), say, is nonsingular one finds a vector \\(\\omega^ m=(a_ 1,\\dots,a_ m)\\) such that \\(\\omega^ m\\cdot H_ m=(d_{m+1},\\dots,d_{2m})\\), and an associated polynomial \\(p_ m(x)=x^ m-a_ mx^{m-1}-\\cdots-a_ 1\\).   Let \\(\\{H_{n_ 0},H_{n_ 1},\\dots,H_{n_ s}\\}\\) be the sequence of all such nonsingular principal submatrices of \\(H_ \\infty\\) and consider the assocaited \\(\\{\\omega^{n_ 0},\\omega^{n_ 1},\\dots,\\omega^{n_ s}\\}\\) and polynomial Hankel sequences (PHS) \\(p_{n_ 0},\\dots,p_{n_ s}\\). Here \\(n_ 0=0\\), \\(1\\leq n_ 1<n_ 2<\\cdots<n_ s\\leq n\\), and the conventions \\(p_ 0=1\\), \\(H_ 0\\) empty but nonsingular, \\(\\omega^ 0\\) empty are used. Let \\(a=-f_ n(\\omega^{n_{s-1}},-1)\\cdot(d_{n_ s},\\dots,d_{n_ s+n_{s- 1}})^ T\\) and define a \\((1+n_{s-1})\\)-square matrix \\(D\\) by \\(D_{ij}=(d_{i+j-n-1})\\), where \\(d\\)'s with negative indices are to be interpreted as zeroes. The main result is that the polynomials defined by \\(v(x)=(1/a)p_{n_{s-1}}(x)\\) and \\(u(x)=-(1/a)(\\omega^{n_{s-1}},- 1)\\cdot D\\cdot (x^{n_{s-1}},\\dots,x,1)^ T\\) satisfy the Hankel extended greatest common (HEGCD) divisor equation \\(u\\cdot f+v\\cdot g=\\text{gcd}(f,g)\\). Pseudo codes for \\(\\text{PHS}(f,g)\\) and \\(\\text{HEGCD}(f,g)=[\\text{gcd}(f,g),u,v]\\) are given. The maximum computing time for HEGCD is \\(O(n^ 9l^ 2)\\) where \\(l=\\max\\{\\log(\\text{norm}(f)),\\log(\\text{norm}(g))\\}\\); the number of operation is \\(O(n^ 2)\\).   The latter number compares favorably with a modular algorithm by \\textit{W. S. Brown} [J. ACM 18, 478-504 (1971; Zbl 0226.65040)]. For related work by the authors see Lect. Notes Comput. Sci. 356, 321-333 (1989; Zbl 0682.15020).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186699$99EFE6D4-3687-4109-9EC9-4ADCEABD716B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"c32074a6a9b33f3199d7f4946756883fac565aa0","datavalue":{"value":"15B57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186699$C50BD483-E473-4370-87D7-58608668EF76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9d105b80ed6a98c28f7c2120246154d24eaf80df","datavalue":{"value":"15A54","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186699$3B74474B-DDE4-42A0-B7DE-3D305B0B9F74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186699$B621140B-9264-440E-B3A8-8DF3871588DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"72309745094959b676ca20810c7af21a33fe24b5","datavalue":{"value":"65F30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186699$BF4C0B40-38D4-4FD8-A17D-1A1096EC25F8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"37e2b3f76036650fa41bcb45ff849b94cfdbcb82","datavalue":{"value":"36996","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186699$8A97772D-4F39-403A-87DF-56C116B47080","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac88c7c4ceb79c868083defb73e33bb7e3d89ba0","datavalue":{"value":"greatest common divisor","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186699$21070846-2AF9-43D7-AC0D-B09C9C19333B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7950860ee87fe00f20a8af86cc446aa4c73bcaab","datavalue":{"value":"extended polynomial GCD algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186699$5478B3A1-A2CA-4746-B208-BE8EA22A8EED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8019dd6d69abf37ba01c1c87ac4872783bcbca6f","datavalue":{"value":"Hankel matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186699$692A3A17-663F-4FC4-8F58-415EF34B2CF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2be129fea592b43f1914be3aeebf94ad9d78e219","datavalue":{"value":"polynomial Hankel sequences","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186699$E922B2C1-A5C5-4D62-81B9-D0F32E0A9496","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4cb749bb0545117c5a39ee1b861da533345043d8","datavalue":{"value":{"entity-type":"item","numeric-id":587686,"id":"Q587686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186699$2A159B38-EC51-4C26-9E50-89024B9AC6F1","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":"Q1186699$121E0DA0-2D12-4A56-9A6D-994C908FDFDD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1047ff1a1c14e5bbc9913a7a397ad9ddee337554","datavalue":{"value":{"entity-type":"item","numeric-id":3952057,"id":"Q3952057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186699$9D55930D-566B-4838-95AF-F33D59FB7C68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2474ba10df186f41753af2a60b363dd32a238373","datavalue":{"value":{"entity-type":"item","numeric-id":5633583,"id":"Q5633583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186699$F0923322-7FC2-493E-976C-820EEC03D74A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c790a28a23b5ecff99b272336c89700604ca255","datavalue":{"value":{"entity-type":"item","numeric-id":3254327,"id":"Q3254327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186699$4E7CEEBD-5C0F-4C2C-A9D7-9DBB29B139B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f70030eb3708727ea2ea3235c28754116ae6bfa","datavalue":{"value":{"entity-type":"item","numeric-id":4731312,"id":"Q4731312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186699$9FBAD2C9-9D10-47D9-8DB5-830764B23854","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"09762bc7e5cb10b5860ce5ca5bdba718588b628e","datavalue":{"value":{"entity-type":"item","numeric-id":3087160,"id":"Q3087160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5c43404a52508056be0f31172cc95bbaf8aa9071","datavalue":{"value":{"amount":"+0.91395754","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":"Q1186699$E3979793-96A7-426B-8D90-FB5868F236B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70c95b62c4b001426060b1d78a850b46675017c7","datavalue":{"value":{"entity-type":"item","numeric-id":5101998,"id":"Q5101998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c97eabcb172185e6a2b7ccf59d54c39854036b4","datavalue":{"value":{"amount":"+0.9105643","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":"Q1186699$43176551-8A7A-4641-B066-B03DA0DE42DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"34b63ce88ae2b6ddd9d72cabe01c1846b3da6428","datavalue":{"value":{"entity-type":"item","numeric-id":3162294,"id":"Q3162294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d242ac6d555477606504c91617274ca13c69a17","datavalue":{"value":{"amount":"+0.90882444","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":"Q1186699$FF105910-C62F-4C52-9B93-1C552150E38B","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":"9332c300c38f740cad9ef3e09ef3d7a6e26c4c9c","datavalue":{"value":{"amount":"+0.8979216","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":"Q1186699$5EB4280E-2665-4E61-8FAD-81D481C125BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5dcc1a82cfcd24841eeff34bc63964fa6c00afd1","datavalue":{"value":{"entity-type":"item","numeric-id":5301644,"id":"Q5301644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aabd066a54a14a6daf602b110d0e51adbc443d2e","datavalue":{"value":{"amount":"+0.89393824","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":"Q1186699$8B201F12-529C-4E0D-AEB0-9D2D113DE427","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d7580f99b59b75a94c02f9c03408f30cc620c3f","datavalue":{"value":{"entity-type":"item","numeric-id":5120202,"id":"Q5120202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18f081bab2b333e54246ec0cc7da0537ed28a0d4","datavalue":{"value":{"amount":"+0.8894983","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":"Q1186699$BDE8E54D-262F-4B2C-8BB0-AE0A334776E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a77e9307b68b9e4cad37afd47b50b0d61583d025","datavalue":{"value":{"entity-type":"item","numeric-id":5423857,"id":"Q5423857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a27255221d55bc412032affd291376bc791d114","datavalue":{"value":{"amount":"+0.8857306","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":"Q1186699$CA99BE73-F2CC-4686-87D4-6607A29A3BAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a4cf2198043113699ae85519546520998cd374a9","datavalue":{"value":{"entity-type":"item","numeric-id":1916729,"id":"Q1916729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ecb3e22edc558623110ec6681b64b10192779068","datavalue":{"value":{"amount":"+0.8850024","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":"Q1186699$056AFA65-2482-4E14-9167-085AF6C32ACA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f673de26ef701b989872c1e137fb68d07981b4ef","datavalue":{"value":{"entity-type":"item","numeric-id":1361353,"id":"Q1361353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6fbd2bfbabcd5b1d4d463916902a25b062120521","datavalue":{"value":{"amount":"+0.883284","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":"Q1186699$451A1650-B288-47F8-86B4-781043C3AA2A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An extended polynomial GCD algorithm using Hankel matrices","badges":[]}}}}}