{"entities":{"Q1179031":{"pageid":1189780,"ns":120,"title":"Item:Q1179031","lastrevid":66512874,"modified":"2026-04-12T10:34:56Z","type":"item","id":"Q1179031","labels":{"en":{"language":"en","value":"The parallel complexity of function approximation"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 23777"}},"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":"Q1179031$BEAF61CF-0375-43BC-83BB-551417C6DDAB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4976b6d104f8b0f28e598f56aae2f0a96dfeb5a3","datavalue":{"value":{"text":"The parallel complexity of function approximation","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1179031$A30913F3-31ED-444A-8233-DC562814E38A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dcfaee7bf6f0f8c470ca578b9a9f37ae8275c317","datavalue":{"value":"0741.68058","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179031$BD02D636-C48B-415A-AA9E-272F4E124CAC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4a75bd762f3bd01ec445ecd26816b111f12aa3cd","datavalue":{"value":"10.1016/0885-064X(91)90005-I","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179031$F9FF4587-4BC3-4089-B1B9-67C29FD5F3C6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1ca594a5829e436ff2b15fe8bac44c9ca40882eb","datavalue":{"value":{"entity-type":"item","numeric-id":1179029,"id":"Q1179029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179031$3D58D744-6415-4D5E-82CE-29ADE09EAA1B","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":"Q1179031$39DD4136-C13D-4197-A721-CCEE4379F25A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1422b5e3113eee9dc98f0455d275631058399b8b","datavalue":{"value":{"time":"+1992-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":"Q1179031$630AB7AE-21B3-4328-8EC8-A69F5C520590","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0f77ae07f6bb60a20c261df0ac20cb807dd219d8","datavalue":{"value":"The author defines a parallel algorithm \\(\\phi\\) with \\(n\\) input variables \\(x_ 1,\\dots,x_ n\\) as a finite directed graph \\((G,M)\\) having the following properties (\\(G\\) being the set of nodes, \\(M\\) the set of edges, \\(M\\subset G\\times G)\\):   1. \\(G\\subseteq\\{N\\cup\\{0\\}\\}\\times N\\) and \\((0,1),\\dots,(0,n)\\in G\\) (\\(N\\) is the set of natural numbers). 2. Every node \\((j,k)\\in G\\) with \\(j>0\\) has exactly 2 incoming edges: \\(((j_ l,k_ l),(j,k))\\), \\(((j_ r,k_ r),(j,k))\\in M\\), where \\(jl,j_ r<j\\). 3. To every node \\((j,k)\\), \\(j>0\\), belongs an operation \\(op(j,k)\\in\\{+,-,\\ast\\}\\).   To each node \\((j,k)\\) of an algorithm \\(\\phi\\) is associated recursively a function \\(\\psi_{(j,k)}\\) of the input variables as follows:   \\(\\psi_{(0,k)}(x_ 1,\\dots,x_ n)=x_ k\\) if \\(1\\leq k\\leq n\\),   \\(\\psi_{(0,k)}(x_ 1,\\dots,x_ n)=a_ k\\) if \\(k\\geq n\\),   \\(\\psi_{(j,k)}(x_ 1,\\dots,x_ n)=\\psi_{(j_ l,k_ l)}(x_ 1,\\dots,x_ n) op(j,k)\\psi_{(j_ r,k_ r)}(x_ 1,\\dots,x_ n)\\) if \\(j>1\\).   The real numbers \\(a_ k\\) are the input constants. The interpretation of this is that at time step \\(j>0\\) the processor number \\(k\\) performs the operation \\(op(j,k)\\) at the operands \\(\\psi_{(j_ l,k_ l)}(x_ 1,\\dots,x_ n)\\), \\(\\psi_{(j_ r,k_ r)}(x_ 1,\\dots,x_ n)\\).   The complexity of a prallel algorithm is given by   \\(\\hbox{comp} \\phi=\\max\\{j\\in N\\mid\\;\\exists k\\in N:\\;(j,k)\\in G\\}\\)   and the parallelism of \\(\\phi\\) is defined by   \\(p(\\phi)=\\max\\{\\hbox{card}\\{(j,k)\\in G\\mid\\;j=l\\}\\mid\\;l\\in N\\}\\).   If \\(f: R^ n\\to R^ 1\\), it is said that the parallel algorithm \\(\\phi\\) computes the function \\(f\\), if there exists a \\((j_ 0,k_ 0)\\in G\\) such that \\(\\psi_{(j_ \\sigma,k_ \\sigma)}(x)=f(x)\\) for all \\(x=(x_ 1,\\dots,x_ n)\\in R^ n\\). For every number \\(p\\) of processors, \\(1\\leq p\\leq\\infty\\), the parallel complexity of a function \\(f\\) is given by   \\(p-\\hbox{comp} f=\\min\\{\\hbox{comp} \\phi\\mid\\;\\phi\\hbox{ computes }f,\\;p(\\phi)\\leq p\\}\\).   If \\(\\Lambda\\) is a class of functions, then define   \\(p-\\hbox{comp}(\\Lambda)=\\max\\{p-\\hbox{comp} q\\mid\\;q\\in\\Lambda\\}\\).   If \\(\\Lambda\\) is a class of functions \\(f: M\\to R^ 1\\), \\(M\\subset R^ n\\), then for \\(f\\in\\Lambda\\) define   \\(p-\\hbox{comp}(f;\\varepsilon)=\\min\\{p-\\hbox{comp} \\phi\\mid\\;\\phi\\hbox{ computes a } \\psi\\hbox{ with } |\\psi(x)-f(x)|\\leq\\varepsilon\\}\\) for all \\(x\\in M\\) and    \\(p-\\hbox{comp}(\\Lambda;\\varepsilon)= \\max\\{p- \\hbox{comp}(f;\\varepsilon)\\mid\\;f\\in\\Lambda\\}\\).   The author obtains lower and upper bounds for \\(p-\\hbox{comp}(P^ r)\\), \\(p-\\hbox{comp}(P_ r)\\), \\(1\\leq p\\leq\\infty\\), where \\(P^ r\\) resp. \\(P_ r\\) is the set of polynomials in \\(R^ n\\) of the degree at most \\(r\\) resp. of the degree at most \\(r\\) in regard to separate variables. He also obtains bounds for \\(p-\\hbox{comp}(\\Lambda:\\varepsilon)\\) for some classes \\(\\Lambda\\) of continuous functions.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179031$A5D30FD8-6A7B-4968-BF35-67556346EBB2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179031$1D7CDD00-AF10-4426-AFF4-2EA4BC4407BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179031$AFCC2D56-6820-49E4-BE00-ECC79341E782","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b65efe51b183d0f4a672427b8171cd1e14211cba","datavalue":{"value":"68W15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179031$5E483D7F-7FA5-4B25-AB3C-AB934761CA00","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a42585eaeeb19dd1a228a1d5b8e6c3488a0322b9","datavalue":{"value":"23777","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179031$6D49949B-F1D8-4EB7-BD40-47ED16761E3C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a63f5fdf3038af45049408a9914d671beb783a5b","datavalue":{"value":"parallel complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179031$86523207-3559-41CB-90A3-DFA6D1AADC65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1fd67d4be6a7db819059ff28f5cc688aebd262c6","datavalue":{"value":"smooth functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179031$37107C16-83FC-462A-BA5F-6D64B9BE1F2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be6c24aa804f93b31bd8d2c801177c00ad8cfe7d","datavalue":{"value":"lower and upper bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179031$E94D5F4B-EE7D-4421-B693-35DF8CE36126","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"bd5187154a3d7aae10e1b91e11055a21ae04641e","datavalue":{"value":{"entity-type":"item","numeric-id":1119026,"id":"Q1119026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179031$61289DD7-7118-4D08-850C-596E5A911241","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":"Q1179031$BBE368C8-7BF0-4A33-B086-B51EF1F3104C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1efc6d224ffe0d7322355df220a9a0a92863a911","datavalue":{"value":{"entity-type":"item","numeric-id":4729768,"id":"Q4729768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179031$CDCDE8EE-B0D7-4DA1-B794-072559872110","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7b687389392c3c46c787b88133af21d18744004","datavalue":{"value":{"entity-type":"item","numeric-id":4190138,"id":"Q4190138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179031$DDCB1AE8-00B3-4C58-8BFF-EBA9BFA7D338","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2c19e191611e0120d3d8c98278117c77405d920","datavalue":{"value":{"entity-type":"item","numeric-id":5342672,"id":"Q5342672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179031$8B6DE460-4762-456B-8B3C-D2A885F53BD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62032912489f874a59e4a84126ea034a7792b084","datavalue":{"value":{"entity-type":"item","numeric-id":5534403,"id":"Q5534403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179031$CCF4295A-BA9F-4806-9AA9-560FF6B5271E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"952fb59f49bb7ae86dc510383afbedaec943f28f","datavalue":{"value":{"entity-type":"item","numeric-id":5540797,"id":"Q5540797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179031$3C65968D-6083-4D06-906E-15BAF783F280","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c17eeef34ee60cf8283e4ce3f1572481637cced5","datavalue":{"value":{"entity-type":"item","numeric-id":3928118,"id":"Q3928118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179031$1BBF7CC5-D501-4C9C-9006-CDF3E94C6AC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f426299e08ffae4b6c6a3d62bf6caaebb7ac204c","datavalue":{"value":{"entity-type":"item","numeric-id":3690212,"id":"Q3690212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179031$892230A2-1B9D-4779-AF70-E63BBA73D5FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba0d6b6280d649206ce50622657adf1acf3d3d02","datavalue":{"value":{"entity-type":"item","numeric-id":3257942,"id":"Q3257942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179031$5710282C-4CC9-4D2E-91B1-1A07E5AE4701","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5384161ad85b784e9c2632d7b4752e591fd1a264","datavalue":{"value":{"entity-type":"item","numeric-id":2638779,"id":"Q2638779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179031$05F646C1-919B-4926-8939-4465F9F72119","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fd412bcfdfc40b3432c1aad481107d905db51ac","datavalue":{"value":{"entity-type":"item","numeric-id":5562739,"id":"Q5562739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179031$8DA169D7-C056-49B0-81AB-68FAE098F5DA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5bedaa58053f0cc546ac14a7fd1b02e71f73d0ca","datavalue":{"value":{"entity-type":"item","numeric-id":1186504,"id":"Q1186504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c30eae0694fa0a98211f6af6a3f4bc84166d63b3","datavalue":{"value":{"amount":"+0.8268293142318726","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":"Q1179031$07F9BA25-27FF-4006-A6DF-691AE3A25999","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca8bf3d4a058e02663ba2235f80f1e187245b1e4","datavalue":{"value":{"entity-type":"item","numeric-id":804282,"id":"Q804282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"419600f654dfe13e45cc9f4a4995e54b99bc76e8","datavalue":{"value":{"amount":"+0.7965975403785706","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":"Q1179031$6133DC4E-741E-416E-886C-128F5390D101","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aff0957f14d07791b15e7d2ec962d401fccc87e5","datavalue":{"value":{"entity-type":"item","numeric-id":3474278,"id":"Q3474278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"473d81a3f7efd6885e447a0c0096cd1c222b18ae","datavalue":{"value":{"amount":"+0.7810397148132324","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":"Q1179031$4D0186A8-0614-4745-8FFF-E7FEF2116844","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2fc39451945a25537b27beba6150ba82f5fdf19b","datavalue":{"value":{"entity-type":"item","numeric-id":4870650,"id":"Q4870650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0fb60da875d13208a1b21073044d6d6d1e5fdc3a","datavalue":{"value":{"amount":"+0.7774357199668884","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":"Q1179031$58035D27-9A5F-4691-BEB0-6D07E8454628","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The parallel complexity of function approximation","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_parallel_complexity_of_function_approximation"}}}}}