{"entities":{"Q5930160":{"pageid":8106962,"ns":120,"title":"Item:Q5930160","lastrevid":47598346,"modified":"2026-01-02T04:35:09Z","type":"item","id":"Q5930160","labels":{"en":{"language":"en","value":"Efficient parallel computation of the characteristic polynomial of a sparse, separable matrix"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1587484"}},"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":"Q5930160$F908E07E-61F4-4B40-A09F-B6FF9316DCF3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fe805188f0c7e12906ec30af67e829fea2782b88","datavalue":{"value":{"text":"Efficient parallel computation of the characteristic polynomial of a sparse, separable matrix","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5930160$55C7E4F0-304F-4060-A96E-2B6A6AF0A320","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bc6d0062ac12158c86945ce28f060bfcf50b21a7","datavalue":{"value":"0986.65043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5930160$49D52F9D-AFC7-4CE9-B88A-EFBB80AB497D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3cdf21d0e331a47790f86a0203b4b15950c2a72f","datavalue":{"value":{"entity-type":"item","numeric-id":537850,"id":"Q537850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5930160$1B2B0C56-152F-443C-BCF1-69F0D6119BD7","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":"Q5930160$7C6C2847-74DD-494A-B02A-F3E8498EDAFE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a43adefc0e2387468f62816a0a1cfc8a0f64a751","datavalue":{"value":{"time":"+2001-07-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5930160$B8EA9A9D-73C6-42E1-A7D7-C96AF24A49D2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"05f952e310bbf0df8f342ccba3eafd27f9b5a3a1","datavalue":{"value":"This paper is concerned with the problem of computing the characteristic polynomial of a matrix. In a large number of applications, the matrices are symmetric and sparse: with \\(O(n)\\) non-zero entries. The problem has an efficient sequential solution in this case, requiring \\(O(n^2)\\) work by use of the sparse Lanczos method. A major question remaining open is: to find a polylog time parallel algorithm with matching work bounds.    Unfortunately, the sparse Lanczos method cannot be parallelized to faster then time \\((n)\\) using \\(n\\) processors. Let \\(M(n)\\) be the processor bound to multiply two square matrices of order \\(n\\) in \\(O(\\log n)\\) parallel time. This article gives a new algorithm for computing the characteristic polynomial of a sparse symmetric matrix assuming that the sparsity graph is \\(s(n)\\)-separable. The author derives an interesting algebraic version of nested dissection, which constructs a sparse factorization of the matrix \\(A-I\\) where \\(A\\) is the input matrix .","type":"string"},"datatype":"string"},"type":"statement","id":"Q5930160$380E28FD-F213-47D5-AFAD-AD444B9748B4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ec9127734f65ef2ab56e16035c5e0b798e9b9662","datavalue":{"value":{"entity-type":"item","numeric-id":587214,"id":"Q587214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5930160$92B6DF38-623B-4521-9586-B8E7B5A33557","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"72309745094959b676ca20810c7af21a33fe24b5","datavalue":{"value":"65F30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5930160$E029F996-D636-4596-842C-60F0CD105A41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1fd405649af5a3f9a37557a0bd816920cbf1d33b","datavalue":{"value":"65F15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5930160$58F18B59-51CE-45AB-8859-7FA6CB1F4DA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8a7edc01538ef78e7e423d9c49f622de0faa5a14","datavalue":{"value":"65Y05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5930160$D2E49784-CCA2-4493-8D41-7E8E91983977","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8951383960d3cb5c642694541440da7344dcb759","datavalue":{"value":"1587484","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5930160$61591E95-510B-4DD4-A142-90F328EBE42C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"431ad0527b194c43bf7b26fc7f3a3705c49e72a4","datavalue":{"value":"parallel computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q5930160$357C14D7-9CA2-47D5-AA47-E41305AAD265","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be99652003a74838f18fb59443c60e79abec0ac4","datavalue":{"value":"sparse separable matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q5930160$E32AA1E2-776C-4469-9E15-91CBE30BD3C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"64287d55cb2f38dd0f11da246e78f83648de9a8a","datavalue":{"value":"characteristic polynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q5930160$21C2AA63-2DAA-42BC-A784-70812B69718C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dae55860cd44265141761ab31ef20ff31fa935a7","datavalue":{"value":"sparse Lanczos method","type":"string"},"datatype":"string"},"type":"statement","id":"Q5930160$9F4AF217-5D64-4942-83D6-791C31A1A0D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6865228c9c1c4e6af02a79d4cda2a5c0636390af","datavalue":{"value":"sparse factorization","type":"string"},"datatype":"string"},"type":"statement","id":"Q5930160$21C5C5AC-9700-4D48-A403-27FD09914A0A","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":"Q5930160$93FF0747-9BCD-4588-A1A7-6232B0C58459","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"01483c4a6f5851abd0399deecf91bfaff199208c","datavalue":{"value":"https://doi.org/10.1007/s004530010068","type":"string"},"datatype":"url"},"type":"statement","id":"Q5930160$B26571F4-F7C3-42EB-8494-71BFB6FB297E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7ffd299d0d3fb5460421116bdf6631cff556a0a7","datavalue":{"value":"W2025745732","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5930160$A8C850F7-5138-48F2-99B8-7E53C1CA56CB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8537ea8225e4fe181f8900803f2fdbb9ad804f1d","datavalue":{"value":"10.1007/S004530010068","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5930160$B2F86368-0E69-4F3B-B099-0BD808EAFFAB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1162062a5045e254dda8f3d905edcdc97b703b62","datavalue":{"value":{"entity-type":"item","numeric-id":2830011,"id":"Q2830011"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf2c5f1b88a378c07dadbd84bf148dbb5cbe7384","datavalue":{"value":{"amount":"+0.7894771695137024","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":"Q5930160$50AD3DF5-EE87-49BE-8502-5BBDAE45338D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c6b8e516e20d1017df1633d7968f767e19693f1","datavalue":{"value":{"entity-type":"item","numeric-id":4277539,"id":"Q4277539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f866a2c22328b0cf345caa58af32808f157355d8","datavalue":{"value":{"amount":"+0.7878158092498779","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":"Q5930160$817992DC-9C98-4B4B-9504-6867247C0910","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a8b8102f3ad567d6c5d54c2edb25a6fbc41513dc","datavalue":{"value":{"entity-type":"item","numeric-id":5301686,"id":"Q5301686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82ab797cdf176019c238468cea71fa4d029eda70","datavalue":{"value":{"amount":"+0.7857003808021545","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":"Q5930160$C64B1D82-F08A-4DB6-AF9B-BF98F1B659DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"57f4f98a31a40137ef2e80a8a1ddb1b013e2e88a","datavalue":{"value":{"entity-type":"item","numeric-id":5262755,"id":"Q5262755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41d5bb14420cc0dcae70c4cce46879d7836d594e","datavalue":{"value":{"amount":"+0.7844024896621704","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":"Q5930160$8EE9C8D3-2AD9-470C-9588-8DCF4727693C","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":"83c294e51465c6649acc0bc2b86e282ec498453f","datavalue":{"value":{"amount":"+0.7726729512214661","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":"Q5930160$784D5509-7C71-4BF1-BCC8-10523D72D05E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5930160","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5930160"}}}}}