An efficient Jacobi-like algorithm for parallel eigenvalue computation

Author

Götze, Jürgen ; Paul, Steffen ; Sauer, Matthias

Author_Institution

Inst. for Network Theor. and Circ. Des., Tech. Univ, Munich, Germany

Volume

42

Issue

9

fYear

1993

fDate

9/1/1993 12:00:00 AM

Firstpage

1058

Lastpage

1065

Abstract

A very fast Jacobi-like algorithm for the parallel solution of symmetric eigenvalue problems is proposed. It becomes possible by not focusing on the realization of the Jacobi rotation with a CORDIC processor, but by applying approximate rotations and adjusting them to single steps of the CORDIC algorithm, i.e., only one angle of the CORDIC angle sequence defines the Jacobi rotation in each step. This angle can be determined by some shift, add and compare operations. Although only linear convergence is obtained for the most simple version of the new algorithm, the overall operation count (shifts and adds) decreases dramatically. A slow increase of the number of involved CORDIC angles during the runtime retains quadratic convergence

Keywords

convergence of numerical methods; eigenvalues and eigenfunctions; matrix algebra; parallel algorithms; signal processing; CORDIC angle sequence; CORDIC processor; Jacobi rotation; Jacobi-like algorithm; approximate rotations; digital signal processing; eigenvalue computation; fast implementations; linear convergence; matrix computation; parallel eigenvalue computation; quadratic convergence; scaling computation; symmetric eigenvalue problems; Concurrent computing; Convergence; Digital signal processing; Eigenvalues and eigenfunctions; Helium; Jacobian matrices; Matrix decomposition; Runtime; Signal processing algorithms; Symmetric matrices;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/12.241595

Filename

241595