page 1  (14 pages)
2to next section

Data Parallel Lanczos and Pad?e-Rayleigh-Ritz

Methods on the CM5

Nahid Emad?
Laboratoire PRiSM, Universit?e Versailles St-Quentin
45, av. des ?Etats-Unis 78000 Versailles France
emad@prism.uvsq.fr

Abstract
The projective Pad?e-Rayleigh-Ritz method that we developed in [6]consists in approximating
the eigenvalues of a hermitian matrix A of order n, by the roots of the polynomial of degree m of the denominator of [m ? 1=m]Rx (>=) where [m ? 1=m]Rx(>=) is the Pad?e approximant of order m of Rx(>=) = ((I ? >=A)?1x; x) the mean value of the resolvant of A. The Lanczos and PRR methods are closely linked. This prompts us to ask first whether PRR has a good stability property compared with the Lanczos. The second question which arises is to know if the exploitation of this method can be interesting from the point of view of its computation cost. In this paper we deal more particularly with this practical second question than with the first. Next, we give performances of the projection phase of these two methods on the massively parallel architecture of Connection Machine 5 (CM5).

Keywords : projection method, large symmetric eigenproblem, Krylov's vectors, sparse matrix, data parallelism, massively parallel architecture, mapping strategy.

R?esum?e
La m?ethode de projection Pad?e-Rayleigh-Ritz que nous avons d?evelopp?e dans [6]consiste ?a approcher les valeurs propres d'une matrice hermitienne A d'ordre n, par les racines du polyn^ome du degr?e m du d?enominateur de [m ? 1=m]Rx (>=) o?u [m ? 1=m]Rx(>=) est l'approximant de Pad?e d'ordre m de Rx(>=) = ((I ? >=A)?1x; x) la valeur moyenne de la r?solvante de A. Les m?ethodes de Lanczos et PRR sont tr?es ?etroitement li?ees. La premi?ere question qui se pose est PRR est-elle une m?ethode num?eriquement stable relativement ?a Lanczos? La question suivante est l'exploitation de cette m?ethode conduit-elle ?a des r?esultats int?eressant au point du vue du co^ut du calcul? Dans ce papier nous nous concentrons sur cette seconde question pratique plut^ot que sur la premi?ere. Nous pr?esentons, alors, les performances de la phase de projection de ces deux m?ethodes sur l'architecture massivement parall?ele de la Connection Machine 5 (CM5).

Mots cl?es : m?ethode de projection, grand probl?eme de valeur propre, vecteurs de Krylov, matrices creuses, data-parall?elisme, architectures massivement parall?eles, placement de donn?ees.

?This work has been supported in part by the Army Research Office under grant number DAAL03-89-C-0038, USA, and in part by PRC PARADIGM of the CNRS, FRANCE.