{"entities":{"Q6550175":{"pageid":14161329,"ns":120,"title":"Item:Q6550175","lastrevid":57123027,"modified":"2026-03-26T17:09:49Z","type":"item","id":"Q6550175","labels":{"en":{"language":"en","value":"Average-case analysis of the Gaussian elimination with partial pivoting"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7859947"}},"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":"Q6550175$D3601CDE-6265-41EF-A945-26EFB21051B7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fa9d1e997ecadc239ea15cb0aef2b3220b23f1d1","datavalue":{"value":{"text":"Average-case analysis of the Gaussian elimination with partial pivoting","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6550175$9A9E85F3-BAE9-4D66-9128-B4DC3C77EEC7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"11958830bc9f981051c867e544a25159a7e1ea6a","datavalue":{"value":"1542.65036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6550175$69AC7061-B0C6-4DC2-B287-58EF935ADBFD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"75072da852dfcd86b85384e003dc5f73c95cf51c","datavalue":{"value":{"entity-type":"item","numeric-id":713080,"id":"Q713080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6550175$30628908-6904-4EAD-8D23-F8178FF6D1C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ff4614ae9b1db8c24ec9f7af9708c0809b78e652","datavalue":{"value":{"entity-type":"item","numeric-id":313535,"id":"Q313535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6550175$031B5CF8-52C2-4DAC-AB63-8CDF9CD8E626","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e6e97122a60c7ccedaaeb96c6b0234ae8eb3c22d","datavalue":{"value":{"time":"+2024-06-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6550175$48474728-2EFE-444B-8CFC-3117BF1E1690","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"85a22a0f74453e555c92dbc74b85adf31d42beb3","datavalue":{"value":"This fascinating paper deals with Gaussian elimination with partial pivoting (GEPP). The Gaussian elimination is an algorithm for solving systems of linear equations. In the case of the simplest form of the Gaussian elimination with no pivoting, one is interested in solving a linear system \\(Ax = b\\) with a square coefficient matrix \\(A\\) by performing the following \\(LU\\)-factorization: The matrix \\(A\\) is represented as the product \\(LU\\) where \\(L\\) and \\(U\\) are lower and upper triangular matrices respectively, and \\(x\\) is obtained by a combination of forward and back substitutions \\(y := L^{-1}b\\), \\(x := U^{-1}y\\). Many strong results on average-case stability of the Gaussian elimination with no pivoting exist in the literature however GEPP lacks matching theoretical guarantees and justifications that it tends to be more stable than the Gaussian elimination with no pivoting. The paper under review makes significant progress on matching theoretical guarantees and justifications that GEPP tends to be more stable than GE with no pivoting. The authors establish that given a random \\(n\\times n\\) standard Gaussian coefficient matrix \\(A\\), the growth factor of the Gaussian elimination with partial pivoting is at most polynomially large in \\(n\\) with probability close to one. This says that with probability close to one the number of bits of precision sufficient to solve the system \\(Ax = b\\) to \\(m\\) bits of accuracy using GEPP is \\(m + O(\\log n)\\). This improves an earlier estimate \\(m + O(\\log^2 n)\\) of Sanka. The authors also provide tail estimates of the growth factor which can be used to support the empirical observation that GEPP is more stable than Gaussian Elimination with no pivoting.\\N\\NThe paper is very written with an excellent set of references.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6550175$6817D3C0-BE72-4E56-8F7C-5DE2C865BC8C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d3c5d3d5668c9ac83cc76e118c3160e619ad3482","datavalue":{"value":{"entity-type":"item","numeric-id":350691,"id":"Q350691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6550175$0ECA471B-0E84-4075-9EC9-1B8449F41C69","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9885aef811aa349f50c28b046ac04fbe99524c67","datavalue":{"value":"65F05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6550175$7357C564-A1CC-4BC6-9501-EF50B9B1BCCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"70859ede1ca06ac7d3be51584cbccead36f691b1","datavalue":{"value":"15B52","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6550175$81BC4D5D-B2C7-4F27-8206-E477766282B3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4bf0b84737103f06d42d0bbda094789200c463bd","datavalue":{"value":"7859947","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6550175$EB3258E8-7DD3-43B6-BF26-51B4B45B8B6E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a39582725d773f66ea7b763bc55e831ca75ab427","datavalue":{"value":"Gaussian elimination","type":"string"},"datatype":"string"},"type":"statement","id":"Q6550175$5F702AF4-913C-474C-9035-ADD23B085894","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"29ef22b3af0ff2b7639eb6eeb493357093087744","datavalue":{"value":"random matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q6550175$09DF0392-DF50-4258-98A0-F7186DA140FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc51caa0c50e2582ddd1570ab3d82d8caf958848","datavalue":{"value":"partial pivoting","type":"string"},"datatype":"string"},"type":"statement","id":"Q6550175$0DE7566C-032F-4CE6-9BAF-B9538A3AF0E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5d6e072df07c0234e5dcb2bc05341f1acf048880","datavalue":{"value":"GEPP","type":"string"},"datatype":"string"},"type":"statement","id":"Q6550175$413C347F-2426-407C-9B03-67E7AD420268","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":"Q6550175$F661129D-DEC0-425E-9FDD-3E31B9AC5056","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6287f4169a29e56db62b7b05e21dcc02078f249","datavalue":{"value":{"entity-type":"item","numeric-id":4907706,"id":"Q4907706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6550175$84DD2429-8052-4226-852C-2D3DFB8757A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31f572d8581e911140a27033eaa6acf745dc4959","datavalue":{"value":{"entity-type":"item","numeric-id":1094628,"id":"Q1094628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6550175$1D3B79B2-A729-42C5-B403-15D0BADC12A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32978a56cddabcd4c57af0540617dde4a9b0eb68","datavalue":{"value":{"entity-type":"item","numeric-id":3834174,"id":"Q3834174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6550175$353F2090-D846-423F-803F-C0F427407BF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3882f432e3b6faf63da761548b52ed040920e323","datavalue":{"value":{"entity-type":"item","numeric-id":4838122,"id":"Q4838122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6550175$873A42A5-8AF1-4667-B645-2BF88E461F7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c97df777e8f9a013c99de0d677d05988743b6097","datavalue":{"value":{"entity-type":"item","numeric-id":4917542,"id":"Q4917542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6550175$3A23F3D4-9B67-4A78-9347-A66D09D1D204","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c9780e360c20a82366b97eb2acf9b054c360e7e","datavalue":{"value":{"entity-type":"item","numeric-id":4779477,"id":"Q4779477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6550175$51DAB330-93E6-4EE3-95A3-EC09B8C2785B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ea4ddcee830a4b3ed574f334f223fb760ef23af","datavalue":{"value":{"entity-type":"item","numeric-id":5115964,"id":"Q5115964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6550175$5659C36D-7F0C-49FB-87FA-5BBEA21D31F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29e8892e86ef5b98ea59f701cb9e55aeb778ee50","datavalue":{"value":{"entity-type":"item","numeric-id":503274,"id":"Q503274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6550175$61AFA0A0-21B9-4BC3-8DAA-74E60CC3AD61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af347f5255d59983990b6c94fcebc5ae9b48f8fa","datavalue":{"value":{"entity-type":"item","numeric-id":4604394,"id":"Q4604394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6550175$6FFCA66D-9396-4D1A-9A1F-1DC4CCE9B4BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1abd6ba79c642fff96c709ac013379679a369fe","datavalue":{"value":{"entity-type":"item","numeric-id":1655790,"id":"Q1655790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6550175$DB889B98-0CAA-4163-9E0E-A61DE93F4F7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"540efb4ed4782e17338d6760b1832feb99862f0d","datavalue":{"value":{"entity-type":"item","numeric-id":3450223,"id":"Q3450223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6550175$E10E5D68-5D45-4525-AAF2-8992ECCCAB19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1ea0ee2c9ae3ddf996240aac12fb15b32b0caae5","datavalue":{"value":{"entity-type":"item","numeric-id":3435007,"id":"Q3435007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6550175$6FE12673-3578-4367-9E20-0366A1477F55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83dfa9d399554dd90179191ed672661605bfe723","datavalue":{"value":{"entity-type":"item","numeric-id":1760392,"id":"Q1760392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6550175$2E70F355-1476-44C6-BB9E-B3982C4F0725","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81e2d8b82f81fe0ba304ba500fc5cd0f0a47819d","datavalue":{"value":{"entity-type":"item","numeric-id":1179026,"id":"Q1179026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6550175$469270C1-12EE-496C-9403-994A063A7EDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3df3b41d37d27c5afa2c5dbc148739413cf6711","datavalue":{"value":{"entity-type":"item","numeric-id":3482750,"id":"Q3482750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6550175$F148C430-DB24-4C56-A9E7-F8415737B235","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"189badd413ee3575f3e4a352c01f0731d8ea8f40","datavalue":{"value":{"entity-type":"item","numeric-id":5935812,"id":"Q5935812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6550175$18580665-56DE-4411-843D-97219E9F3CE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"083c0ebe3bbc73ba1fd801ad50cd3d2c1acc0fcf","datavalue":{"value":{"entity-type":"item","numeric-id":4643248,"id":"Q4643248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6550175$A3F5D532-3CF8-4C21-9C84-1ABC82A8AB76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb3dc320553e3531a143bb1318994a72f6219c8a","datavalue":{"value":{"entity-type":"item","numeric-id":3845598,"id":"Q3845598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6550175$5BF970AD-6FDA-4FCC-8118-2C42A63D7E0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da5a069e9628f11cbc7feb8164584d6ab10aaddc","datavalue":{"value":{"entity-type":"item","numeric-id":4337395,"id":"Q4337395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6550175$47E196A0-50C7-49B8-AAF1-87C4412D1239","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3e4ddda27c7b76772b0a1708a44a37e8574d8b29","datavalue":{"value":{"entity-type":"item","numeric-id":3036360,"id":"Q3036360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6550175$2C50F117-FEB1-43EF-A1ED-569B7654AAA0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"65ed20aa023c3dce82948a3400c7e54fcb8e5f32","datavalue":{"value":"10.1007/S00440-024-01276-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6550175$012E0059-363E-4D29-9751-1767C7D9A060","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"73da419b5dc2b75b25b21e4bf598d3c692bcb754","datavalue":{"value":{"entity-type":"item","numeric-id":3482750,"id":"Q3482750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"53c24cb8bad4df52d10f918ef10adb6b903d9d39","datavalue":{"value":{"amount":"+0.8464197516441345","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":"Q6550175$84A15300-FDDE-4A44-BE33-8955E6FA1921","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dfc6bfa8642a65a76761289259e5bb31b6901b4e","datavalue":{"value":{"entity-type":"item","numeric-id":4337395,"id":"Q4337395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e5b35ec1e6ff37862a9f0cbdd48dfebfbd95a907","datavalue":{"value":{"amount":"+0.8097987174987793","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":"Q6550175$497992C5-CAF0-4C78-AF4C-8289E7ABF2F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"73fa37ea6ad0dc7125acdc208a807b05aae9ff93","datavalue":{"value":{"entity-type":"item","numeric-id":1827483,"id":"Q1827483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e6deb89b36f08d3ea27dd8b53850391a1648df6d","datavalue":{"value":{"amount":"+0.8006799221038818","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":"Q6550175$C7DA93E6-A630-44B0-9EB3-9436BFC266DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"744059305fa0cd0602ac5b81cd296db95702716c","datavalue":{"value":{"entity-type":"item","numeric-id":1569884,"id":"Q1569884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80a991364afe8acf866d7fe2f25bb8f77803b710","datavalue":{"value":{"amount":"+0.7924261093139648","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":"Q6550175$69EF0C54-22AF-408D-9ACF-B3BD49D10DCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a7b22c87d1694189adbf1b39180c9e6c83e92e3","datavalue":{"value":{"entity-type":"item","numeric-id":1362360,"id":"Q1362360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03bea9ef7a23d4140190e1ef34067afcb7696695","datavalue":{"value":{"amount":"+0.7743670344352722","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":"Q6550175$B3380F00-85A6-4869-87B3-6659FA25EDC0","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6550175$21B539EF-4888-4906-ABEE-007E3851D503","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6550175","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6550175"}}}}}