{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T07:41:59Z","timestamp":1787384519279,"version":"build-2736575974"},"reference-count":32,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2006,1]]},"abstract":"<jats:p>Bisection is one of the most common methods used to compute the eigenvalues of symmetric tridiagonal matrices. Bisection relies on the Sturm count: For a given shift \u03c3, the number of negative pivots in the factorization $T - \\sigma I = LDL^T$ equals the number of eigenvalues of T that are smaller than \u03c3. In IEEE\u2010754 arithmetic, the value \u221e permits the computation to continue past a zero pivot, producing a correct Sturm count when T is unreduced. Demmel and Li showed [IEEE Trans. Comput., 43 (1994), pp. 983\u2013992] that using \u221e rather than testing for zero pivots within the loop could significantly improve performance on certain architectures. When eigenvalues are to be computed to high relative accuracy, it is often preferable to work with $LDL^T$ factorizations instead of the original tridiagonal T. One important example is the MRRR algorithm. When bisection is applied to the factored matrix, the Sturm count is computed from $LDL^T$ which makes differential stationary and progressive qds algorithms the methods of choice. While it seems trivial to replace T by $LDL^T$, in reality these algorithms are more complicated: In IEEE\u2010754 arithmetic, a zero pivot produces an overflow followed by an invalid exception (NaN, or \u201cNot a Number\u201d) that renders the Sturm count incorrect. We present alternative, safe formulations that are guaranteed to produce the correct result. Benchmarking these algorithms on a variety of platforms shows that the original formulation without tests is always faster provided that no exception occurs. The transforms see speed\u2010ups of up to $2.6\\times$ over the careful formulations. Tests on industrial matrices show that encountering exceptions in practice is rare. This leads to the following design: First, compute the Sturm count by the fast but unsafe algorithm. Then, if an exception occurs, recompute the count by a safe, slower alternative. The new Sturm count algorithms improve the speed of bisection by up to $2\\times$ on our test matrices. Furthermore, unlike the traditional tiny\u2010pivot substitution, proper use of IEEE\u2010754 features provides a careful formulation that imposes no input range restrictions.<\/jats:p>","DOI":"10.1137\/050641624","type":"journal-article","created":{"date-parts":[[2006,11,28]],"date-time":"2006-11-28T18:05:07Z","timestamp":1164737107000},"page":"1613-1633","source":"Crossref","is-referenced-by-count":4,"title":["Benefits of IEEE\u2010754 Features in Modern Symmetric Tridiagonal Eigensolvers"],"prefix":"10.1137","volume":"28","author":[{"given":"Osni A.","family":"Marques","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"E. Jason","family":"Riedy","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christof","family":"V\u00f6mel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,9,29]]},"reference":[{"key":"R1","unstructured":"Advanced Micro Devices, Inc.\n                      AMD Athlon Processor x86 Code Optimization Guide\n                      , February 2002, 22007 revision K."},{"key":"R2","unstructured":"Advanced Micro Devices, Inc.\n                      Software Optimization Guide for AMD Athlon 64 and AMD Opteron\n                      , November 2004, 25112 revision 3.05."},{"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\u2019 Guide\n                      , 3rd ed., SIAM, Philadelphia, 1999.","DOI":"10.1137\/1.9780898719604"},{"key":"R4","unstructured":"ANSI\/IEEE,\n                      IEEE Standard for Binary Floating Point Arithmetic\n                      , 754\u20131985 ed., New York, 1985."},{"key":"R5","unstructured":"T. Davis,\n                      University of Florida Sparse Matrix Collection\n                      , http:\/\/www.cise.ufl.edu\/research\/sparse\/matrices\/, NA Digest, 92 (1994) (Oct. 16), 96 (1996) (July 23), and 97 (1997) (June 7)."},{"key":"R6","first-page":"116","volume":"3","author":"Demmel J. W.","year":"1995","journal-title":"Electron. Trans. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/1097-4067","issn-type":"print"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/0911052"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1109\/12.295860"},{"key":"R9","unstructured":"I. S. Dhillon, B. N. Parlett, and C. V\u00f6mel,\n                      LAPACK Working Note 162: The Design and Implementation of the MRRR Algorithm\n                      , Tech. report UCBCSD\u201004\u20131346, University of California, Berkeley, CA, 2004."},{"key":"R10","unstructured":"I. S. Duff, R. G. Grimes, and J. G. Lewis,\n                      Users\u2019 Guide for the Harwell\u2010Boeing Sparse Matrix Collection (Release I)\n                      , Tech. report RAL\u2010TR\u201092\u2013086, Atlas Centre, Rutherford Appleton Laboratory, Oxfordshire, UK, 1992."},{"key":"R11","unstructured":"I. S. Duff, R. G. Grimes, and J. G. Lewis,\n                      The Rutherford\u2010Boeing Sparse Matrix Collection\n                      , Tech. report RAL\u2010TR\u201097\u2013031, Atlas Centre, Rutherford Appleton Laboratory, Oxfordshire, UK, 1997."},{"key":"R12","unstructured":"E. Apra et al.\n                      NWChem, a Computational Chemistry Package for Parallel Computers\n                      , version 4.7, Tech. report, Pacific Northwest National Laboratory, Richland, WA, 2005."},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/S0010-4655(00)00065-5"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/s002110050024"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1002\/nla.1680020604"},{"key":"R16","unstructured":"G. H. Golub and C. van Loan,\n                      Matrix Computations\n                      , 3rd ed., The Johns Hopkins University Press, Baltimore, MD, 1996."},{"key":"R17","unstructured":"Intel Corporation,\n                      Intel Itanium 2 Processor Reference Manual for Software Development and Optimization\n                      , 251110\u2013003, 2004."},{"key":"R18","unstructured":"Intel Corporation,\n                      IA\u201032 Intel Architecture Optimization Reference Manual\n                      , 248966\u2013012, 2005."},{"key":"R19","unstructured":"W. Kahan,\n                      Accurate Eigenvalues of a Symmetric Tridiagonal Matrix\n                      , Technical report CS41, Computer Science Department, Stanford University, Stanford, CA, 1966 (revised 1968)."},{"key":"R20","unstructured":"W. Kahan,\n                      A Demonstration of Presubstitution for $\\infty\/\\infty$\n                      , unpublished, 2005."},{"key":"R21","doi-asserted-by":"crossref","unstructured":"M. Overton,\n                      Numerical Computing with IEEE Floating Point Arithmetic\n                      , SIAM, Philadelphia, 2001.","DOI":"10.1137\/1.9780898718072"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"B. N. Parlett,\n                      The new qd algorithms\n                      , in Acta Numerica, 1995, Acta Numer., Cambridge University Press, Cambridge, UK, 1995, pp. 459\u2013491.","DOI":"10.1017\/S0962492900002580"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(97)00022-0"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(99)00262-1"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2003.12.028"},{"key":"R26","first-page":"858","volume":"25","author":"Parlett B. N.","year":"2004","journal-title":"SIAM J. Matrix Anal. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0895-4798","issn-type":"print"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(00)00010-0"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1007\/BF01600331"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"H. Rutishauser,\n                      Vorlesungen \u00fcber Numerische Mathematik\n                      , Birkh\u00e4user Verlag, Basel, 1976.","DOI":"10.1007\/978-3-0348-5509-9"},{"key":"R30","unstructured":"Silicon Graphics, Inc.\n                      Origin 2000 and Onyx2 Performance Tuning and Optimization Guide\n                      , Document 007\u20103430\u2010003, Mountain View, CA, 2002."},{"key":"R31","unstructured":"Sun Microsystems, Inc.\n                      UltraSPARC\u2010IIi User\u2019s Manual\n                      , 805\u20100087\u201001, 1997."},{"key":"R32","unstructured":"S. Andersson, R. Bell, J. Hague, H. Holthoff, P. Mayes, J. Nakano, D. Shieh, and J. Tuccillo,\n                      RS\/6000 Scientific and Technical Computing: POWER3 Introduction and Tuning Guide\n                      , 1st ed., IBM, Austin, TX, 1998."}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/050641624","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:54:57Z","timestamp":1787334897000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/050641624"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1]]},"references-count":32,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2006,1]]}},"alternative-id":["10.1137\/050641624"],"URL":"https:\/\/doi.org\/10.1137\/050641624","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,1]]}}}