Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2024 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

A new parallel chasing algorithm for transforming arrowhead matrices to tridiagonal form
HTML articles powered by AMS MathViewer

by Suely Oliveira PDF
Math. Comp. 67 (1998), 221-235 Request permission

Abstract:

Rutishauser, Gragg and Harrod and finally H.Y. Zha used the same class of chasing algorithms for transforming arrowhead matrices to tridiagonal form. Using a graphical theoretical approach, we propose a new chasing algorithm. Although this algorithm has the same sequential computational complexity and backward error properties as the old algorithms, it is better suited for a pipelined approach. The parallel algorithm for this new chasing method is described, with performance results on the Paragon and nCUBE. Comparison results between the old and the new algorithms are also presented.
References
  • Z. Chen, A parallel implementation of a chasing algorithm, tech. rep., Texas A&M University, 1996. project report.
  • Z. Chen, Y. Deng, and S. Oliveira, A parallel implementation of a new chasing algorithm, tech. rep., Texas A&M University, 1996. manuscript.
  • Y. Deng, Some applications of pipelining techniques in parallel scientific computing, Master’s thesis, Texas A&M University, 1996.
  • Gene H. Golub and Charles F. Van Loan, Matrix computations, 2nd ed., Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1989. MR 1002570
  • William B. Gragg and William J. Harrod, The numerically stable reconstruction of Jacobi matrices from spectral data, Numer. Math. 44 (1984), no. 3, 317–335. MR 757489, DOI 10.1007/BF01405565
  • H. Rutishauser, On Jacobi rotation patterns, Proc. Sympos. Appl. Math., Vol. XV, Amer. Math. Soc., Providence, R.I., 1963, pp. 219–239. MR 0160321
  • D. Stewart, A graph theoretical model of Givens rotations and its implications. Accepted by Linear Alg. Appl., 1996.
  • Sabine Van Huffel and Haesun Park, Parallel tri- and bi-diagonalization of bordered bidiagonal matrices, Parallel Comput. 20 (1994), no. 8, 1107–1128. MR 1290523, DOI 10.1016/0167-8191(94)90071-X
  • Sabine Van Huffel and Haesun Park, Efficient reduction algorithms for bordered band matrices, Numer. Linear Algebra Appl. 2 (1995), no. 2, 95–113. MR 1323815, DOI 10.1002/nla.1680020204
  • Hong Yuan Zha, A two-way chasing scheme for reducing a symmetric arrowhead matrix to tridiagonal form, J. Numer. Linear Algebra Appl. 1 (1992), no. 1, 49–57. MR 1169869
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC (1991): 65F15, 68R10, 65F50
  • Retrieve articles in all journals with MSC (1991): 65F15, 68R10, 65F50
Additional Information
  • Suely Oliveira
  • Affiliation: Department of Computer Science, Texas A&M University, College Station, Texas 77843
  • Email: suely@cs.tamu.edu
  • Received by editor(s): September 19, 1996
  • Additional Notes: This research is supported by NSF grant ASC 9528912 and a Texas A&M University Interdisciplinary Research Initiative Award.
  • © Copyright 1998 American Mathematical Society
  • Journal: Math. Comp. 67 (1998), 221-235
  • MSC (1991): Primary 65F15; Secondary 68R10, 65F50
  • DOI: https://doi.org/10.1090/S0025-5718-98-00895-3
  • MathSciNet review: 1433266