{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:36:02Z","timestamp":1787322962049,"version":"3.56.0"},"reference-count":20,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[1996,10]]},"abstract":"<jats:p>We describe a divide-and-conquer tridiagonalization approach for matrices with repeated eigenvalues. Our algorithm hinges on the fact that, under easily constructively verifiable conditions, a symmetric matrix with band width b and k distinct eigenvalues must be block diagonal with diagonal blocks of size at most $bk$. A slight modification of the usual orthogonal band-reduction algorithm allows us to reveal this structure, which then leads to potential parallelism in the form of independent diagonal blocks. Compared to the usual Householder reduction algorithm, the new approach exhibits improved data locality, significantly more scope for parallelism, and the potential to reduce arithmetic complexity by close to 50% for matrices that have only two numerically distinct eigenvalues. The actual improvement depends to a large extent on the number of distinct eigenvalues and a good estimate thereof. However, at worst the algorithms behave like a successive band-reduction approach to tridiagonalization. Moreover, we provide a numerically reliable and effective algorithm for computing the eigenvalue decomposition of a symmetric matrix with two numerically distinct eigenvalues. Such matrices arise, for example, in invariant subspace decomposition approaches to the symmetric eigenvalue problem.<\/jats:p>","DOI":"10.1137\/s0895479892227608","type":"journal-article","created":{"date-parts":[[2005,2,27]],"date-time":"2005-02-27T07:15:07Z","timestamp":1109488507000},"page":"869-885","source":"Crossref","is-referenced-by-count":1,"title":["On Tridiagonalizing and Diagonalizing Symmetric Matrices with Repeated Eigenvalues"],"prefix":"10.1137","volume":"17","author":[{"given":"Christian H.","family":"Bischof","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaobai","family":"Sun","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","volume-title":"LAPACK User's Guide","author":"Anderson E.","year":"1992"},{"key":"R2","volume-title":"LAPACK User's Guide Release 2.0","author":"Anderson E.","year":"1994"},{"key":"R3","unstructured":"L. Auslander, A. Tsao,  A Divide-and-Conquer Algorithm for the Eigenproblem Via Complementary Invariant Subspace Decomposition, Tech. report, SRC-TR-89-003, Supercomputing Research Center, Institute for Defense Analysis, Bowie, MD,  1989"},{"key":"R4","unstructured":"Z. Bai, J. Demmel,  Design of a parallel nonsymmetric eigenroutine toolbox, Part I,  Proc. of the Sixth SIAM Conference on Parallel Processing for Scientific Computing,  1993,  391\u2013398"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1080\/10556789308805543"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"C. Bischof, S. Huss-Lederman, X. Sun, A. Tsao,  The PRISM project: Infrastructure and algorithms for parallel eigensolvers,  Proc. of the Scalable Parallel Libraries Conference, IEEE Computer Society, Washington, DC,  1994,  123\u2013131","DOI":"10.1109\/SPLC.1993.365575"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"C. Bischof, X. Sun, B. Lang,  Parallel tridiagonalization through two-step band reduction,  Proc. of Scalable High Performance Computing Conference, IEEE Computer Society Press, Knoxville, TN,  1994,  23\u201327","DOI":"10.1109\/SHPCC.1994.296622"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-75833-1_13"},{"key":"R9","volume-title":"Parallel and Vector Supercomputing: Methods and Algorithms","author":"Bischof C. H.","year":"1989"},{"key":"R10","unstructured":"C. H. Bischof, X. Sun,  A Framework for Band Reduction and Tridiagonalization of Symmetric Matrices,  1992, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL, Preprint MCS-P298-0392"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/0908009"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(88)90071-3"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(92)90011-U"},{"key":"R14","series-title":"Oxford Sci. Publ.","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1093\/oso\/9780198535645.003.0019","volume-title":"Reliable numerical computation","author":"Dongarra Jack","year":"1990"},{"key":"R15","unstructured":"J. J. Dongarra, S. J. Hammarling, D. C. Sorensen,  Block Reduction of Matrices to Condensed Form for Eggenvalue Computations, Tech. report, MCS-TM-99, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL,  1987"},{"key":"R16","volume-title":"Matrix computations","author":"Golub Gene H.","year":"1989"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1145\/44128.44130"},{"key":"R18","volume-title":"The theory of matrices in numerical analysis","author":"Householder Alston S.","year":"1964"},{"key":"R19","unstructured":"S. Lederman, A. Tsao, T. Turnbull,  A Parallelizable Eigensolver for Real Diagonalizable Matrices with Real Eigenvalues, Tech. report, TR-91-042, Supercomputing Research Center, Institute for Defense Analysis, Bowie, MD,  1991"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/0910005"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0895479892227608","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:35:38Z","timestamp":1787319338000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0895479892227608"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,10]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1996,10]]}},"alternative-id":["10.1137\/S0895479892227608"],"URL":"https:\/\/doi.org\/10.1137\/s0895479892227608","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,10]]}}}