SOME CRITERIA FOR THE HOMOTOPY METHOD FOR

THE TRIDIAGONAL EIGENPROBLEM

Kuiyuan Li

University of West Florida

Abstract. In this paper, we shall give some criteria which guarantee the safety of choosing a diagonal starting matrix of the homotopy method for the symmetric tridiagonal eigenproblem.

1. Introduction. The homotopy continuation method can be used to solve the symmetric eigenvalue problem:

(1)  Ax = λx

where A is an n × n real symmetric tridiagonal matrix of the form

(2)  A = ( \begin{matrix}α_{1} & β_{2} \\ β_{2} & α_{2} & β_{3} \\ & ... & ... & ... \\ & & β_{n−1} & α_{n−1} & β_{n} \\ & & & β_{n} & α_{n} \end{matrix} ) .

In (2), if some β_{i} = 0, then ℝ^{n} is clearly decomposed into two complementary subspaces invariant under A. Thus, the eigenproblem is decomposed in an obvious way into two smaller subproblems. Therefore we will assume that each β_{i} ≠ 0. That is, A is unreduced.

Consider the homotopy, H: ℝ^{n} × ℝ × [0, 1] → ℝ^{n} × ℝ, defined by

(3)  \begin{aligned}H(x, λ, t) & = (1 − t) ( λx − Dx_{\frac{x^{T} x−1}{2}} ) + t ( λx − Ax_{\frac{x^{T} x−1}{2}} ) \\ & = ( λx − [(1 − t)D + tA]x_{\frac{x^{T} x−1}{2}} ) \\ & = ( λx − A(t)x_{\frac{x^{T} x−1}{2}} ) \end{aligned}

where A(t) = (1 − t)D + tA. Here, D is the initial matrix, a specially chosen symmetric tridiagonal matrix such that A(t) is unreduced for t in (0, 1]. It can be seen that the solution set of H(x, λ, t) = 0 in (3) consists of disjoint smooth curves (x(t), λ(t)), each joins an eigenpair of D to one of A. We call each of these curves a homotopy curve or an eigenpath and its component λ(t) an eigenvalue path. Thus, by following the eigenpaths emanating from the eigenpairs of D at t = 0, we can reach all the eigenpairs of A at t = 1.

The theoretical aspect of the continuation approach to the eigenvalue problems has been studied in [1,2,3,9]. A first attempt was made in [7] to make the method computationally efficient. In [7], the initial matrix D was chosen as D = diag{α_{1}, α_{2}, …, α_{n}}. An efficient parallel and robust algorithm was given in [6]. Evidenced by the numerical results, the algorithm is strongly competitive with other methods in terms of speed, accuracy and orthogonality, and leads in speed in almost all cases. In [6],

(4)  D = ( \begin{matrix}D_{1} & 0 \\ 0 & D_{2} \end{matrix} )

where

D_{1} = ( \begin{matrix}α_{1} & β_{2} \\ β_{2} & α_{2} & β_{3} \\ & ... & ... & ... \\ & & β_{k−1} & α_{k−1} & β_{k} \\ & & & β_{k} & α_{k} \end{matrix} ) , D_{2} = ( \begin{matrix}α_{k+1} & β_{k+2} \\ β_{k+2} & α_{k+2} & β_{k+3} \\ & ... & ... & ... \\ & & β_{n−1} & α_{n−1} & β_{n} \\ & & & β_{n} & α_{n} \end{matrix} ) .

It is desirable to choose D as a diagonal matrix, consisting of the diagonal part of A, rather than the form in [6]. If D is a diagonal matrix, then eigenvalues and corresponding eigenvectors of D are immediately available. Thus, the work of solving the eigenproblem of D is saved. In [7], Li and Rhee showed that this strategy worked very well for certain matrices, such as [1, i, 1], i = 1, 2, …, n. That is, if we choose D = diag{1, 2, …, n} in solving the eigenproblem of the matrix [1, i, 1], the eigenpaths are still very flat and easy to follow. However, this strategy breaks down when we consider the eigenproblem of tridiagonal matrices [1, 2, 1]. The eigenpaths are rather difficult to follow. In this paper, we shall give some criteria which guarantee the safety of choosing a diagonal starting matrix D.

2. Criteria. Let (A)^{1} denote the (n − 1) × (n − 1) matrix obtained by deleting the first row and column of A, and (A)_{1} the (n − 1) × (n − 1) matrix obtained by deleting the last row and column of A. Let λ_{i}(A) denote the ith smallest eigenvalue of A.

\underline{Theorem 1}. If α_{i} < α_{i+1}, i = 1, 2, …, n − 1 and if there exists a constant c, 0 < c ≤ 1 such that

(A)^{1} − (A)_{1} − c min_{1≤i≤n−1}(α_{i+1} − α_{i})I

is positive semidefinite then

min_{1≤i≤n−1}(λ_{i+1} − λ_{i}) ≥ c min_{1≤i≤n−1}(α_{i+1} − α_{i})

where λ_{i} = λ_{i}(A).

\underline{Proof}. Since A is symmetric, so are (A)_{1} and (A)^{1}. Let

μ_{1} ≤ μ_{2} ≤ ⋯ ≤ μ_{n−1}

and

δ_{1} ≤ δ_{2} ≤ ⋯ ≤ δ_{n−1}

be the eigenvalues of (A)^{1} and (A)_{1}, respectively, then by Cauchy’s interlacing theorem [10],

(5)  λ_{1} ≤ μ_{1} ≤ λ_{2} ≤ ⋯ ≤ μ_{n−1} ≤ λ_{n}

(6)  λ_{1} ≤ δ_{1} ≤ λ_{2} ≤ ⋯ ≤ δ_{n−1} ≤ λ_{n}.

Since (A)^{1} = (A)_{1} +cαI +[(A)^{1} −(A)_{1} −cαI], and (A)^{1} −(A)_{1} −cαI is positive semidefinite, where

α = min_{1≤i≤n−1}(α_{i+1} − α_{i}),

by the Courant–Fisher maximum characterization [12],

λ_{i}((A)^{1}) ≥ λ_{i}((A)_{1} + cαI) for any i, 1 ≤ i ≤ n − 1

i.e.,

μ_{i} − δ_{i} ≥ cα > 0, 1 ≤ i ≤ n − 1.

By (5) and (6),

λ_{1} ≤ δ_{1} ≤ μ_{1} ≤ λ_{2} ≤ ⋯ ≤ δ_{n−1} ≤ μ_{n−1} ≤ λ_{n}.

Hence,

λ_{i+1} − λ_{i} ≥ μ_{i} − δ_{i} ≥ cα, 1 ≤ i ≤ n − 1

and

min_{1≤i≤n−1}(λ_{i+1} − λ_{i}) ≥ c min_{1≤i≤n−1}(α_{i+1} − α_{i}).

\underline{Corollary 1}. If

(A)_{1} − ( \begin{matrix}α_{1} \\ & . & . & . \\ & & & & α_{n−1} \end{matrix} ) = (A)^{1} − ( \begin{matrix}α_{2} \\ & . & . & . \\ & & & & α_{n} \end{matrix} ) ,

then

(7)  min_{1≤i≤n−1}(λ_{i+1} − λ_{i}) ≥ min_{1≤i≤n−1}(α_{i+1} − α_{i}).

\underline{Proof}. (7) follows immediately from Theorem 1, since

(A)^{1} − (A)_{1} − ( \begin{matrix}α_{2} − α_{1} \\ & . & . & . \\ α_{n} − α_{n−1} \end{matrix} ) = 0.

Let A(t) = (1 − t)D + tA, where D is a diagonal matrix consisting of the diagonal elements of A. Then we have the following corollary.

\underline{Corollary 2}.

min_{1≤i≤n−1}(λ_{i+1}(t) − λ_{i}(t)) ≥ c min_{1≤i≤n−1}(α_{i+1} − α_{i}), t ∈ [0, 1].

\underline{Proof}.

(8)  \begin{matrix}(A(t))^{1} − (A(t))_{1} − αI = t((A)^{1} − (A)_{1} − αI) \\ + (1 − t)diag(α_{2} − α_{1} − α, α_{3} − α_{2} − α, ⋯, α_{n} − α_{n−1} − α), \end{matrix}

where

α = c min_{1≤i≤n−1}(α_{i+1} − α_{i}), 0 < c ≤ 1.

Clearly, the second term of the right hand side of (8) is positive semidefinite and the first term is positive semidefinite by assumption. Hence, (A(t))^{1} −(A(t))_{1} −αI is positive semidefinite for t ∈ [0, 1]. By Theorem 1,

min_{1≤i≤n−1}(λ_{i+1}(t) − λ_{i}(t)) ≥ c min_{1≤i≤n−1}(α_{i+1} − α_{i}) t ∈ [0, 1].

\underline{Remark}. If (β_{i+1} − β_{i})^{2} < (α_{i} − α_{i−1})(α_{i+1} − α_{i}), i = 2, 3, …, n − 1 and α_{i} < α_{i+1}, i = 1, 2, …, n − 1, then A satisfies the conditions in Theorem 1.

If A satisfies the conditions in Theorem 1, we may choose the initial matrix D as a diagonal matrix consisting of the diagonal elements of A, then A(t) is an unreduced symmetric tridiagonal matrix and the eigenvalue curves are not only distinct, but also very well separated. There is a lower bound between any two eigenvalue curves so that the eigenvalue curves are easy to follow.

\underline{Example 1}. A = [1, i, 1], where i = 1, 2, …, 20. If we let D = diag\{1, 2, …, 20\}, then all the eigenvalue curves are very well separated. See Figure 1.

Figure 1. The eigenvalue curves of [1, i, 1] matrix with D = [0, i, 0].

\underline{References}

1. M. T. Chu, “A Simple Application of the Homotopy Method to Symmetric Eigenvalue Problems,” Linear Algebra and Appl., 59 (1984), 85–90.

2. M. T. Chu, “A Note on the Homotopy Method for Linear Algebraic Eigenvalue Problems,” Linear Algebra and Appl., 105 (1988), 225–236.

3. M. T. Chu, T. Y. Li and T. Sauer, “Homotopy Method for General λ-Matrix Problems,” SIAM J. Matrix Anal. and Appl., 9 (1988), 528–536.

4. J. J. Dongarra and D. C. Sorensen, “A Fully Parallel Algorithm for Symmetric Eigenvalue Problems,” SIAM J. Sci. Stat. Comput., 8 (1987), 139–154.

5. K. Li and T. Y. Li, “Homotopy Method for the Singular Symmetric Tridiagonal Eigenvalue Problem,” Missouri Journal of Mathematical Sciences, 6 (1994), 34–46.

6. K. Li and T. Y. Li, “An Algorithm for Symmetric Tridiagonal Eigen–problems – Divide and Conquer with Homotopy Continuation,” SIAM J. Sci. Comput., 14 (1993), 735– 751.

7. T. Y. Li and N. H. Rhee, “Homotopy Algorithm for Symmetric Eigenvalue Problems,” Numer. Math., 55 (1989), 256–280.

8. T. Y. Li and T. Sauer, “Homotopy Method for Generalized Eigenvalue Problems,” Lin. Alg. Appl., 91 (1987), 65–74.

9. T. Y. Li, T. Sauer and J. Yorke, “Numerical Solution of a Class of Deficient Polynomial Systems,” SIAM J. Numer. Anal., 24 (1987), 435–451.

10. B. N. Parlett, The Symmetric Eigenvalue Problem, Prentice–Hall, Englewood Cliffs, N.J., 1980.

11. B. T. Smith, et. al., Matrix Eigensystem Routines–EISPACK Guide, (2nd ed.), Springer–Verlag, New York, 1976.

12. J. H. Wilkinson, The Algebraic Eigenvalue Problem, Oxford University Press, New York, 1965.