{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T07:09:39Z","timestamp":1787382579542,"version":"build-2736575974"},"reference-count":72,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>A novel variant of the parallel QR algorithm for solving dense nonsymmetric eigenvalue problems on hybrid distributed high performance computing systems is presented. For this purpose, we introduce the concept of multiwindow bulge chain chasing and parallelize aggressive early deflation. The multiwindow approach ensures that most computations when chasing chains of bulges are performed in level 3 BLAS operations, while the aim of aggressive early deflation is to speed up the convergence of the QR algorithm. Mixed MPI-OpenMP coding techniques are utilized for porting the codes to distributed memory platforms with multithreaded nodes, such as multicore processors. Numerous numerical experiments confirm the superior performance of our parallel QR algorithm in comparison with the existing ScaLAPACK code, leading to an implementation that is one to two orders of magnitude faster for sufficiently large problems, including a number of examples from applications.<\/jats:p>","DOI":"10.1137\/090756934","type":"journal-article","created":{"date-parts":[[2010,8,4]],"date-time":"2010-08-04T21:27:49Z","timestamp":1280957269000},"page":"2345-2378","source":"Crossref","is-referenced-by-count":20,"title":["A Novel Parallel QR Algorithm for Hybrid Distributed Memory HPC Systems"],"prefix":"10.1137","volume":"32","author":[{"given":"Robert","family":"Granat","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bo","family":"K\u00e5gstr\u00f6m","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Kressner","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,8,4]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"B. Adlerborn, K. Dackland, and B. K\u00e5gstr\u00f6m,\n                      Parallel and blocked algorithms for reduction of a regular matrix pair to Hessenberg-triangular and generalized Schur forms\n                      , in Applied Parallel Computing (PARA 2002), J. Fagerholm, J. Haataja, J. J\u00e4rvenen, M. Lyly, P. R\u00e5back, and V. Savolainen, eds., Lecture Notes in Comput. Sci. 2367, Springer-Verlag, Berlin, 2002, pp. 319\u2013328.","DOI":"10.1007\/3-540-48051-X_32"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"B. Adlerborn, D. Kressner, and B. K\u00e5gstr\u00f6m,\n                      Parallel variants of the multishift QZ algorithm with advanced deflation techniques\n                      , in Applied Parallel Computing\u2014State of the Art in Scientific Computing (PARA 2006), B. K\u00e5gstr\u00f6m, E. Elmroth, J. Dongarra, and J. Wa\u015bniewski, eds., Lecture Notes in Comput. Sci. 4699, Springer-Verlag, Berlin, 2007, pp. 117\u2013126.","DOI":"10.1007\/978-3-540-75755-9_15"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"E. Anderson, Z. Bai, C. Bischof, S. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, and D. Sorensen,\n                      LAPACK Users' Guide\n                      , 3rd ed., SIAM, Philadelphia, 1999.","DOI":"10.1137\/1.9780898719604"},{"key":"R4","unstructured":"D. Antonelli and C. Voemel,\n                      LAPACK Working Note\n                      168:\n                      PDSYEVR. ScaLAPACK's Parallel MRRR Algorithm for the Symmetric Eigenvalue Problem\n                      , Technical report UCB\/CSD-05-1399, EECS Department, University of California, Berkeley, CA, 2005."},{"key":"R5","unstructured":"Z. Bai, D. Day, J. W. Demmel, and J. J. Dongarra,\n                      A Test Matrix Collection for Non-Hermitian Eigenvalue Problems (Release $1.0$)\n                      , Technical report CS-97-355, Department of Computer Science, University of Tennessee, Knoxville, TN, 1997; also available online from http:\/\/math.nist.gov\/MatrixMarket."},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1142\/S0129053389000068"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(93)90286-W"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. van der Vorst, eds.\n                      Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide\n                      , Software Environ. Tools 11, SIAM, Philadelphia, 2000.","DOI":"10.1137\/1.9780898719581"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(00)00012-0"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1023\/A:1019191431273"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"P. Benner, E. S. Quintana-Ort\u00ed, and G. Quintana-Ort\u00ed,\n                      Solving linear and quadratic matrix equations on distributed memory parallel computers\n                      , in Proceedings of the IEEE International Symposium on Computer Aided Control System Design, 1999, pp. 64\u201369.","DOI":"10.1109\/CACSD.1999.808625"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(95)00015-G"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/030601107"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"L. S. Blackford, J. Choi, A. Cleary, E. D'Azevedo, J. Demmel, I. Dhillon, J. Dongarra, S. Hammarling, G. Henry, A. Petitet, K. Stanley, D. Walker, and R. C. Whaley,\n                      ScaLAPACK Users' Guide\n                      , SIAM, Philadelphia, 1997.","DOI":"10.1137\/1.9780898719642"},{"key":"R15","unstructured":"D. Boley and R. Maier,\n                      A Parallel QR Algorithm for the Nonsymmetric Eigenvalue Problem\n                      , Technical report TR-88-12, Department of Computer Science, University of Minnesota, Minneapolis, MN, 1988."},{"key":"R16","unstructured":"K. Braman,\n                      Middle deflations in the QR algorithm\n                      , talk at Householder Symposium XVII, Zeuthen, Germany, 2008."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479801384573"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479801384585"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(87)90222-9"},{"key":"R20","unstructured":"R. Byers,\n                      LAPACK $3.1$ xHSEQR: Tuning and Implementation Notes on the Small Bulge Multi-shift QR Algorithm with Aggressive Early Deflation\n                      , LAPACK Working Note 187, 2007."},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1007\/BF02140776"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"K. Dackland,\n                      Parallel Reduction of a Regular Matrix Pair to Block-Hessenberg-Triangular Form\u2014Algorithm Design and Performance Modelling\n                      , Report UMINF-98.09, Department of Computing Science, Ume\u00e5 University, Ume\u00e5, Sweden, 1998.","DOI":"10.1007\/BFb0095325"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1145\/332242.332244"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1145\/77626.79170"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1987.1676879"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"J. G. F. Francis,\n                      The QR transformation, part\n                      I, Comput. J., 4 (1961\/1962), pp. 265\u2013271.","DOI":"10.1093\/comjnl\/4.3.265"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"J. G. F. Francis,\n                      The QR transformation, part\n                      II, Comput. J., 4 (1961\/1962), pp. 332\u2013345.","DOI":"10.1093\/comjnl\/4.4.332"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(90)90147-2"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"G. A. Geist, R. C. Ward, G. J. Davis, and R. E. Funderlic,\n                      Finding eigenvalues and eigenvectors of unsymmetric matrices using a hypercube multiprocessor\n                      , in Proceedings of the Third Conference on Hypercube Concurrent Computers and Applications, G. Fox, ed., ACM, New York, 1988, pp. 1577\u20131582.","DOI":"10.1145\/63047.63118"},{"key":"R30","unstructured":"G. H. Golub and C. F. Van Loan,\n                      Matrix Computations\n                      , 3rd ed., The Johns Hopkins University Press, Baltimore, MD, 1996."},{"key":"R31","unstructured":"GOTO-BLAS,\n                      High-Performance BLAS by Kazushige Goto\n                      , http:\/\/www.cs.utexas.edu\/users\/ flame\/goto\/."},{"key":"R32","unstructured":"R. Granat and B. K\u00e5gstr\u00f6m,\n                      Algorithm\n                      XXX:\n                      The SCASY software library\u2014parallel solvers for Sylvester-type matrix equations with applications in condition estimation, part\n                      II, ACM Trans. Math. Software, to appear."},{"key":"R33","unstructured":"R. Granat and B. K\u00e5gstr\u00f6m,\n                      Parallel solvers for Sylvester-type matrix equations with applications in condition estimation, part\n                      I:\n                      Theory and algorithms\n                      , ACM Trans. Math. Software, to appear."},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.1386"},{"key":"R35","doi-asserted-by":"crossref","unstructured":"R. Granat, B. B. K\u00e5gstr\u00f6m, and D. Kressner,\n                      A parallel Schur method for solving continuous-time algebraic Riccati equations\n                      , in Proceedings of the IEEE International Symposium on Computer-Aided Control Systems Design, San Antonio, TX, 2008, pp. 583\u2013588.","DOI":"10.1109\/CACSD.2008.4627344"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1137\/0917056"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827597325165"},{"key":"R38","doi-asserted-by":"crossref","unstructured":"N. J. Higham,\n                      Accuracy and Stability of Numerical Algorithms\n                      , 2nd ed., SIAM, Philadelphia, 2002.","DOI":"10.1137\/1.9780898718027"},{"key":"R39","unstructured":"HPC2N,\n                      High Performance Computing Center North\n                      , http:\/\/www.hpc2n.umu.se."},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1137\/05064521X"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1145\/292395.292412"},{"key":"R42","unstructured":"L. Karlsson and B. K\u00e5gstr\u00f6m,\n                      A framework for dynamic node scheduling of two-sided blocked matrix computations\n                      , in State of the Art in Scientific and Parallel Computing (PARA 2008), Lecture Notes in Comput. Sci., Springer-Verlag, Berlin, to appear."},{"key":"R43","unstructured":"D. Kressner,\n                      Numerical Methods for General and Structured Eigenvalue Problems\n                      , Lect. Notes Comput. Sci. Eng. 46, Springer-Verlag, Heidelberg, 2005."},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1145\/1186785.1186787"},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1137\/06067609X"},{"key":"R46","first-page":"637","volume":"3","author":"Kublanovskaya V. N.","year":"1961","journal-title":"USSR Comp. Math Phys."},{"key":"R47","unstructured":"B. Lang,\n                      Effiziente Orthogonaltransformationen bei der Eigen- und Singul\u00e4rwertzerlegung\n                      , Habilitationsschrift, Fachbereich Mathematik, Bergische Universit\u00e4t GH Wuppertal, Germany, 1997."},{"key":"R48","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595280211"},{"key":"R49","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1979.1102178"},{"key":"R50","doi-asserted-by":"publisher","DOI":"10.1155\/2010\/574728"},{"key":"R51","doi-asserted-by":"crossref","unstructured":"R. M. Martin,\n                      Electronic Structure: Basic Theory and Practical Methods\n                      , Cambridge University Press, New York, 2004.","DOI":"10.1017\/CBO9780511805769"},{"key":"R52","unstructured":"Matrix Market,\n                      A Visual Repository of Test Data for Use in Comparative Studies of Algorithms for Numerical Linear Algebra\n                      , http:\/\/math.nist.gov\/MatrixMarket\/."},{"key":"R53","unstructured":"MPI,\n                      Message Passing Interface\n                      , http:\/\/www-unix.mcs.anl.gov\/mpi\/."},{"key":"R54","unstructured":"PBLAS,\n                      Parallel Basic Linear Algebra Subprograms\n                      , http:\/\/www.netlib.org\/scalapack\/."},{"key":"R55","doi-asserted-by":"publisher","DOI":"10.1080\/00207178008922881"},{"key":"R56","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(94)90112-0"},{"key":"R57","unstructured":"ScaLAPACK Users' Guide, http:\/\/www.netlib.org\/scalapack\/slug\/."},{"key":"R58","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(87)90017-2"},{"key":"R59","doi-asserted-by":"crossref","unstructured":"R. A. van de Geijn,\n                      Storage schemes for parallel eigenvalue algorithms\n                      , in Numerical Linear Algebra Digital Signal Processing and Parallel Algorithms, G. Golub and P. Van Dooren, eds., Springer-Verlag, Berlin, 1988, pp. 639\u2013648.","DOI":"10.1007\/978-3-642-75536-1_52"},{"key":"R60","doi-asserted-by":"publisher","DOI":"10.1137\/0614016"},{"key":"R61","unstructured":"R. A. van de Geijn and D. G. Hudson,\n                      An efficient parallel implementation of the nonsymmetric QR algorithm\n                      , in Proceedings of the Fourth Conference on Hypercube Concurrent Computers and Applications, Monterey, CA, 1989, pp. 697\u2013700."},{"key":"R62","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479896312869"},{"key":"R63","unstructured":"V. Volkov and J. W. Demmel,\n                      LAPACK Working Note $197$: Using GPUs to Accelerate the Bisection Algorithm for Finding Eigenvalues of Symmetric Tridiagonal Matrices\n                      , Technical report UCB\/EECS-2007-179, EECS Department, University of California, Berkeley, CA, 2007."},{"key":"R64","doi-asserted-by":"publisher","DOI":"10.1137\/0915057"},{"key":"R65","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479893245991"},{"key":"R66","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(95)00545-5"},{"key":"R67","first-page":"1","volume":"23","author":"Watkins D. S.","year":"2006","journal-title":"Electron. Trans. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/1097-4067","issn-type":"print"},{"key":"R68","doi-asserted-by":"crossref","unstructured":"D. S. Watkins,\n                      The Matrix Eigenvalue Problem: $GR$ and Krylov Subspace Methods\n                      , SIAM, Philadelphia, 2007.","DOI":"10.1137\/1.9780898717808"},{"key":"R69","doi-asserted-by":"publisher","DOI":"10.1137\/060659454"},{"key":"R70","doi-asserted-by":"crossref","unstructured":"R. C. Whaley,\n                      Empirically tuning LAPACK's blocking factor for increased performance\n                      , in Proceedings of the International Multiconference on Computer Science and Information Technology (IMCSIT), Vol. 3, Polish Information Processing Society, Warsaw, Poland, 2008, pp. 303\u2013310.","DOI":"10.1109\/IMCSIT.2008.4747256"},{"key":"R71","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(00)00087-9"},{"key":"R72","doi-asserted-by":"crossref","unstructured":"Y. Yamamoto,\n                      Performance modeling and optimal block size selection for the small-bulge multishift QR algorithm\n                      , in Parallel and Distributed Processing and Applications, M. Guo, L. T. Yang, B. Di Martino, H. Zima, J. J. Dongarra, and F. Tang, eds., Lecture Notes in Comput. Sci. 4330, Springer-Verlag, Berlin, 2006, pp. 451\u2013463.","DOI":"10.1007\/11946441_44"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090756934","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:51:01Z","timestamp":1787331061000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090756934"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":72,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/090756934"],"URL":"https:\/\/doi.org\/10.1137\/090756934","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}