{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:54:15Z","timestamp":1750308855095,"version":"3.41.0"},"reference-count":14,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2011,2,1]],"date-time":"2011-02-01T00:00:00Z","timestamp":1296518400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["848\/04"],"award-info":[{"award-number":["848\/04"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Grant Agency of the Czech Academy of Sciences","award":["IAA100300802"],"award-info":[{"award-number":["IAA100300802"]}]},{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2002261"],"award-info":[{"award-number":["2002261"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2011,2]]},"abstract":"<jats:p>\n            We present a partitioned algorithm for reducing a symmetric matrix to a tridiagonal form, with partial pivoting. That is, the algorithm computes a factorization\n            <jats:italic>PAPT<\/jats:italic>\n            =\n            <jats:italic>LTLT<\/jats:italic>\n            , where,\n            <jats:italic>P<\/jats:italic>\n            is a permutation matrix,\n            <jats:italic>L<\/jats:italic>\n            is lower triangular with a unit diagonal and entries\u2019 magnitudes bounded by 1, and\n            <jats:italic>T<\/jats:italic>\n            is symmetric and tridiagonal. The algorithm is based on the basic (nonpartitioned) methods of Parlett and Reid and of Aasen. We show that our factorization algorithm is componentwise backward stable (provided that the growth factor is not too large), with a similar behavior to that of Aasen\u2019s basic algorithm. Our implementation also computes the\n            <jats:italic>QR<\/jats:italic>\n            factorization of\n            <jats:italic>T<\/jats:italic>\n            and solves linear systems of equations using the computed factorization. The partitioning allows our algorithm to exploit modern computer architectures (in particular, cache memories and high-performance\n            <jats:sc>blas<\/jats:sc>\n            libraries). Experimental results demonstrate that our algorithms achieve approximately the same level of performance as the partitioned Bunch-Kaufman factor and solve routines in\n            <jats:sc>lapack<\/jats:sc>\n            .\n          <\/jats:p>","DOI":"10.1145\/1916461.1916462","type":"journal-article","created":{"date-parts":[[2011,3,3]],"date-time":"2011-03-03T08:44:26Z","timestamp":1299141866000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Partitioned Triangular Tridiagonalization"],"prefix":"10.1145","volume":"37","author":[{"given":"Miroslav","family":"Rozlo\u017en\u00edk","sequence":"first","affiliation":[{"name":"Academy of Sciences of the Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gil","family":"Shklarski","sequence":"additional","affiliation":[{"name":"Microsoft"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sivan","family":"Toledo","sequence":"additional","affiliation":[{"name":"Tel-Aviv University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01931804"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Anderson E. Bai Z. Bischof C. Blackford S. Demmel J. Dongarra J. Du Croz J. Greenbaum A. Hammarling S. McKenney A. and Sorensen D. 1999. LAPACK Users\u2019 Guide 3rd ed. SIAM Philadelphia PA. Anderson E. Bai Z. Bischof C. Blackford S. Demmel J. Dongarra J. Du Croz J. Greenbaum A. Hammarling S. McKenney A. and Sorensen D. 1999. LAPACK Users\u2019 Guide 3rd ed. SIAM Philadelphia PA.","DOI":"10.1137\/1.9780898719604"},{"volume-title":"Proceedings of the 4th Conference on Parallel Processing for Scientific Computing. J. Dongarra, P. Messina, D. C. Sorensen, and R. G. Voigt, Eds. SIAM","author":"Anderson E.","key":"e_1_2_1_3_1","unstructured":"Anderson , E. and Dongarra , J . 1989. Evaluating block algorithm variants in LAPACK . In Proceedings of the 4th Conference on Parallel Processing for Scientific Computing. J. Dongarra, P. Messina, D. C. Sorensen, and R. G. Voigt, Eds. SIAM , Philadelphia, PA, 3--8. Anderson, E. and Dongarra, J. 1989. Evaluating block algorithm variants in LAPACK. In Proceedings of the 4th Conference on Parallel Processing for Scientific Computing. J. Dongarra, P. Messina, D. C. Sorensen, and R. G. Voigt, Eds. SIAM, Philadelphia, PA, 3--8."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479896296921"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/355694.355697"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055531.1055532"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Bunch J. and Kaufman L. 1977. Some stable methods for calculating inertia and solving symmetric linear systems. Math. Comp. 31 137 163--179. Bunch J. and Kaufman L. 1977. Some stable methods for calculating inertia and solving symmetric linear systems. Math. Comp. 31 137 163--179.","DOI":"10.1090\/S0025-5718-1977-0428694-0"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/77626.79170"},{"volume-title":"Numerical Linear Algebra for High-Performance Computers","author":"Dongarra J. J.","key":"e_1_2_1_9_1","unstructured":"Dongarra , J. J. , Duff , I. S. , Sorensen , D. C. , and van der Vorst , H. A. 1998. Numerical Linear Algebra for High-Performance Computers . SIAM , Philadelphia, PA . Dongarra, J. J., Duff, I. S., Sorensen, D. C., and van der Vorst, H. A. 1998. Numerical Linear Algebra for High-Performance Computers. SIAM, Philadelphia, PA."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144503428693"},{"volume-title":"High-performance implementation of the level-3 BLAS. Tech. rep. CS-TR-06-23. Department of Computer Sciences","author":"Goto K.","key":"e_1_2_1_11_1","unstructured":"Goto , K. and van de Geijn , R. 2006. High-performance implementation of the level-3 BLAS. Tech. rep. CS-TR-06-23. Department of Computer Sciences , The University of Texas at Austin, Austin, TX. Goto, K. and van de Geijn, R. 2006. High-performance implementation of the level-3 BLAS. Tech. rep. CS-TR-06-23. Department of Computer Sciences, The University of Texas at Austin, Austin, TX."},{"volume-title":"The Graduate Student\u2019s Guide to Numerical Analysis \u201998","author":"Higham N. J.","key":"e_1_2_1_12_1","unstructured":"Higham , N. J. 1999. Notes on accuracy and stability of algorithms in numerical linear algebra . In The Graduate Student\u2019s Guide to Numerical Analysis \u201998 , M. Axinsworth, J. Levesley, and M. Marletta, Eds. Springer-Verlag , Berlin, Germany , 48--82. Higham, N. J. 1999. Notes on accuracy and stability of algorithms in numerical linear algebra. In The Graduate Student\u2019s Guide to Numerical Analysis \u201998, M. Axinsworth, J. Levesley, and M. Marletta, Eds. Springer-Verlag, Berlin, Germany, 48--82."},{"key":"e_1_2_1_13_1","volume-title":"Accuracy and Stability of Numerical Algorithms","author":"Higham N. J.","unstructured":"Higham , N. J. 2002. Accuracy and Stability of Numerical Algorithms , 2 nd Ed. SIAM , Philadelphia, PA . Higham, N. J. 2002. Accuracy and Stability of Numerical Algorithms, 2nd Ed. SIAM, Philadelphia, PA.","edition":"2"},{"key":"e_1_2_1_14_1","first-page":"386","article-title":"On the solution of a system of linear equations whose matrix is symmetric but not definite","volume":"10","author":"Parlett B. N.","year":"1970","unstructured":"Parlett , B. N. and Reid , J. K. 1970 . On the solution of a system of linear equations whose matrix is symmetric but not definite . BIT 10 , 386 -- 397 . Parlett, B. N. and Reid, J. K. 1970. On the solution of a system of linear equations whose matrix is symmetric but not definite. BIT 10, 386--397.","journal-title":"BIT"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1916461.1916462","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1916461.1916462","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:14:52Z","timestamp":1750281292000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1916461.1916462"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,2]]},"references-count":14,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,2]]}},"alternative-id":["10.1145\/1916461.1916462"],"URL":"https:\/\/doi.org\/10.1145\/1916461.1916462","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"type":"print","value":"0098-3500"},{"type":"electronic","value":"1557-7295"}],"subject":[],"published":{"date-parts":[[2011,2]]},"assertion":[{"value":"2007-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-02-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}