Abstract

Title: A Parallel Algorithm for Computing Eigenpairs of a Symmetric Matrix

Undergraduate Student: Maxim Naumov

Supervisor: Professor Ahmed Sameh   

The purpose of this project was to develop a new algorithm for computing eigenpairs of a real symmetric matrix in             some given interval on a parallel computer.

The algorithm will compute Gerschgorian circles of the matrix M, and then for each of the processors it will do the following (can be done in parallel by each of the processors): 

1) Choose a circle to be isolated that has not been isolated yet. Isolate that circle by moving other circles centers, which in reality means add to M a diagonal perturbation matrix E.

2) Once we have an isolated Gerschgorian circle we know that there is at least one eigenvalue inside that isolated circle.  Find that eigenvalue using Newton’s method with initial seed being the center of the isolated circle. 

3) Correct the eigenvalue found to be the one of matrix M not M+E. In  practice it means  find  an eigenvalue of M using Newton’s   method  and  starting  with  initial  seed  as  the  eigenvalue  found  in  step 2.  Also find the corresponding eigenvector for it and correct the eigenvector to be of matrix M not N (matrix resulting after deflation) if deflation has been done.

4) Wait for all the processors to be done. Deflate all the distinct eigenvalues found from matrix M. Which in practice means pre multiply and post multiply matrix M by special matrices H  and from the resulting matrix  N  take a smaller matrix of dimension mxm, where m = n - # of distinct eigenvalues.

5) If all eigenpairs were found stop and you are done. Otherwise start at step 1 again using deflated matrix N.