SC740 SEMINAR REPORT 09 for Frederick L. Jones
PRESENTER: Dr. Kuiyuan Li
TOPIC: Homotopy Method for Tridiagonal Eigenvalue Problem
OVERVIEW
Dr. Kuiyuan Li described a fully parallel Homotopy Method of finding the eigenvalues of a real, tridiagonal matrix. The parallel Homotopy Method is a Divide–and-Conquer method based on the Homotopy Continuation. Dr. Li also presented numerical results of the Homotopy Method that were run on both single and multiprocessor systems.
HOMOTOPY THEORY
Since Dr. Kuiyuan Li assumed that Homotopy Theory was understood by all of the audience, he did not explain it to the audience. However, I do not think that everyone in the audience understood algebraic topology. Therefore, I will briefly explain Homotopy Theory by virtually quoting from the following online definition found at the following web page:
www.ma.umist.ac.uk/kd/knots/node2.html.
Algebraic topology involves the classification of topological spaces in terms of algebraic objects (groups,rings) that are invariant under usefully large classes of homomorphisms. The fundamental concept here is that of homotopy equivalence, for maps and spaces.
A pair of continuous maps f,g: X ® Y which agree on A Í X is said to admit a homotopy H from f to g relative to A if there is a map X x [0,1] H® Y : ( x,t) ® Ht(x) with Ht(a) = H(a,t) = f(a) = g(a) for all a ' A, H0 = H( ,0) = t, and H1 = H( ,1) = g. … If A = 0 or A is clear from the context, then we write f H~ g and say that f and g are homotopic.
The concept of Homotopy Continuation within Homotopy Theory also has a specific definition. However, my attempt to find one specific definition of "Homotopy Continuation" on the Internet failed. However, I did find several references to Homotopy Continuation method solutions of Eigenvalue Problems at Web Pages such as the following one:
www.siam.org/meetings/archives/SM96/slc.html.
THE TRIDIAGONAL EIGENVALUE PROBLEM
Dr. Kuiyuan Li really started his presentation with a description of the Tridiagonal Eigenvalue Problem. The Tridiagonal Eigenvalue Problem was described in terms of finding the eigenvalues of a real matrix PENCIL (A,B), where A and B are real, symmetric, tridiagonal and at least one of them is positive definite. (Note: The PENCIL of a pair of matrices (A,B) is the eigenpair (l ,z), where l is an eigenvalue and z is a stationary point, i.e. a point where its time derivatives vanish.)
Dr. Li continued his presentation with a description of several of the solution techniques currently in use for tridiagonal systems. Dr. Li noted that the QR method was stable but not parallel. The Bisection method was also described by Dr. Li as stable, parallel, but slow solution method. The Divide and Conquer method was described as stable and parallel. Finally, the Homotopy method was listed as both stable and parallel.
THE HOMOTOPY CONTINUATION METHOD
The Homotopy Continuation Method presented by Dr. Li was described as an attempt to replace a Tridiagonal Matrix A with a Diagonal Matrix B containing approximations of the eigenvectors. Dr. Li presented his argument formally as follows:
A x = l x
xTx = 1
A x - l x = 0
xTx - 1 = 0
A x - l x
let p(l ,x) = , then p(l ,x) = 0.
xTx - 1
H(l ,x,t) = tQ(l ,x) + (1-t) p(l ,x)
H(l ,x,t) = (l ,t)Q(l ,x) + t p(l ,x) = 0
B x - l x
let Q(l ,x) =
xTx - 1
The justification for using a parallel Homotopy Continuation Method as an Eigenvalue solution technique was described formally as follows:
(1)All eigenvalue curves are disjoint, continuous and differentiable.
(2)l (t) is strictly monotone or l (t) = C.
(3)l I-1(0) < l i(1) < l I+1(0) "
(4)l 1(t) is concave downward, l n(t) is concave upward
n
(5)å (l i(0) - l i(1)) < 2 B2R+1
i=1
SUMMARY AND CONCLUSIONS
Dr. Kuiyuan Li described a fully parallel Homotopy Method of finding the eigenvalues of a real, tridiagonal matrix. The parallel Homotopy Method is a Divide–and-Conquer method based on the Homotopy Continuation. Dr. Li also presented numerical results of the Homotopy Method that were run on both single and multiprocessor systems.