{"entities":{"Q1973275":{"pageid":1984017,"ns":120,"title":"Item:Q1973275","lastrevid":46915272,"modified":"2025-12-25T20:35:19Z","type":"item","id":"Q1973275","labels":{"en":{"language":"en","value":"Asymptotic complexity of Monte Carlo methods for solving linear systems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1436923"}},"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":"Q1973275$5E5BEE87-748F-41AB-915E-31C0502E1ED1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c8ae6e6edb96d39cbe4eb511ae60df2fa9b0f351","datavalue":{"value":{"text":"Asymptotic complexity of Monte Carlo methods for solving linear systems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1973275$61DEE082-E169-4DD5-AF85-1501327E42DA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"331eec41790e7f8b8b941460fff59dc7f05d166e","datavalue":{"value":"0972.65025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1973275$F5B81FCF-DB2D-49AD-8DEF-CA57F4E2C0A1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bcfec539a906d1b76d3f7c3d7e816c839af25750","datavalue":{"value":"10.1016/S0378-3758(99)00060-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1973275$926A4F93-E7E1-4141-BCC4-2C1AC0EA7714","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"179017faa85e752b7b31ffc4d2f48d0cbb6bead5","datavalue":{"value":{"entity-type":"item","numeric-id":1373584,"id":"Q1373584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1973275$9FCCCD80-3C90-4E93-ACFF-CF64180D096C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cbacfcb77fbb0d56315d5395dcbe0931664e2380","datavalue":{"value":{"entity-type":"item","numeric-id":1174333,"id":"Q1174333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1973275$997F5CB4-23A4-4B70-8060-748ADDC4C34B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"aa7a17153b7bd1862e5dc2096a1f2b5a8539b176","datavalue":{"value":{"entity-type":"item","numeric-id":1742111,"id":"Q1742111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1973275$9C67AF03-3D24-480D-8E70-B56B13430A6E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c4f1d146edae4b7d1fb7c199d8e4d54181e32d52","datavalue":{"value":{"entity-type":"item","numeric-id":62245,"id":"Q62245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1973275$91D94CC1-C672-4587-8CB7-244D5CC32AB3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f463ba8dc66fb17d66e4b57732786affbeaa4904","datavalue":{"value":{"time":"+2001-11-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1973275$D2297B6A-B577-45CA-BD50-FAE5C488E328","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f52854697d61b5782050a455201a7a6fad164f8d","datavalue":{"value":"The authors study and compare the complexity of two methods for solving a system of \\(d\\) linear equations \\(x = Ax +g\\) where the spectral radius \\(\\rho (|A |)\\) of the matrix \\(|A |\\) with elements \\(|a_{ij} |\\) is less than 1. The complexity of the (deterministic) method of successive iteration is the number \\(T_I (\\varepsilon, A) \\) of arithmetic operations needed to calculate an approximate solution of accuracy \\(\\leq \\varepsilon \\). The complexity of the von Neumann-Ulam Monte Carlo method is defined as the average number \\(ET(A,\\varepsilon)\\) of arithmetic operations required to get a confidence interval for the solution with width \\(\\varepsilon\\).    The main result of the paper shows that for symmetric matrices \\(A\\) with \\(\\geq Cd^{1+\\alpha}\\), \\(\\alpha >0,\\) non-zero elements and \\(\\rho(A)\\leq q <1\\) the ratio \\(ET(A,\\varepsilon)/T_I(\\varepsilon,A)\\) is of order \\(O(\\log d /\\varepsilon^2 d^2)\\) as \\(d \\to \\infty\\). Thus, for small dimensions the stochastic algorithm gives with the same computational effort less accuracy than the deterministic method, but as the dimension becomes large the attainable accuracy \\(\\varepsilon\\) improves nearly with the order \\(d^{-1}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1973275$12AA5C29-C543-42CA-8954-5C07A83CD47C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9e4257514d9fd4eac10996fc6305328b84fd9c9b","datavalue":{"value":"65F10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1973275$3C8679E5-C949-4761-A1F4-ACEC9B09466F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"63aec181f5f25f527f4a50518ef030353abadcda","datavalue":{"value":"65C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1973275$DD61FB7A-9FD2-4E9E-A139-7884F31297D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"355ea56a4f84d7973d94c70a8b1f92966ec83542","datavalue":{"value":"65Y20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1973275$86642BE1-0B66-4062-AC44-A31ADEB0F8E7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c92a2ddc2cffd00ffc96d52f50397fa180f10c9e","datavalue":{"value":"1436923","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1973275$3CE07742-ACD4-4D08-9C84-0035FDC757B4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1973275$EEC242B3-CE9A-482B-8AE8-0B951BE5EC2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b974a2271f2278f390929a60d648461f74ea9e7a","datavalue":{"value":"von Neumann-Ulam Monte Carlo method","type":"string"},"datatype":"string"},"type":"statement","id":"Q1973275$8A2CFDA9-9772-4D02-8C2D-936EDB06B871","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0f47e4fdc183ef8beb69defca6943946e6f2cb91","datavalue":{"value":"Markov processes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1973275$C4AAB402-BE39-4116-9CD2-69BE32909686","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"783b0e30cf3f83cbe0f901cfa254e291e8e14952","datavalue":{"value":"method of successive iteration","type":"string"},"datatype":"string"},"type":"statement","id":"Q1973275$45950A0D-E828-4EDE-A242-D071A6DCF50E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"126b03fa26c9b86185b2deba3b4744d88a137b1b","datavalue":{"value":"stochastic algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1973275$56D457B4-7CC9-4BC5-9566-F8C87C398FE6","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1e695733bba342c78bfd029e1dcdf7c8e9e4c51c","datavalue":{"value":{"entity-type":"item","numeric-id":188853,"id":"Q188853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1973275$0C32F505-4F2A-4E1F-8DE9-9E24A2A47121","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":"Q1973275$40DD9E35-7878-49B8-AF23-5208B0ABC5A5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb428e55cdecdbeeefd11cfc81b4c8708aa73e4a","datavalue":{"value":{"entity-type":"item","numeric-id":4064914,"id":"Q4064914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1973275$043EFC66-3186-4C95-A3EA-04029AC103F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99ef4062e89df2f225b4ec9d7d9c3e250a455f19","datavalue":{"value":{"entity-type":"item","numeric-id":4893790,"id":"Q4893790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1973275$5F41CF64-01FD-47FB-BC3F-10E128A8358D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3433dda59832b66996e43dd05ce5a23e90cac87","datavalue":{"value":{"entity-type":"item","numeric-id":3994613,"id":"Q3994613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1973275$E6C31DF4-7C96-42EE-99C0-F8BC64742358","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2de4e7d4a64cec0b81a66df673db8cd9c23954d","datavalue":{"value":{"entity-type":"item","numeric-id":4178385,"id":"Q4178385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1973275$F1BDFB2C-06B3-47DC-8A06-AD5144A192A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1342ecc81b8c2e2804ac0cf88903f5c9464b2d1","datavalue":{"value":{"entity-type":"item","numeric-id":5511710,"id":"Q5511710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1973275$353B6A49-0452-4C96-8734-8B6F3ACB4F02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"69ecdbe77c0eb0a44a2b5d8ff620f93830c41c72","datavalue":{"value":{"entity-type":"item","numeric-id":1975767,"id":"Q1975767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1973275$0E827310-C4C9-443C-826F-DF58ED31D75C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4cad8a3b4b63dd0415187276b2afe46569be901","datavalue":{"value":{"entity-type":"item","numeric-id":1422811,"id":"Q1422811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1973275$78407AE1-1BAD-444C-9316-6F0E8F5CEFD8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"95d9816baafce85c9436e6c05df540001a8e5e1d","datavalue":{"value":"https://doi.org/10.1016/s0378-3758(99)00060-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1973275$4ABC07DF-221F-4CBC-B68D-ED5CC86867AA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"70993e48ef0c46aa87c0b89f450dbde87991d526","datavalue":{"value":"W1995228485","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1973275$20A3E6A4-3D00-4E7A-9F91-F56E18E4A8BF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ebb75084752c151b3d650c28d58e0d36fa998c35","datavalue":{"value":{"entity-type":"item","numeric-id":1921611,"id":"Q1921611"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9dc755625e9558386971e7808322e16b12e3cb38","datavalue":{"value":{"amount":"+0.8373996615409851","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":"Q1973275$9976E2FC-21E3-40EE-8C2D-21832BF29F5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b19f14f0831dde3db15c746ebc0067a8dabc73e","datavalue":{"value":{"entity-type":"item","numeric-id":5308921,"id":"Q5308921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ade5c825b6606007ebb98738d831aeb6dbabc7f","datavalue":{"value":{"amount":"+0.835500955581665","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":"Q1973275$1BBC012C-05F7-4231-9F4B-A96E56262C6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45959e0c434aa41ef0685aed19a0ebbd80cf7e2e","datavalue":{"value":{"entity-type":"item","numeric-id":5470329,"id":"Q5470329"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d3ece4a32e5a1d73b468aafed77b44102ccf7bc7","datavalue":{"value":{"amount":"+0.8302260637283325","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":"Q1973275$B31085D5-4D34-4405-8E6B-F6FC11CE829E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b93e90cb66eee7b894c7e83efad33017a3d055a","datavalue":{"value":{"entity-type":"item","numeric-id":5437705,"id":"Q5437705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e4b0f94dcf7257a6f6788bc89fccd8bc61a697bb","datavalue":{"value":{"amount":"+0.809043288230896","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":"Q1973275$706E3FCE-35CA-4163-AEC0-0E3873AA9DA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f762cba3bfa5718934c98dfc935357c5f67129a4","datavalue":{"value":{"entity-type":"item","numeric-id":1120249,"id":"Q1120249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8721e062c0cb5a6d897e79d25a66a6110515cda2","datavalue":{"value":{"amount":"+0.8060755729675293","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":"Q1973275$ECDF1FE8-FC63-4B8C-9352-E215072775CD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1973275","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1973275"}}}}}