Parallel implementation of bisection for the calculation of eigenvalues of tridiagonal symmetric matrices (Q1069670)

\textit{D. J. Kuck} and \textit{A. H. Sameh} [Inform. Processing 71, Proc. IFIP Congr. 1971, Ljubljana, Yugoslavia 1971, 1266-1272 (1972; Zbl 0256.65024)], \textit{H.-M. Huang} [A parallel algorithm for symmetric tridiagonal eigenvalue problems. CAC Document No.109, Center for Advanced Computation, University of Illinois at Urbana-Champaign, February 1974] and \textit{Y. Wallach} [Alternating sequential/parallel processing, Lect. Notes in Computer Science 127 (1982; Zbl 0495.68002)] have investigated parallel implementations of Givens' bisection algorithm. On an MIMD (multiple instruction stream - multiple data stream) machine one could apply parallelism on any or all of three levels: within each Sturm sequence calculation, within each individual bisection, or on the outer level assigning intervals to be searched. We show that allocating bisections to individual processors on the outer level is more effective than having processors share the work of a bisection when the number of processors is smaller than the number of eigenvalues to be found.