loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
3rd Euromicro Workshop on Parallel and Distributed Processing
Parallel QR algorithm for the complete eigensystem of symmetric matrices
San Remo, Italy
January 25-January 27
ISBN: 0-8186-7031-2
R.M.S. Ralha, Departamento de Matematica, Universidade do Minho, Braga, Portugal
We propose a parallel organization of the QR algorithm for computing the complete eigensystem of symmetric matrices. We developed Occam versions of standard sequential implementations of the QR algorithm: the procedure qr1 which computes only eigenvalues and qr2 for the computation of all eigenvalues and eigenvectors. The Occam procedure parqr2 is a parallel implementation of qr2 and was tested on a pipeline of 16 transputers. Although parqr2 could be used to compute the eigenvalues and eigenvectors of a symmetric tridiagonal matrix, it is best suited to be used in conjunction with a parallel algorithm for the reduction of a dense symmetric matrix to tridiagonal form where the orthogonal transformations are accumulated in an explicit way. In the practical tests parqr2 has proved to be efficient and we have carried out a simple analyses that appears to indicate that it is possible to use efficiently a number p of processors of the same order of magnitude of the size n of the matrix (p/spl les/n/6). This is an interesting result from the point of view of the scalability of our parallel algorithm.
Index Terms:
parallel algorithms; eigenvalues and eigenfunctions; matrix algebra; Occam; parallel QR algorithm; eigensystem; symmetric matrices; Occam versions; sequential implementations; symmetric tridiagonal matrix; dense symmetric matrix; scalability; parallel algorithm
Citation:
R.M.S. Ralha, "Parallel QR algorithm for the complete eigensystem of symmetric matrices," pdp, pp.480, 3rd Euromicro Workshop on Parallel and Distributed Processing, 1995
Usage of this product signifies your acceptance of the Terms of Use.