{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:20:54Z","timestamp":1750306854900,"version":"3.41.0"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2014,2,1]],"date-time":"2014-02-01T00:00:00Z","timestamp":1391212800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"eSSENCE"},{"name":"UMIT Research Lab via Balticgruppen"},{"DOI":"10.13039\/501100004359","name":"Vetenskapsr\u00e4det","doi-asserted-by":"publisher","award":["VR 7062571"],"award-info":[{"award-number":["VR 7062571"]}],"id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"publisher"}]},{"name":"strategic collaborative eScience programme"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2014,2]]},"abstract":"<jats:p>\n            The QR algorithm is the method of choice for computing all eigenvalues of a dense nonsymmetric matrix\n            <jats:italic>A<\/jats:italic>\n            . After an initial reduction to Hessenberg form, a QR iteration can be viewed as chasing a small bulge from the top left to the bottom right corner along the subdiagonal of\n            <jats:italic>A<\/jats:italic>\n            . To increase data locality and create potential for parallelism, modern variants of the QR algorithm perform several iterations simultaneously, which amounts to chasing a chain of several bulges instead of a single bulge. To make effective use of level 3 BLAS, it is important to pack these bulges as tightly as possible within the chain. In this work, we show that the tightness of the packing in existing approaches is not optimal and can be increased. This directly translates into a reduced chain length by 33% compared to the state-of-the-art LAPACK implementation of the QR algorithm. To demonstrate the impact of our idea, we have modified the LAPACK implementation to make use of the optimal packing. Numerical experiments reveal a uniform reduction of the execution time, without affecting stability or robustness.\n          <\/jats:p>","DOI":"10.1145\/2559986","type":"journal-article","created":{"date-parts":[[2014,3,18]],"date-time":"2014-03-18T12:09:07Z","timestamp":1395144547000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Optimally packed chains of bulges in multishift QR algorithms"],"prefix":"10.1145","volume":"40","author":[{"given":"Lars","family":"Karlsson","sequence":"first","affiliation":[{"name":"Ume\u00e5 University, Sweden"}]},{"given":"Daniel","family":"Kressner","sequence":"additional","affiliation":[{"name":"EPF Lausanne, Switzerland"}]},{"given":"Bruno","family":"Lang","sequence":"additional","affiliation":[{"name":"University of Wuppertal, Germany"}]}],"member":"320","published-online":{"date-parts":[[2014,3,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"E. Anderson Z. Bai etal 1999. LAPACK Users' Guide. 3rd Ed. SIAM Philadelphia PA.   E. Anderson Z. Bai et al. 1999. LAPACK Users' Guide. 3rd Ed. SIAM Philadelphia PA.","DOI":"10.1137\/1.9780898719604"},{"key":"e_1_2_1_2_1","unstructured":"Z. Bai D. Day J. W. Demmel and J. J. Dongarra. 1997. A test matrix collection for non-Hermitian eigenvalue problems (release 1.0). Tech.l Rep. CS-97-355 Department of Computer Science University of Tennessee Knoxville TN http:\/\/math.nist.gov\/MatrixMarket.   Z. Bai D. Day J. W. Demmel and J. J. Dongarra. 1997. A test matrix collection for non-Hermitian eigenvalue problems (release 1.0). Tech.l Rep. CS-97-355 Department of Computer Science University of Tennessee Knoxville TN http:\/\/math.nist.gov\/MatrixMarket."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129053389000068"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479801384573"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479801384585"},{"key":"e_1_2_1_6_1","unstructured":"R. Byers. 2007. LAPACK 3.1 xHSEQR: Tuning and implementation notes on the small bulge multi-shift QR algorithm with aggressive early deflation. LAPACK Working Note 187.  R. Byers. 2007. LAPACK 3.1 xHSEQR: Tuning and implementation notes on the small bulge multi-shift QR algorithm with aggressive early deflation. LAPACK Working Note 187."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/4.3.265"},{"edition":"3","volume-title":"Matrix Computations","author":"Golub G. H.","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/090756934"},{"volume-title":"Tech. Rep. UMINF-12.06, Department of Computing Science","year":"2012","author":"Granat R.","key":"e_1_2_1_10_1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827597325165"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/05064521X"},{"volume-title":"Numerical Methods for General and Structured Eigenvalue Problems","series-title":"Lecture Notes in Computational Science and Engineering","author":"Kressner D.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","first-page":"50","article-title":"On the use of larger bulges in the QR algorithm","volume":"20","author":"Kressner D.","year":"2005","journal-title":"Electron. Trans. Numer. Anal."},{"key":"e_1_2_1_15_1","unstructured":"B. Lang. 1997. Effiziente Orthogonaltransformationen bei der Eigen- und Singul\u00e4rwertzerlegung. Habilitationsschrift Bergische Universit\u00e4t Gesamthochschule Wuppertal.  B. Lang. 1997. Effiziente Orthogonaltransformationen bei der Eigen- und Singul\u00e4rwertzerlegung. Habilitationsschrift Bergische Universit\u00e4t Gesamthochschule Wuppertal."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0915057"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479893245991"},{"volume-title":"The Matrix Eigenvalue Problem. GR and Krylov Subspace Methods","author":"Watkins D. S.","key":"e_1_2_1_18_1"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2559986","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2559986","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:10:25Z","timestamp":1750234225000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2559986"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,2]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,2]]}},"alternative-id":["10.1145\/2559986"],"URL":"https:\/\/doi.org\/10.1145\/2559986","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"type":"print","value":"0098-3500"},{"type":"electronic","value":"1557-7295"}],"subject":[],"published":{"date-parts":[[2014,2]]},"assertion":[{"value":"2012-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-03-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}