A Jacobi Method by Blocks on a Mesh of Processors
- Domingo Gimenez
- Departamento de Informatica y Sistemas
- Univ. de Murcia
- Aptdo 4021
- 30001 Murcia
- Spain
- domingo@dif.um.es
- Vicente Hernandez
- Departmento de Sistemas Informaticos y Computacion
- Univ. Politecnica de Valencia
- Aptdo 22012
- 46071 Volencia
- Spain
- cpvhg@dsic.upv.es
- Robert A. van de Geijn
- Department of Computer Sciences
- University of Texas
- Austin, TX 78712
- rvdg@cs.utexas.edu
- Antonio M. Vidal
- Departmento de Sistemas Informaticos y Computacion
- Univ. Politecnica de Valencia
- Aptdo 22012
- 46071 Volencia
- Spain
- cpavm@dsic.upv.es
Abstract
In this paper, we study the parallelization of the Jacobi
method to solve the symmetric eigenvalue problem on
a mesh of processors. To solve this problem obtaining a
theoretical efficiency of 100%, it is necessary to exploit
the symmetry of the matrix. The only previous algorithms
we know exploiting the symmetry on multicomputers is that in
[18], but that algorithm uses a storage scheme adequate
for a logical ring of processors, so having low scalability.
In this paper we show how matrix symmetry can be exploited
on a logical mesh of processors obtaining a higher scalability
that that obtained with the algorithm in [18]. In addition, we show how
the storage scheme exploiting the symmetry can be combined with a
scheme by blocks to obtain a highly efficient and scalable
Jacobi method for solving the symmetrix eigenvalue problem for distributed
memory parallel computers. We report performance results from the
Intel Touchstone DELTA.
D. Gimenez, V. Hernandez, R. van de Geijn, and A. Vidal,
A Jacobi Method by Blocks on a Mesh of Processors,
submitted to Concurrency: Practice and Experience.