{"entities":{"Q582007":{"pageid":583774,"ns":120,"title":"Item:Q582007","lastrevid":49340878,"modified":"2026-01-07T00:06:10Z","type":"item","id":"Q582007","labels":{"en":{"language":"en","value":"Topological complexity of a root finding algorithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4129892"}},"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":"Q582007$375D336A-8EB8-4141-9710-38F21F8DAC1F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7738577bcb6ccf6716e81ed85e86744ad857b2b3","datavalue":{"value":{"text":"Topological complexity of a root finding algorithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q582007$4549749D-3DC8-4E04-8108-D352922FE208","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1096bd6edce502e6bdaef1aee6308564de962485","datavalue":{"value":"0689.65030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582007$6C18D46F-63FB-48D9-BC5C-5552DCBD3F13","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"84a38fdce8f3fe47908d4940aa42d9340d01def4","datavalue":{"value":"10.1016/0885-064X(89)90029-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582007$7C7214FC-B67F-4699-A9BA-82E4FFFA9564","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"99a182f0b4a776c91817d685cb2eab7d30c2e89f","datavalue":{"value":{"entity-type":"item","numeric-id":582006,"id":"Q582006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582007$A027B7F0-0DE6-4CB4-AC8D-6445EAB626FB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f728e963338f0590fef2609026707340c65ee9d2","datavalue":{"value":{"entity-type":"item","numeric-id":162057,"id":"Q162057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582007$3AC8D68D-592D-4195-B65C-3CF571988A1C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q582007$D30D4BDD-6205-4407-B564-57CEAF1C50EA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7385ed775790fdd135c53de103cd79f476a902b1","datavalue":{"value":"Defining the set of the polynomials by \\(P_ d(1)=\\{f(z)=\\sum^{d}_{j=0}a_ jz^ j,\\quad a_ d=1,\\quad | a_ j| \\leq 1\\},\\) the author proposes an algorithm for solving the following problem: For any \\(f\\in P_ d(1)\\), any \\(\\epsilon >0\\), find \\(\\{x_ j\\}\\) j-1,...,d, such that \\(| x_ j-\\xi_ j| \\leq \\epsilon\\), where \\(f(z)=\\prod^{d}_{j-1}(z-\\xi_ j).\\)    The paper is focused on minimizing the branching nodes (or topological complexity) appearing in the algorithm. It is shown that the topological complexity of the proposed algorithm is (d-1) and the depth of this algorithm is (log d). For a subclass of \\(P_ d(1)\\) of real polynomials with only real roots an algorithm is given which always finds all d \\(\\epsilon\\)-roots, i.e. the topological complexity is 0.","type":"string"},"datatype":"string"},"type":"statement","id":"Q582007$8287846D-420E-42A8-A9D4-CAEE5CEACB17","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f7c34836818ffbea9a518ee3069a773adc88b483","datavalue":{"value":"65H05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582007$F5FAAF6C-04C5-4E03-AD4C-B7FEBEB3F5AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582007$A7078B2C-C258-4135-ABDC-6FDF5829012A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"28cc557c6c35aaa162b4d5c0a30d55d28da55f24","datavalue":{"value":"26C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582007$4EDF0DCA-4D3A-4F5E-88F7-59DFE8D3485D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8871fa000545a707dc0c8eb8145c5cf9a99c7e40","datavalue":{"value":"30C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582007$897AEE97-A596-4063-9C82-60CDA0A7E096","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7a7421668a57076c36921f4f5e1cda9aa307770b","datavalue":{"value":"4129892","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582007$E74EBDD1-5F47-4AD0-956D-FFD499A790FA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3acd5923c97c149020165f1d61eb2fa68f47f750","datavalue":{"value":"root finding algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q582007$1B0881D3-EF46-4603-9509-AFC1EED8DA01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf8ea604a0caa84f4d4c668f209db78531490820","datavalue":{"value":"zeros of polynomials","type":"string"},"datatype":"string"},"type":"statement","id":"Q582007$BAC0E89C-E45C-40E1-9B98-9DD358AEE6A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q582007$615D8280-A478-42B7-986B-2E4651797736","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"012d977463d5424ed98c7a8122956bd77f6e0b35","datavalue":{"value":"topological complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q582007$9ED9326D-5362-4788-83E4-0B50E086FAD6","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"32b61be5a8579cbff56f3ae053504391f67cfee3","datavalue":{"value":{"entity-type":"item","numeric-id":587430,"id":"Q587430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582007$86B7FB38-7793-4319-A25A-9E8D476ED196","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":"Q582007$1D4AA9AC-3C0F-4518-9819-E20DEBE0AEE8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7be6d702681e99b0ccab415381817ca346e3964e","datavalue":{"value":{"entity-type":"item","numeric-id":3285751,"id":"Q3285751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582007$3C542987-0EF1-46E8-A643-9D9DAEBC0B2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ca9760eaf43c20583dc35af9bc1cbf2105dab26","datavalue":{"value":{"entity-type":"item","numeric-id":3028211,"id":"Q3028211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582007$09862F69-1195-4DDB-8780-ADAC6F28F00E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f7eccd52ba0c2f4f3799d1244a47fded1da28e9","datavalue":{"value":{"entity-type":"item","numeric-id":3904686,"id":"Q3904686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582007$AED337E7-F045-48F7-AC7A-403CD48F7BB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad1b4d13f9cd94948cd300eb11a60522142555e3","datavalue":{"value":{"entity-type":"item","numeric-id":3721699,"id":"Q3721699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582007$48519EA0-C8E9-477E-9FE3-409D60AA99EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1959864393df920e2e4af3b07395c2ebb46cc880","datavalue":{"value":{"entity-type":"item","numeric-id":1099953,"id":"Q1099953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582007$340FAA94-8020-4499-9301-6FFE5392E246","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2f227dd4b3c4f631bf03c458153dbd301d529b90","datavalue":{"value":"https://doi.org/10.1016/0885-064x(89)90029-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q582007$4DE15B03-16C7-46A0-83E0-0870FC2974B2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"eb5a98bbf113adee422d61537d7cb2e6204ef90c","datavalue":{"value":"W2077918470","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582007$3700DAAD-B044-4356-BDB6-C45C5DCB3781","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e5a477d6152cae7e7be98df8b5c24d54b3f110a","datavalue":{"value":{"entity-type":"item","numeric-id":1387387,"id":"Q1387387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86160d143f5c941f7d780a2f652739e37a003feb","datavalue":{"value":{"amount":"+0.916126310825348","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":"Q582007$5C4B655F-3684-4EAD-A8E1-1AE0833FA9F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"05f0b3556de0553ec8af9e49365cd573bffb2191","datavalue":{"value":{"entity-type":"item","numeric-id":3359764,"id":"Q3359764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16f865ea2acc58004a55392e659a2695d9f69711","datavalue":{"value":{"amount":"+0.879123330116272","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":"Q582007$806EA0EE-A615-4BB1-BB34-335022DE2D05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c6740e13ca845a867cea1410bfc8014df9b9f05","datavalue":{"value":{"entity-type":"item","numeric-id":1099953,"id":"Q1099953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5603374a6d017ee0357845cb0e59d9cf33283864","datavalue":{"value":{"amount":"+0.8739043474197388","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":"Q582007$358FB01E-781E-4B28-8323-E13322B28B5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b47e1f97527130d0377c8f99b12d28c60cbc2bb","datavalue":{"value":{"entity-type":"item","numeric-id":4717968,"id":"Q4717968"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"463d30d44e0bd8d0ab117a7d739e095e36cd20dc","datavalue":{"value":{"amount":"+0.8642353415489197","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":"Q582007$032B456B-B4C7-4DAD-A218-28B9AD436149","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ddccb15a92506e5990ece6d5f634c8d9953ac43c","datavalue":{"value":{"entity-type":"item","numeric-id":4291566,"id":"Q4291566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d4552941a1cda69f12797a8971ccf617690377c7","datavalue":{"value":{"amount":"+0.8409161567687988","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":"Q582007$A0A4DF91-862F-4F81-AF68-6FA5249FAD33","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:582007","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:582007"}}}}}