{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:10:25Z","timestamp":1750219825845,"version":"3.41.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,9,10]],"date-time":"2022-09-10T00:00:00Z","timestamp":1662768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Swedish National Infrastructure for Computing (SNIC) at High-Performance Computing Center North","award":["SNIC 2019\/3-311 and SNIC 2020\/5-286"],"award-info":[{"award-number":["SNIC 2019\/3-311 and SNIC 2020\/5-286"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2022,9,30]]},"abstract":"<jats:p>Inverse iteration is known to be an effective method for computing eigenvectors corresponding to simple and well-separated eigenvalues. In the non-symmetric case, the solution of shifted Hessenberg systems is a central step. Existing inverse iteration solvers approach the solution of the shifted Hessenberg systems with either RQ or LU factorizations and, once factored, solve the corresponding systems. This approach has limited level-3 BLAS potential since distinct shifts have distinct factorizations. This paper rearranges the RQ approach such that data shared between distinct shifts can be exploited. Thereby the backward substitution with the triangular R factor can be expressed mostly with matrix\u2013matrix multiplications (level-3 BLAS). The resulting algorithm computes eigenvectors in a tiled, overflow-free, and task-parallel fashion. The numerical experiments show that the new algorithm outperforms existing inverse iteration solvers for the computation of both real and complex eigenvectors.<\/jats:p>","DOI":"10.1145\/3544789","type":"journal-article","created":{"date-parts":[[2022,7,15]],"date-time":"2022-07-15T11:33:23Z","timestamp":1657884803000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Robust level-3 BLAS Inverse Iteration from the Hessenberg Matrix"],"prefix":"10.1145","volume":"48","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8444-6303","authenticated-orcid":false,"given":"Angelika","family":"Schwarz","sequence":"first","affiliation":[{"name":"Ume\u00e5 University SwedenUme\u00e5, Sweden"}]}],"member":"320","published-online":{"date-parts":[[2022,9,10]]},"reference":[{"key":"e_1_3_2_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/898921"},{"key":"e_1_3_2_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/323215"},{"issue":"2","key":"e_1_3_2_4_1","first-page":"12","article-title":"A note on shifted Hessenberg systems and frequency response computation","volume":"38","author":"Beattie Christopher","year":"2012","unstructured":"Christopher Beattie, Zlatko Drma\u010d, and Serkan Gugercin. 2012. A note on shifted Hessenberg systems and frequency response computation. ACM Trans. Math. Softw. 38, 2, Article 12 (Jan. 2012), 16 pages.","journal-title":"ACM Trans. Math. Softw."},{"key":"e_1_3_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/567806.567809"},{"key":"e_1_3_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/567806.567807"},{"key":"e_1_3_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2450153.2450157"},{"key":"e_1_3_2_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1144465"},{"key":"e_1_3_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3264491"},{"key":"e_1_3_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/77626.79170"},{"key":"e_1_3_2_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/248979"},{"key":"e_1_3_2_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/866641"},{"key":"e_1_3_2_13_1","first-page":"546","volume-title":"Proceedings of the Seventh SIAM Conference on Parallel Processing for Scientific Computing","author":"Henry Greg","year":"1995","unstructured":"Greg Henry. 1995. A parallel unsymmetric inverse iteration solver. In Proceedings of the Seventh SIAM Conference on Parallel Processing for Scientific Computing. 546\u2013551."},{"key":"e_1_3_2_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144596300773"},{"key":"e_1_3_2_15_1","unstructured":"Carl Christian Kjelgaard Mikkelsen. 2020. Well-conditioned eigenvalue problems that overflow. (2020). arxiv:2005.05356"},{"key":"e_1_3_2_16_1","first-page":"68","volume-title":"International Conference on Parallel Processing and Applied Mathematics","author":"Mikkelsen Carl Christian Kjelgaard","year":"2017","unstructured":"Carl Christian Kjelgaard Mikkelsen and Lars Karlsson. 2017a. Blocked algorithms for robust solution of triangular linear systems. In International Conference on Parallel Processing and Applied Mathematics. Springer, 68\u201378."},{"key":"e_1_3_2_17_1","unstructured":"Carl Christian Kjelgaard Mikkelsen and Lars Karlsson. 2017b. Robust Solution of Triangular Linear Systems NLAFET Working Note 9. (May 2017)."},{"issue":"19","key":"e_1_3_2_18_1","doi-asserted-by":"crossref","first-page":"e5064","DOI":"10.1002\/cpe.5064","article-title":"Parallel robust solution of triangular linear systems","volume":"31","author":"Mikkelsen Carl Christian Kjelgaard","year":"2019","unstructured":"Carl Christian Kjelgaard Mikkelsen, Angelika B. Schwarz, and Lars Karlsson. 2019. Parallel robust solution of triangular linear systems. Concurrency and Computation: Practice and Experience 31, 19 (2019), e5064.","journal-title":"Concurrency and Computation: Practice and Experience"},{"key":"e_1_3_2_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/280490"},{"key":"e_1_3_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-86940-2_29"},{"key":"e_1_3_2_21_1","volume-title":"Comparing the Performance of Computing Eigenvectors from the Schur Matrix and by Inverse Iteration from the Hessenberg Matrix","author":"Schwarz Angelika","year":"2020","unstructured":"Angelika Schwarz. 2020. Comparing the Performance of Computing Eigenvectors from the Schur Matrix and by Inverse Iteration from the Hessenberg Matrix. UMINF 21.08. https:\/\/webapps.cs.umu.se\/uminf\/reports\/2021\/008\/part1.pdf."},{"key":"e_1_3_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2009.207"},{"key":"e_1_3_2_23_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-68-99868-2"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3544789","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3544789","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:25Z","timestamp":1750178785000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3544789"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,10]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,9,30]]}},"alternative-id":["10.1145\/3544789"],"URL":"https:\/\/doi.org\/10.1145\/3544789","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"type":"print","value":"0098-3500"},{"type":"electronic","value":"1557-7295"}],"subject":[],"published":{"date-parts":[[2022,9,10]]},"assertion":[{"value":"2020-09-19","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-05-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-09-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}