{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:37:46Z","timestamp":1787337466493,"version":"build-2736575974"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>\n                    Surprisingly simple corollaries from the Courant--Fischer minimax characterization theorem enable us to devise a very effective algorithm for the evaluation of a set S interleaving the set E of the eigenvalues of an n X n real symmetric tridiagonal (rst) matrix T\n                    <jats:sub>n<\/jats:sub>\n                    (as well as a point that splits E into two subsets of comparable cardinalities). Furthermore, we extend this algorithm so as to approximate all the n eigenvalues of T\n                    <jats:sub>n<\/jats:sub>\n                    at nearly optimal sequential and parallel cost, that is, at the cost of staying within polylogarithmic factors from the straightforward lower bounds. The resulting improvement of the known processor bound in NC algorithms for the rst-eigenproblem is roughly by factor n. Our approach extends the previous works [M. Ben-Or and P. Tiwari, J. Complexity, 6(1990), pp. 417--442] and [M. Ben-Or et al., SIAM J. Comput., 17(1988), pp. 1081--1092] for the approximation of the zeros of a polynomial having only real zeros, and our algorithm leads to an alternative and simplified derivation of the known record parallel and sequential complexity estimates for the latter problem.\n                  <\/jats:p>","DOI":"10.1137\/s0097539790182482","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1099-1115","source":"Crossref","is-referenced-by-count":20,"title":["Computing Matrix Eigenvalues and Polynomial Zeros Where the Output is Real"],"prefix":"10.1137","volume":"27","author":[{"given":"Dario","family":"Bini","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Victor Y.","family":"Pan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","unstructured":"A. Aho, D\u017e. Hopkroft, D\u017e. Ulp\u00b8man, Postroenie i analiz vychislitelnykh algoritmov, \u201cMir\u201d, 1979, 536\u20130, Translated by A. O. Slisenko; Edited by Ju. V. Matijasevi\u010d80g:68036"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"Dario Bini, Divide and conquer techniques for the polynomial root\u2010finding problem, de Gruyter, Berlin, 1996, 3885\u201338961389341","DOI":"10.1515\/9783110883237.3885"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/0217069"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/s002110050035"},{"key":"R5","volume-title":"The computational complexity of algebraic and numeric problems","author":"Borodin Allan","year":"1975"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01396012"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(90)90032-9"},{"key":"R8","unstructured":"Dario Bini, Victor Pan, Parallel complexity of tridiagonal symmetric eigenvalue problem, ACM, New York, 1991, 384\u20133931095855"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/BF02241709"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/0222041"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"D. Bini and V. Y. Pan,\n                      Matrix and Polynomial Computations, Volume 1: Fundamental Algorithms\n                      , Birkhauser, Boston, 1994.","DOI":"10.1007\/978-1-4612-0265-3_1"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321815"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/BF01396757"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479892241287"},{"key":"R15","unstructured":"G. H. Golub and C. F. Van Loan,\n                      Matrix Computations\n                      , The Johns Hopkins Univ. Press, Baltimore, MD, 1989."},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(87)90019-3"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(87)90186-6"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"V. Y. Pan,\n                      Optimal (up to polylog factors) sequential and parallel algorithms for approximating complex polynomial zeros\n                      , in Proc. 27th Annual ACM Symposium on Theory of Computing, ACM, New York, 1995, pp. 741\u2013750.","DOI":"10.1145\/225058.225292"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/BF02431995"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(96)00080-6"},{"key":"R21","unstructured":"B. N. Parlett,\n                      The Symmetric Eigenvalue Problem\n                      , Prentice\u2010Hall, Englewood Cliffs, NJ, 1980."},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(93)90129-J"},{"key":"R23","first-page":"483","volume":"4","author":"Pan Victor","year":"1997","journal-title":"Ann. Numer. Math."},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(85)90002-6"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"J. H. Reif and S. H. Tate,\n                      Optimal size integer division circuits\n                      , in Proc. 21st ACM Symposium on Theory of Computing, ACM Press, New York, 1989, pp. 264\u2013270.","DOI":"10.1145\/73007.73032"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(87)90022-7"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"J. H. Reif,\n                      An O(nlog3n) algorithm for the real root problem\n                      , in Proc. 34th Annual IEEE Symposium on Foundations on Computer Science, IEEE, Piscataway, NJ, 1993, pp. 626\u2013635.","DOI":"10.1109\/SFCS.1993.366824"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"J. H. Reif,\n                      Approximate complex polynomial evaluation in near constant work per point\n                      , in Proc. 29th Annual ACM Symposium on Theory of Computing, ACM, New York, 1997, pp. 30\u201339.","DOI":"10.1145\/258533.258543"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539790182482","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:07Z","timestamp":1787335927000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539790182482"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539790182482"],"URL":"https:\/\/doi.org\/10.1137\/s0097539790182482","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}