{"entities":{"Q5940607":{"pageid":8117409,"ns":120,"title":"Item:Q5940607","lastrevid":47655151,"modified":"2026-01-02T08:42:02Z","type":"item","id":"Q5940607","labels":{"en":{"language":"en","value":"The role of arithmetic in fast parallel matrix inversion"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1632042"}},"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":"Q5940607$51A3B467-4CAC-42E7-BE1D-A0363D8CFBCC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"117ff155cc9cde29654c57fcfe5c434ee9018d67","datavalue":{"value":{"text":"The role of arithmetic in fast parallel matrix inversion","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5940607$EFF010AC-028D-4755-8406-C420888D652D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"10d947f5ce0313eeb1f87ff696f3f6a4edb524e2","datavalue":{"value":"0982.65031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5940607$53AD96F3-3E11-441A-BA9D-062919478874","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"99f13638f7a28701b64ce922802aeb47e87b6beb","datavalue":{"value":{"entity-type":"item","numeric-id":918126,"id":"Q918126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5940607$6D9F0D93-2923-44B0-9514-E983F72481DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5d3c23882963549ef688a9b135abbee310291023","datavalue":{"value":{"entity-type":"item","numeric-id":779439,"id":"Q779439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5940607$9A9C5D48-B298-4442-B87A-4FBB88EC6344","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"09a0d0c7c3a8cc7117eaef5e49aac31cce266126","datavalue":{"value":{"entity-type":"item","numeric-id":414867,"id":"Q414867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5940607$0E55BEB9-C031-4220-B11C-84BB6E32739D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5940607$3968EF38-CE65-4455-B7D3-38095FD7665C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"09811d42eddac0306570884e48501ce7068fc838","datavalue":{"value":{"time":"+2001-08-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5940607$4D8C887E-8EB3-483F-91C1-6FC1554C256C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d65ea10125e6e2ab1884b67c2b31d9fe9e42608d","datavalue":{"value":"The authors analyse the numerical behaviour of known fast parallel matrix inversion algorithms, e.g., \\textit{L. Csanky}'s algorithm [SIAM J. Comput. 5, 618-623 (1976; Zbl 0353.68063)], a recursive factorization algorithm [see \\textit{J. H. Reif}, \\({\\mathcal O}(\\log^2n)\\) time efficient parallel factorization of dense, sparse separable, and banded matrices. Proc. 6th ACM Symp. on Parallel Algorithms and Architectures, ACM Press, New York, 278-289 (1994); \\textit{D. Bini} and \\textit{V. Y. Pan}, Polynomial and matrix computations. Vol. I (1994; Zbl 0809.65012)], Gaussian elimination with no pivoting [see \\textit{A. Borodin, J. von zur Gathen}, and \\textit{J. Hopcroft}, Inf. Control 52, 241-256 (1982; Zbl 0507.68020)], and Newton's iterative method [see \\textit{V. Pan} and \\textit{J. H. Reif}, Fast and efficient parallel solution of linear systems. Proc. 17th ACM Symp. on Theory of Computing, AMS, Providence, RI, 143-152 (1985); \\textit{V. Pan} and \\textit{J. H. Reif}, Comput. Math. Appl. 17, No. 11, 1481-1491 (1989; Zbl 0684.65024); \\textit{V. Pan} and \\textit{R. Schreiber}, SIAM J. Sci. Stat. Comput. 12, No. 5, 1109-1131 (1991; Zbl 0733.65023)].    A comparative analysis under both fixed- and variable-precision models of arithmetic is developed. It is shown that Csanky's algorithm, the recursive factorization algorithm, and Gaussian elimination are practically infeasible for computing the exact inverse of an integer matrix of large size. They require word sizes linear or superlinear in the order of the matrix. Only Newton's iterative algorithm admits sufficiently accurate NC (polylogarithmic time) implementations.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5940607$9B4DDD26-A9BD-4878-ABEB-BF7E3F928069","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3d1fc9742b2aa47ee3fa5235cc1ed4d6e7313c7a","datavalue":{"value":{"entity-type":"item","numeric-id":588361,"id":"Q588361"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5940607$E04DAF1C-B863-48D4-95BD-3E37F0498E9A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9885aef811aa349f50c28b046ac04fbe99524c67","datavalue":{"value":"65F05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5940607$7E6560C2-F46C-42AC-A3C9-FBC69FDCAFF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5940607$2B47120B-7434-486C-8059-A51457901C24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9e4257514d9fd4eac10996fc6305328b84fd9c9b","datavalue":{"value":"65F10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5940607$4A0B0BD4-3BA2-47DF-98B2-053CBB683C8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8a7edc01538ef78e7e423d9c49f622de0faa5a14","datavalue":{"value":"65Y05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5940607$989D99AB-6A34-4E1C-9A85-7C90B4A591AC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2b8dd1357d2fa1ea3f0abc138910d15d62617618","datavalue":{"value":"1632042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5940607$22537657-52FD-45EF-8543-94F7D291A297","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d33669a46e6c8e8b36873d1f752821b7694a60c9","datavalue":{"value":"parallel algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q5940607$7A3DFA9C-2AC0-45E9-A11F-79BB8F423158","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"59b0c1a02a224b9fb659082e53fed4a02f3d9545","datavalue":{"value":"matrix inversion","type":"string"},"datatype":"string"},"type":"statement","id":"Q5940607$4FD1D4CC-5C4D-445B-ADC8-C7B38752F523","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3b8d8125665ed970ed391913e939d0240c8a57e4","datavalue":{"value":"computer arithmetic models","type":"string"},"datatype":"string"},"type":"statement","id":"Q5940607$D7F764E8-EC34-42D7-AE63-E7EFE3D51566","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"83c11e7234676c30064ac6c0f8c1cc19cf359958","datavalue":{"value":"Csanky's algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q5940607$2D666387-AD6D-454B-BDCA-347B940B7A7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a39582725d773f66ea7b763bc55e831ca75ab427","datavalue":{"value":"Gaussian elimination","type":"string"},"datatype":"string"},"type":"statement","id":"Q5940607$DCE372AF-7085-409A-8BAA-6E9AB75727D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1736cb68dc4e94b68b37018132c473552b61bdfc","datavalue":{"value":"Newton's method","type":"string"},"datatype":"string"},"type":"statement","id":"Q5940607$6F08DFE4-FDE1-4F04-B70A-52D203107F2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"18c251393a4b87c40303da921625dd229be6e2ef","datavalue":{"value":"variable-precision models","type":"string"},"datatype":"string"},"type":"statement","id":"Q5940607$66345691-E386-4E28-BDAF-2EF843EA82A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d32cca4fb4a95762ec9be54ae4d74d3f1eb64275","datavalue":{"value":"recursive factorization algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q5940607$C4EBD88A-E67A-4877-B05C-8A0E8937CAC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d8a7c045d68d9d1e4eb7e25a6170ff6b4c735c5","datavalue":{"value":"integer matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q5940607$3725A302-457A-49F7-B1B5-63EC728E0589","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e45821b32c01d73604d072faa20d3b8278daebc6","datavalue":{"value":"comparison of methods","type":"string"},"datatype":"string"},"type":"statement","id":"Q5940607$711C80A5-A15A-4854-83B6-9BA24E524C82","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":"Q5940607$F196C55C-A204-430D-A258-BFB9325BA780","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"96938805c850cfdc0e25708592cb8f8c99e1bccb","datavalue":{"value":"https://doi.org/10.1007/s00453-001-0033-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q5940607$3D4C1EB4-42EC-4D55-9976-F747C1CB80F6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c405d1f2244146df89ca41b03960a74f365da9bc","datavalue":{"value":"W1978444682","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5940607$0DD9D286-3F9A-4B2B-BCBA-C20D5FA8C0B5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0a1735c5bf2fb42cba5593b3e9beddf51f653fb7","datavalue":{"value":"10.1007/S00453-001-0033-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5940607$40557428-50E7-4A8B-A831-6D16B0DDCE5B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d774cb248a2401ef63bf68c0fb97cc3190cb70f8","datavalue":{"value":{"entity-type":"item","numeric-id":3732964,"id":"Q3732964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec56999e9481d1666b20d3a14fec5f4110dd8d1e","datavalue":{"value":{"amount":"+0.8635770678520203","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":"Q5940607$7FB4A5B3-0DFB-45C3-A73A-C16C9B06F4FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"14f7d797a0adba1428ac727e0a0fd45159c35dbd","datavalue":{"value":{"entity-type":"item","numeric-id":1115596,"id":"Q1115596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7149cc2e503e901db7f4bac6abf5ab971cbb6c0f","datavalue":{"value":{"amount":"+0.8412432670593262","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":"Q5940607$E3C9AF51-3BAC-47AF-9121-F5D9B6C97C71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1621523a4e4e20238ba0cfc2786568a40c52813","datavalue":{"value":{"entity-type":"item","numeric-id":2706467,"id":"Q2706467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6ed3bdf609b05c36cf2d4325c703e6379f6a5d83","datavalue":{"value":{"amount":"+0.8178265690803528","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":"Q5940607$8C578FED-FF9A-40E5-AAA5-22FF4B478CF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc86fe0faa0b7293cee7e04851935d08bc440aaf","datavalue":{"value":{"entity-type":"item","numeric-id":1100892,"id":"Q1100892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dcf1fadb4e5e1c8c7eb4d66a1ca08f195953af68","datavalue":{"value":{"amount":"+0.8165937066078186","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":"Q5940607$3271ADAC-F045-4BCA-8361-A515F82FB4D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bfe74125e6438cc6b3410b735794022dec837392","datavalue":{"value":{"entity-type":"item","numeric-id":1825589,"id":"Q1825589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"008ac43e9d4f841c670f5deb682a9c8488087b04","datavalue":{"value":{"amount":"+0.7959610223770142","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":"Q5940607$BD3AE510-ED43-48D3-99BA-E20B47BCE20E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5940607","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5940607"}}}}}