{"entities":{"Q753418":{"pageid":755267,"ns":120,"title":"Item:Q753418","lastrevid":64158696,"modified":"2026-04-11T18:01:42Z","type":"item","id":"Q753418","labels":{"en":{"language":"en","value":"Estimating the extremal eigenvalues of a symmetric matrix"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4180660"}},"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":"Q753418$3D64ADFD-DFEB-490A-8E2E-1E2A59D9EE22","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c1da6397138720898b875e6fbcd69c99f8da0510","datavalue":{"value":{"text":"Estimating the extremal eigenvalues of a symmetric matrix","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q753418$E70CA35D-ED06-4CAC-882D-642DE1B6C628","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dfca04fa76b888d1bbc76be47bb48a616422ef2f","datavalue":{"value":"0716.65034","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q753418$213A27AA-FCD4-4DAA-A8CF-5AC1DE34A31A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fd40235f9964634b097192dc82388ef7d2c72c4d","datavalue":{"value":"10.1016/0898-1221(90)90236-D","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q753418$386FE258-A4C1-42B1-9AF2-8A04C50279DA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q753418$02E0EFAB-5E1E-4326-AFEB-4A3DC930F91E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b60bed24d7288cc2b5f738d0048ff3838242cf99","datavalue":{"value":"For an \\(n\\times n\\) real symmetric non-singular matrix A and a natural number m the author proposes an algorithm to approximate the values of trace \\(A^ m\\) and trace \\(A^{-m}\\) (that enables us to estimate the two absolutely extremal eigenvalues \\(\\lambda_ 1\\) and \\(\\lambda_ n\\) of the matrix A; \\(| \\lambda_ 1| =\\max \\{| \\lambda_ i| \\}\\), \\(| \\lambda_ n| =\\min \\{| \\lambda_ i| \\}\\) for \\(i=1,2,...,n)\\). Instead of the powers of A, the algorithm needs to calculate traces of matrices of the form \\((p_ rI-A)^{-1}\\) for \\(r=0,1,...,Q-1\\), where \\(Q>m\\) is an integer, \\(p_ r=H\\omega^ r\\), \\(H<| \\lambda_ 1|\\) being a real number and \\(\\omega\\) being a primitive Q-th root of 1 \\((\\omega^ Q=1\\), \\(\\omega^ r\\neq 1\\) for \\(0<r<Q).\\)    The algorithm is analyzed for some special classes of matrices: if A is a Hermitian or real Toeplitz matrix, its time complexity is of the order of O(mn log\\({}^ 2n)\\); for Toeplitz-like matrices having a small displacement rank d, it is of the order of \\(O(md^ 2n \\log^ 2n)\\). For bounded matrices with lower bandwidth w and upper bandwidth \\(w^*\\) (i.e. \\(a_{ij}=0\\) for \\(i-j>w\\) or \\(j-i>w^*)\\), the cost is of the order of \\(O((w+w^*)^ 2mn)\\), but in the case when A is a strongly diagonally dominant matrix, the algorithm needs some modifications increasing the cost about log n times to guarantee its numerical stability.    Finally, for symmetric positive definite matrix A having O(\\(\\sqrt{n})\\)- separator tree, the algorithm needs \\(O(mn^ 2)\\) arithmetic operations. With about the same cost the method gives approximations of trace \\(A^ s\\) simultaneously for all s between -m and m. Th classical algorithms, calculating powers of A, involve O(log m) matrix multiplications, i.e. \\(O(n^ 3\\log m)\\) arithmetic operations in general case. The space cost of the algorithm is of the same order as input data, i.e. \\(O(n^ 2).\\)    The author analyzes also the numerical stability of the algorithm in dependence of the magnitude of the parameter H.","type":"string"},"datatype":"string"},"type":"statement","id":"Q753418$CAAC6524-F11B-4028-9A54-B4C6685D9868","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d5fd5ff183c0604d4604d01e4d7272b9df444640","datavalue":{"value":{"entity-type":"item","numeric-id":593684,"id":"Q593684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753418$937782DE-DB5F-45CC-BF5C-DAFE064E6B91","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1fd405649af5a3f9a37557a0bd816920cbf1d33b","datavalue":{"value":"65F15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q753418$958E11C3-ACEF-4864-A167-4C96007396B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"01c01fe808ed718e2875de738d94f61942d3944d","datavalue":{"value":"65F35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q753418$27C26657-37BE-44B4-B104-4CE04974B34A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1052971e64d8bbbcec770ab511479888ca947f1f","datavalue":{"value":"4180660","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q753418$6B6AE888-B0AC-4066-B85E-317238016278","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"325812d2169d2788f5bfbaad00bba2cd32fd0e20","datavalue":{"value":"Hermitian matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q753418$EFD57834-7CD3-4BD7-9FFA-011928CE6EAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a6c9742b2b3d7ac516e02efc35a191f4272f5860","datavalue":{"value":"computational cost","type":"string"},"datatype":"string"},"type":"statement","id":"Q753418$8048B90F-F720-4E26-A8D7-044F37C6317D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q753418$305A643B-8AA2-43F6-8C30-AC4F1D57E516","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c49916021edccb418deb9b5c9398917147892e7c","datavalue":{"value":"trace","type":"string"},"datatype":"string"},"type":"statement","id":"Q753418$85C93086-BD87-4E67-919C-744BE787472A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"043c779f82456b9d153f53d2a84c35850fc86b2e","datavalue":{"value":"absolutely extremal eigenvalues","type":"string"},"datatype":"string"},"type":"statement","id":"Q753418$2791362F-FCAF-4C3E-80C4-58C8BB85B19E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2927cc86648e30b9fcc703c74bc75d478fbf6fd0","datavalue":{"value":"Toeplitz matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q753418$FB22A66C-D5FC-427C-9F56-6C06A28A0729","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2e9c6ddbd3ee2e6c0c4bc7ccc631220ae7833471","datavalue":{"value":"diagonally dominant matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q753418$FEC1A8BF-3735-4121-82A9-2B6B6F3F2DA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d6fdada31bc04ff0cf7f429946e4bda038f72fbc","datavalue":{"value":"numerical stability","type":"string"},"datatype":"string"},"type":"statement","id":"Q753418$63AA8949-266B-49FF-BF75-DC2B0658B1E7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"748dce42a571924bd5dc5be9f8a70b8adc09d292","datavalue":{"value":{"entity-type":"item","numeric-id":163211,"id":"Q163211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753418$B273C2C2-3AD3-4F5C-AF21-D14435295C18","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":"Q753418$86DB0A6D-3159-42A0-AF8B-F0AC81C613CB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d265fbff8b64abcf0b5d33afc6285bbd82d8752","datavalue":{"value":{"entity-type":"item","numeric-id":3321334,"id":"Q3321334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753418$22AE6490-E706-4C5B-82E0-348A81470C8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9018f87737e241c9efb83879b029bb382b55d8d","datavalue":{"value":{"entity-type":"item","numeric-id":1812812,"id":"Q1812812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753418$90788948-0A50-4911-BB8E-DF443F2C7A52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8b0c96b6e1df635a7afe206ef8a1d8f9ae1c297","datavalue":{"value":{"entity-type":"item","numeric-id":3333131,"id":"Q3333131"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753418$56646E95-E81C-4646-BBC3-D3BFFAAFD84B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"330dd283475f3bbcdd859c49881f99fc779feb8d","datavalue":{"value":{"entity-type":"item","numeric-id":3806667,"id":"Q3806667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753418$DF32EA21-74EB-4521-8D6F-F89A13E8B409","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"412caca700699e97c6cc67456c515935ba50151a","datavalue":{"value":{"entity-type":"item","numeric-id":1139102,"id":"Q1139102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753418$6DA839CB-CB11-484E-BC6B-73C695B4816F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b0c5f3793820cee27a15fd71af98d448c688a99","datavalue":{"value":{"entity-type":"item","numeric-id":3769848,"id":"Q3769848"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753418$84F04D5C-614E-4241-90C2-B69235A80D20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e5b6059657d3cca0322bc1c6fdface9fb02ccb8","datavalue":{"value":{"entity-type":"item","numeric-id":1151720,"id":"Q1151720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753418$F134DE39-DDAA-4AB9-8AAA-FAF669223433","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a33725447015b364cc1b3d3f360910a33951f755","datavalue":{"value":{"entity-type":"item","numeric-id":1253692,"id":"Q1253692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753418$BF42548C-4362-4F67-9FC0-DAE957B979C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"345185326fcea964d9ec1c9fc4c0010b480b5b25","datavalue":{"value":{"entity-type":"item","numeric-id":3734977,"id":"Q3734977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753418$CFF1B7DF-4A87-40DC-978F-BD21A5712492","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27d7e3ea5e32569f562d397c63044c70766a5448","datavalue":{"value":{"entity-type":"item","numeric-id":5185900,"id":"Q5185900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753418$305CA01F-B1FC-4722-ACEC-70A1D922BCFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c09a17a3a3fddac49f04bf0248b9d9ae8f25fb9c","datavalue":{"value":{"entity-type":"item","numeric-id":4117303,"id":"Q4117303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753418$610CF97A-1045-4B85-9B92-52CD6B861CCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6141476b65d14923fb002fbcd5da8a63dbb0016","datavalue":{"value":{"entity-type":"item","numeric-id":3875202,"id":"Q3875202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753418$B7C9EBC3-13FE-4E3D-99A0-F460F1E66FB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b316d9d40fb12243e75ebbe441ad8374a5ed27b6","datavalue":{"value":{"entity-type":"item","numeric-id":1825589,"id":"Q1825589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753418$D0354474-A9D3-4F99-BA44-FE6CC3163972","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"52fbeed5c2ddd3ebf53e76e80dd689cf06f451b8","datavalue":{"value":"https://doi.org/10.1016/0898-1221(90)90236-d","type":"string"},"datatype":"url"},"type":"statement","id":"Q753418$4A7F962C-D60D-4660-A38D-1A01571C688B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"de2541564f3fb801c11d73afe38ecb390792b781","datavalue":{"value":"W2047126140","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q753418$6E04F41D-08C7-43C2-A6E3-B0AF8D043DEF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"293935db3834ff8b5d542ae1771b7c6cb66baa38","datavalue":{"value":{"entity-type":"item","numeric-id":85551,"id":"Q85551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q753418$80F11876-1C75-4231-9D67-13076744795D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab715612cab9a247a4a566cb2969ba2ef588557c","datavalue":{"value":{"entity-type":"item","numeric-id":3321334,"id":"Q3321334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f2e52d0bd18fc3295ab69d3cadac1513c3250aa","datavalue":{"value":{"amount":"+0.8039612174034119","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":"Q753418$5E675CA5-8330-4702-A7E3-4C1195055972","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a8bb80d887d81eb269248350b15ad318397074c","datavalue":{"value":{"entity-type":"item","numeric-id":1311389,"id":"Q1311389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c26729e7b6bce271ed3945d50d67610c1a40bf29","datavalue":{"value":{"amount":"+0.7967758178710938","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":"Q753418$45AE1053-CAC4-4DCF-9AFB-E226009A700E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53b89f2ddc54cce531cdbdecac55cdc8302581c3","datavalue":{"value":{"entity-type":"item","numeric-id":4210086,"id":"Q4210086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1eb2434b95aee8919520f59db656b22bc2558dd0","datavalue":{"value":{"amount":"+0.7934461832046509","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":"Q753418$64B69884-A918-44FC-94DA-4C89EB61F20C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"68e9d2adde164028e8fb7d67f684fb897ddd49cd","datavalue":{"value":{"entity-type":"item","numeric-id":3349863,"id":"Q3349863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e29d54aa4fae1faa2d101243b4cba6cb23c2c6e","datavalue":{"value":{"amount":"+0.7899172306060791","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":"Q753418$0DF80515-5F53-48A3-80FA-2140F84A4D53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"073330ae709b7683ded44531370920cc192a672c","datavalue":{"value":{"entity-type":"item","numeric-id":2819583,"id":"Q2819583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd33de92c378483152f9733ce674ff53b7c0228e","datavalue":{"value":{"amount":"+0.7839975953102112","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":"Q753418$B09D1628-CE18-457C-88A5-31F12F57B57F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Estimating the extremal eigenvalues of a symmetric matrix","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Estimating_the_extremal_eigenvalues_of_a_symmetric_matrix"}}}}}