|
A new parallel chasing algorithm for transforming arrowhead matrices to tridiagonal form
Author(s):
Suely
Oliveira.
Journal:
Math. Comp.
67
(1998),
221-235.
MSC (1991):
Primary 65F15;
Secondary 68R10, 65F50
Retrieve article in:
PDF DVI PostScript
This article is available free of charge
Abstract |
References |
Similar articles |
Additional information
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:
- 1.
- Z. Chen, A parallel implementation of a chasing algorithm, tech. rep., Texas A&M University, 1996. project report.
- 2.
- Z. Chen, Y. Deng, and S. Oliveira, A parallel implementation of a new chasing algorithm, tech. rep., Texas A&M University, 1996. manuscript.
- 3.
- Y. Deng, Some applications of pipelining techniques in parallel scientific computing, Master's thesis, Texas A&M University, 1996.
- 4.
- G. Golub and C. Van Loan, Matrix Computations, 2nd ed., Johns Hopkins Univ. Press, Baltimore, MD, 1989. MR 90d:65055
- 5.
- W. B. Gragg and W. J. Harrod, The numerically stable reconstruction of Jacobi matrices from spectral data, Numer. Math., 44 (1984), pp. 317-335. MR 85i:65052
- 6.
- H. Rutishauser, On Jacobi rotation patterns, in Proceedings of Symposia in Applied Mathematics, vol. XV, Providence, RI, 1963, pp. 219-239. MR 28:3534
- 7.
- D. Stewart, A graph theoretical model of Givens rotations and its implications. Accepted by Linear Alg. Appl., 1996.
- 8.
- S. Van Huffel and H. Park, Parallel tri- and bi-diagonalization of bordered bidiagonal matrices, Parallel Computing, 20 (1994), pp. 1107-1128. MR 95f:65082
- 9.
- height 2pt depth -1.6pt width 23pt, Efficient reduction algorithms for bordered band matrices, Numer. Linear Alg. Appl., 2 (1995), pp. 95-113. MR 96a:65070
- 10.
- H. Zha, A two-way chasing scheme for reducing an arrowhead matrix to tridiagonal form, J. Numer. Lin. Alg. Appl., 1 (1992), pp. 49-57. MR 93c:65061
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
DOI:
10.1090/S0025-5718-98-00895-3
PII:
S 0025-5718(98)00895-3
Keywords:
Arrowhead matrices,
chasing algorithms,
pipeline algorithms
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 of article:
Copyright
1998,
American Mathematical Society
|
Comments: webmaster@ams.org