{"entities":{"Q1095657":{"pageid":1106409,"ns":120,"title":"Item:Q1095657","lastrevid":69826896,"modified":"2026-04-13T10:36:47Z","type":"item","id":"Q1095657","labels":{"en":{"language":"en","value":"A fast numerical algorithm for the composition of power series with complex coefficients"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4028895"}},"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":"Q1095657$1B6EB0B8-C049-4C24-931B-3F88C0D800E0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"06af8a389dc73028dcfba3415cc6aad8d3459e27","datavalue":{"value":{"text":"A fast numerical algorithm for the composition of power series with complex coefficients","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1095657$D1D2BA34-AEDF-41FB-8DD1-A9EBEE195CC2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c718e6d76c7f0ca5d6058e6b62b71fa8d9fa1130","datavalue":{"value":"0632.68039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095657$6365F166-C8B0-4E53-9C9A-451013B00BB7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fe61de497d8db9ae0af38aad505fc6f378de099e","datavalue":{"value":"10.1016/0304-3975(86)90107-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095657$8804BDA7-E501-4774-9D48-BFDF996D1918","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"09024d3d3b3b7a321ad80a472df5249aafeb7903","datavalue":{"value":{"entity-type":"item","numeric-id":1095656,"id":"Q1095656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095657$3BB669CD-2685-4FB9-8F01-AD54FA6E72AA","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095657$6AF3DF68-F119-437C-99C0-5FFCC6873DF7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1095657$29BD474A-83FF-4FCF-BCD8-01939AAF76CE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3961b5c2500503ebdb53ff341e8eb19ab55e6efa","datavalue":{"value":"Let P, Q be formal power series in a variable t over an infinite field K, \\(P(0)=0\\). The composition problem is the task of computing the coefficients of the polynomial \\(Q\\circ P\\) mod \\(t^{n+1}\\) given the first \\(n+1\\) coefficients of P and Q. The best known upper bound for the Ostrowski complexity of this problem is reached by an \\(O(n^{3/2}(\\log n)^{1/2})\\) algorithm due to Brent and Kung. On the other hand no nonlinear lower bound is known so far. The author shows that the composition problem is essentially equivalent to computing only the nth coefficient of \\(Q\\circ P\\). A second result determines the complexity of an approximate version. It is shown that the complexity of computing \\(Q\\circ P\\) mod\\(\\prod^{n}_{i=0}(t-\\epsilon_ i)\\) \\((\\epsilon_ 0,...,\\epsilon_ n\\in K^{\\times}\\) pairwise different) is of order n log n.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095657$31C5A172-9B8B-4A94-9628-829A80F35446","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4b79e10cd9b8c0f9d5fd29c0d2d77f1f9c811d42","datavalue":{"value":{"entity-type":"item","numeric-id":705547,"id":"Q705547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095657$E7ABAE74-07DB-4E9D-83A1-F9868BDF1009","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095657$58B20FBE-0508-431E-96B5-FEAEC4332D70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095657$586C9A05-04D9-4E44-9DE4-C7759B59D90D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"51efc554bfb92b5f7ccc84939ee295c597c8def4","datavalue":{"value":"4028895","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095657$B387A7C6-B799-4650-A98F-9EAEA9DDB5E0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f3590eb8b47f26c41d61639b5166afe44752133e","datavalue":{"value":"formal power series","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095657$E828A4C2-F4C4-4FA2-9744-0E27248D751B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a590632250dd0dce19fe0eccd8498936078a10c3","datavalue":{"value":"composition problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095657$B89D28DE-B854-40E1-B1D1-0A9C6858E13D","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":"Q1095657$69928F97-7CAB-4535-8B0C-D31E6EE20086","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"52205f4a109496467e490fc342489bf5a9892a5a","datavalue":{"value":"https://doi.org/10.1016/0304-3975(86)90107-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1095657$AA15C4AC-C274-4B52-8D61-EBDA5902EDAF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"08d6e69aa5a67243772b35d75f7325c27c1ffabd","datavalue":{"value":"W2030141403","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095657$C47A4F9E-AC7B-4671-94C4-ACA558BB238F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3bfd11a4c1ce94b86c6942c6ee034fea4de139a","datavalue":{"value":{"entity-type":"item","numeric-id":1253097,"id":"Q1253097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095657$1010A831-A8BA-4BDA-A381-B4B39DC695FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56f9c7811c124ca56369c529ee35b195555e21a5","datavalue":{"value":{"entity-type":"item","numeric-id":1171380,"id":"Q1171380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095657$E8D586D6-B6E6-4A27-8625-5FB236FDE8F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6cabc1e92b122cd8a54b27aae806fe27ccb5241","datavalue":{"value":{"entity-type":"item","numeric-id":4170245,"id":"Q4170245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095657$BEE9E23E-192E-48BD-B5CC-7611F621D229","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28df99e75eed7657feddfab656ff7bdee4430b02","datavalue":{"value":{"entity-type":"item","numeric-id":1216049,"id":"Q1216049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095657$010A1967-58CD-4761-89F7-6B4977E2420F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecd9e3f8a36027b7b9841c9e193478610271133a","datavalue":{"value":{"entity-type":"item","numeric-id":3325040,"id":"Q3325040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095657$04BB8B64-9159-4CAE-B4C1-28321CEBAE2D","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":"Q1095657$B789BC95-B38E-4BD8-87A9-3F7FF6674312","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0fe306443dd55a37acf1827ce0f93f62152ca84","datavalue":{"value":{"entity-type":"item","numeric-id":2557116,"id":"Q2557116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095657$10021049-8136-4E94-AD6A-131141F1D334","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b85a9808fa2e37b1e25b3c149d3448127226f96","datavalue":{"value":{"entity-type":"item","numeric-id":2557099,"id":"Q2557099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095657$572D8ABC-6FCC-4021-B37D-00D758CC3CE2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"79b529fa77246ca0f9ca6b69794a82cc36f4741e","datavalue":{"value":{"entity-type":"item","numeric-id":3586258,"id":"Q3586258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ace0d3a0e6d38be3ef547730f92e70e3e61dd74","datavalue":{"value":{"amount":"+0.8113723993301392","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":"Q1095657$96429FE7-CCCF-49DB-A45E-858302262B2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"585f2d087dfa4564695ebe2180dab2711277884e","datavalue":{"value":{"entity-type":"item","numeric-id":1267071,"id":"Q1267071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c9791e28930ca956313a5e94a9a4b6da1274c0e8","datavalue":{"value":{"amount":"+0.7928636074066162","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":"Q1095657$178E2F22-51A8-4589-8C33-F26F3844AB30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1fd0256e8fee215a49446df347ea61bd30fd6544","datavalue":{"value":{"entity-type":"item","numeric-id":5301633,"id":"Q5301633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d07728b02a5dc30f5517d292ef4c0543b7647b7","datavalue":{"value":{"amount":"+0.7879809737205505","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":"Q1095657$5632AF8A-79FE-424C-8D02-F24E28DC24A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa93ff95b162a488aa9bc156b08033bfc186a28d","datavalue":{"value":{"entity-type":"item","numeric-id":5497035,"id":"Q5497035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1703bbf56ccdede22bacac1225493c760e302b33","datavalue":{"value":{"amount":"+0.7826682925224304","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":"Q1095657$5EC99FA3-A1F4-472E-BE55-0311598C28E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85645b31c94dd78bccb59f9914ffb7b2b44430cb","datavalue":{"value":{"entity-type":"item","numeric-id":5119973,"id":"Q5119973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6085446e486d18bb39700af2d780fad2d6f9c211","datavalue":{"value":{"amount":"+0.7821228504180908","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":"Q1095657$D4D2FB9F-2D87-4C96-929A-16FA052ABDEE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A fast numerical algorithm for the composition of power series with complex coefficients","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_fast_numerical_algorithm_for_the_composition_of_power_series_with_complex_coefficients"}}}}}