On the Convergence of Parallelized Eberlein Methods

D.Pupovci Department of Mathematics, University of Prishtina, M.Tita bb., 38000 Prishtina, Yugoslavia and Vjeran Hari^{∗} Department of Mathematics, University of Zagreb, Bijenička cesta 30, 41001 Zagreb, Croatia

Abstract. The well-known methods of Eberlein for diagonalizing general complex, real and symmetric complex matrices are modified to cope with parallel computing. The convergence is proved for all pivot strategies which are weakly equivalent to the modulus strategy. The obtained convergence results are quite similar to the known ones for the sequential methods under the serial strategies.

Subject Classifications: AMS (MOS): 65F15; CR: 5.14

Key Words and Phrases: Jacobi-type method, norm-reduction, modulus strategy

0 Introduction

The current arising interest in Jacobi-type methods is due to their adaptability for parallel processing. In this paper we consider the global convergence of some norm-reducing Jacobi-type methods under a class of pivot strategies which includes the most important sequential (i.e. the serial) and parallel strategies.

∗This paper was written while this author was visiting the Department of Mathematics, University of Kansas, Lawrence, Kansas.

The first efficient norm-reducing Jacobi-type methods have been proposed by Eberlein [1], [2] and Eberlein and Boothroyd [4]. Later Veselić [14] and Hari [5] have considered the global convergence of one of these methods. The first attempt to adapt a norm-reducing method for parallel computers is due to Sameh [12]. In their recent papers Luk and Park [10] and Hari [8] have considered convergence of Jacobi-type methods under the most common parallel strategies. Here we collect the ideas from all these papers to parallelize the methods of Eberlein and to prove appropriate convergence results which are not worse than the best known ones for the serial methods.

The paper is organized as follows. In Section 1 we provide a resume of the so called generalized cyclic Jacobi-type methods together with a general convergence result from [8]. In Section 2 we discuss the global convergence of the sequential methods of Eberlein, whereas in Section 3 we define the generalized cyclic (which include the parallel) versions of these methods. In Section 4 we prove convergence results of the new methods under a class of pivot strategies which are weakly-equivalent to the modulus one.

The results presented in Section 2 and especially in Section 3 and Section 4 are parts of an M.S.thesis [11].

The authors are indebted to the anonymous referee for helpful comments and suggestions.

1 Sequential and Parallel Jacobi-type Methods

Sequential Jacobi-type methods for solving eigenproblems of general matrices are iterative processes of the form

A^{(k+1)} = T_{k}^{−1}A^{(k)}T_{k}, k ≥ 1  (1.1)

where A^{(1)} = A is the initial matrix of order n , and T_{k}, k ≥ 1 are nonsingular elementary plane matrices. Each T_{k} is defined by a pair of indices (p_{k}, q_{k}) called pivot pair and by a 2 × 2 matrix T̂_{k} ,

T̂ = [ \begin{matrix}t_{p_{k}p_{k}}^{(k)} & t_{p_{k}q_{k}}^{(k)} \\ t_{q_{k}p_{k}}^{(k)} & t_{q_{k}q_{k}}^{(k)} \end{matrix} ] , k ≥ 1

called pivot submatrix of T_{k} or the (p_{k}, q_{k})-restriction of T_{k}. Here T_{k} = (t_{rs}^{(k)}) and except for its (p_{k}, q_{k})-restriction, T_{k} is equal to the identity matrix l_{n}. Each pivot submatrix T̂_{k} is determined by the algorithm of the method. If T̂_{k} depends only on Â^{(k)}, i.e. on the elements a_{p_{k}p_{k}}^{(k)}, a_{p_{k}q_{k}}^{(k)}, a_{q_{k}p_{k}}^{(k)} and a_{q_{k}q_{k}}^{(k)} for all k, the algorithm (or the method itself) is called simple. Typical examples of simple methods are (pure) Jacobi methods which diagonalize Â^{(k)} at each step. On the other side are the norm-reducing Jacobi-type methods where T̂_{k} depends on the elements of the l’th and m’th rows and columns of A^{(k)}. The matrices T_{k} and T̂_{k} shall be also denoted by T_{p_{k}q_{k}} and T̂_{p_{k}q_{k}}, respectively.

Besides by its algorithm each Jacobi-type method is defined by a pivot strategy. The most common are the serial strategies, i.e. the row- and the column-cyclic ones. They belong to a larger class of cyclic strategies. Each cyclic strategy is defined by an ordering of the set P_{n} = {(i, j); 1 ≤ i < j ≤ n}. If O = (i_{1}, j_{1}), …, (i_{N}, j_{N}), where N = n(n − 1)/2, is an ordering of P_{n} then it defines a cyclic strategy namely the one where the pivot pair runs through the sequence O in the cyclic way. For example, the row-cyclic strategy is defined by the row-cyclic ordering O_{R} = (1, 2), (1, 3), …, (1, n), (2, 3), …, (2, n), …, (n − 1, n).

Two pairs (i, j) and (p, q) from P_{n} are called disjoint or commuting provided that i ≠ p, i ≠ q and j ≠ p, j ≠ q. In the set O(P_{n}) of all orderings of P_{n} are defined the three equivalence relations: equivalence, shift-equivalence and weak-equivalence (cf. [13]). Two orderings from O(P_{n}) are equivalent if one can be derived from the other by a sequence of transpositions of adjacent disjoint pairs. If O is as above and O′ = (i_{σ+1}, j_{σ+1}), …, (i_{N}, j_{N}), (i_{1}, j_{1}), …, (i_{σ}, j_{σ}) for 0 ≤ σ < N, then O and O′ are shift-equivalent. The third equivalence relation is the join of the previous ones. Thus, O and Õ are weaklyequivalent if there is a sequence O_{1} = O, O_{2}, …, O_{m} = Õ of orderings from O(P_{n}), such that each O_{i}, 1 ≤ i < m is equivlent or shift- equivalent to O_{i+1}. Two cyclic strategies are equivalent (shift- or weak-equivalent) if their defining orderings from O(P_{n}) are such.

Jacobi-type methods are well suited for parallel processing. Here it is essential that under certain pivot strategies several consecutive plane transformations can be performed concurrently provided that the corresponding pivot pairs are commuting. For simple Jacobi-type methods such are certain cyclic strategies (see [10],[12],[13]). In general, however, we can use the concept of generalized cyclic (GC) strategies which includes both the cyclic strategies and the parallel strategies (the latter ones enable optimal concurrency). Each GC strategy is defined by a partition of P_{n} into subsets of commuting pairs (rotation sets) and by a numbering of this subset. A typical example of a parallel strategy is the modulus one (see [7],[10]) which is defined by the sequence M_{1}, …, M_{n} of subset, where

M_{τ} = {(i, j) ∈ P_{n}; i + j ≡ τ + 1(mod n)}, 1 ≤ τ ≤ n.

Note that each M_{τ} contains around [n/2] pairs where generally [a] denotes the largest integer ≤ a.

In the sequel we assume that R_{1}, …, R_{w} is the defining sequence of a given GC strategy. For τ ≥ 1 let

P iv(τ) = \{ \begin{matrix}R_{w} & if τ is a multiple of w \\ R_{τ mod w} & otherwise \end{matrix}

where τ mod w = τ −[τ/w]w. A GC Jacobi-type method is defined as follows (cf. [8]).

At time τ = 1, 2, ⋯ the nonsingular plane matrices T_{pq}^{[τ]}, (p, q) ∈ P iv(τ) are determined from the elements of A^{[τ]} and the similarity transformation

A^{[τ+1]} = T^{[τ]−1} A^{[τ]} T^{τ]}.  (1.2)

is accomplished, where A^{[1]} = A and

T^{[τ]} = ∏_{(p,q)∈P iv(τ)} T_{pq}^{[τ]}.  (1.3)

Since the pairs from P iv(τ), τ ≥ 1 are commuting the matrices T_{pq}^{[τ]}, (p, q) ∈ P iv(τ) commute, hence T^{[τ]} is well defined by the relation (1.3). We call P iv(τ) pivot set at time τ. Algorithm of a GC Jacobi-type method is just the algorithm for computing the matrices T̂_{pq}^{[τ]}.

If w = N, then each R_{r}, 1 ≤ r ≤ w, contains exactly one pair from P_{n}, hence we have a cyclic that is a sequential strategy. If each R_{i} contains around [n/2] pairs we shall rather speak of a parallel than of a GC strategy (or Jacobi-type process). The transformations (1.2) shall be referred to as a (parallel or single) step of a GC process.

If each rotation set R_{r} is somehow ordered, then R_{1}, ⋯, R_{w} represents an ordering of P_{n}. Thus, to each GC strategy one can associate more orderings. On the set of GC strategies one can define the three equivalence relations as above. Two GC strategies are equivalent (weakly-equivalent) if there exists a pair of associated orderings from O(P_{n}) which are equivalent (weakly-equivalent). strategies can be found in [8]. In particular, It has been proved in [8] that the row cyclic strategy and the modulus(GC) strategy are weakly equivalent. In [10] it has been shown that certain orderings associated with today’s most common parallel strategies are weakly equivalent to an ordering associated with the modulus strategy. This fact shows the importance of the class of GC strategies which are weakly equivalent to the modulus one.

In this paper we consider convergence of some norm-reducing GC Jacobitype methods. The convergence shall be measured by

∥ A ∥_{off}=∥ A − diag(a_{11}, …, a_{nn}) ∥= [ ∑_{j≠i^{i,j=1}}^{n} | a_{ij} |^{2}]^{1/2} .

Here ∥ · ∥ denots the Euclidean (Schur, Frobenius) matrix norm. The measure ∥ · ∥_{off} is called the off-norm or departure from the diagonal form. Later on we shall need

Theorem 1.1 Let A be a matrix of order n. Let A^{[1]} = A, A^{[2]}, … be defined by the rule

A^{[τ+1]} = U^{[τ]−1}A^{[τ]}U^{[τ]} + E^{[τ]}, τ ≥ 1,

with

U^{[τ]} = ∏_{(p,q)∈P iv(τ)} U_{pq}^{[τ]}, τ ≥ 1,

and let the generalized cyclic strategy be weakly equivalent to the modulus one. Let the conditions (i)—(v) hold.

(i) The sequence (A^{[τ]}, τ ≥ 1) is bounded;

(ii) lim_{τ→∞} ∥E^{[τ]}∥_{off} = 0;

(iii) U^{[τ]} = (u_{rs}^{[τ]}), τ ≥ 1 are unitary;

(iv) lim inf_{τ→∞} min_{1≤r≤n} | u_{rr}^{[τ]} |> 0;

(v) lim_{τ→∞} max_{(p,q)∈P iv(τ)}{| ã_{pq}^{[τ]} |^{2} + | ã_{qp}^{[τ]} |^{2}} = 0

where Ã^{[τ]} = U^{τ]−1}A^{[τ]}U^{[τ]} = (ã_{rs}^{[τ]}), τ ≥ 1. Then

lim_{τ→∞} ∥A^{[τ]}∥_{off} = 0.

Proof. The proof follows directly from Corollary 2.8 of [8].

Theorem 1.1. can be used for both the cyclic (when w=N) and parallel (when w ≈ n) Jacobi-type methods. The first (second) case shall be treated in Section 2 (Section 3).

2 The Methods of Eberlein

Here we shortly discuss the convergence properties of the three well-known sequential methods of Eberlein. These are Jacobi-type methods for diagonalizing general complex, symmetric complex and general real matrices (see [1],[2],[3],[4]). First we consider a modification of the method for general complex matrices.

Let A be a complex matrix of order n. The method generates the sequence A^{(1)} = A, A^{(2)}, … by the rule (1.1), where T_{k} = R_{k}S_{k} and R_{k}, S_{k} are nonsingular plane matrices defined by their pivot submatrices

R̂_{k} = [ \begin{matrix}cos x_{k} & −e^{iα_{k}} sin x_{k} \\ e^{iα_{k}} sin x_{k} & cos x_{k} \end{matrix} ] , Ŝ_{k} = [ \begin{matrix}cosh y_{k} & −ie^{iβ_{k}} sinh y_{k} \\ ie^{−iβ_{k}} sinh y_{k} & cosh y_{k} \end{matrix} ] ,

respectively. Since R_{k} is unitary, we can rewrite (1.1) in the form

A^{(k+1)} = S_{k}^{−1}Ã^{(k)}S_{k}, Ã^{(k)} = R_{k}^{∗}A^{(k)}R_{k}, k ≥ 1,  (2.1)

where, generally T^{∗} denotes the complex conjugate transpose of T. For k ≥ 1 we define

B^{(k)} = \frac{1}{2}[A^{(k)} + A^{(k)∗}] = (b_{rs}^{(k)})
C(Ã^{(k)}) = Ã^{(k)}Ã^{(k)∗} − Ã^{(k)∗}Ã^{(k)} = (c̃_{rs}^{(k)})

and set

A^{(k)} = (a_{rs}^{(k)}), Ã^{(k)} = (ã_{rs}^{(k)}).

Next we consider the tranformations involved at step k . For simplicity , we denote the pivot indices p_{k}, q_{k} by p, q. The parameters x_{k} and α_{k} are chosen to annihilate the pivot element b_{pq}^{(k)} of the Hermitian matrix B^{(k)}. The standard Jacobi formulas yield (see [15], [9])

α_{k} = arg(b_{pq}^{(k)}), tan 2x_{k} = \frac{2 | b_{pq}^{(k)} |}{b_{pp}^{(k)} − b_{qq}^{(k)}} , x_{k} ∈ [−\frac{π}{4} , \frac{π}{4} ] .  (2.2)

The parameters y_{k} and z_{k} are chosen to reduce the Euclidean norm of A^{(k)}, i.e. to increase Δ_{k}, where

Δ_{k} = ∥A^{(k)}∥^{2} − ∥A^{(k+1)}∥^{2} , k ≥ 1.

The transformation formulas are as follows (see [1])

a_{rs}^{k+1)} = a_{rs}^{(k)} if (r, s) and (p, q) are disjoint,
a_{pr}^{(k+1)} = ã_{rs}^{(k)} cosh y_{k} + ie^{iβ^{k}}ã_{qr}^{(k)} sinh y_{k}
a_{rp}^{(k+1)} = ã_{rp}^{(k)} cosh y_{k} + ie^{−iβ^{k}}ã_{rq}^{(k)} sinh y_{k}
a_{qr}^{(k+1)} = ã_{qr}^{(k)} cosh y_{k} − ie^{−iβ^{k}}ã_{pr}^{(k)} sinh y_{k}
a_{rq}^{(k+1)} = ã_{rq}^{(k)} cosh y_{k} − ie^{iβ^{k}}ã_{rp}^{(k)} sinh y_{k}
a_{pp}^{(k+1)} = \frac{1}{2} (ã_{pp}^{(k)} + ã_{qq}^{(k)} + D̃_{pq}^{(k)} cosh 2y_{k} + iξ̃_{pq}^{(k)} sinh 2y_{k}),
a_{qq}^{(k+1)} = \frac{1}{2} (ã_{pp}^{(k)} + ã_{qq}^{(k)} − D̃_{pq}^{(k)} cosh 2y_{k} − iξ̃_{pq}^{(k)} sinh 2y_{k}),
a_{pq}^{(k+1)} = \frac{1}{2}e^{iβ}(η̃_{pq}^{(k)} − iD̃_{pq}^{(k)} sinh 2y_{k} + ξ̃_{pq}^{(k)} cosh 2y_{k}),
a_{qp}^{(k+1)} = \frac{1}{2}e^{−iβ}(−η̃_{pq}^{(k)} − D̃_{pq}^{(k)} sinh 2y_{k} + ξ̃_{pq}^{(k)} cosh 2y_{k}),

where r ∉ {p, q} and

ξ̃_{pq}^{(k)} = (ã_{pq}^{(k)} + ã_{qp}^{(k)}) cos β_{k} − i(ã_{pq}^{(k)} − ã_{qp}^{(k)}) sin β_{k}
η̃_{pq}^{(k)} = (ã_{pq}^{(k)} − ã_{qp}^{(k)}) cos β_{k} − i(ã_{pq}^{(k)} + ã_{qp}^{(k)}) cos β_{k}
D̃_{pq}^{(k)} = ã_{pp}^{(k)} − ã_{qq}^{(k)}.

In [1] Eberlein proved that

Δ_{k} = G̃_{pq}^{(k)}(1 − cosh 2y_{k}) − H̃_{pq}^{(k)} sinh 2y_{k}

+ \frac{1}{2}(| D̃_{pq}^{(k)} |^{2} + | ξ̃_{pq}^{(k)} |^{2})(1 − cosh 4y_{k}) + Im(ξ̃_{pq}^{(k)} D̃_{pq}^{(k)∗}) sinh 4y_{k},

where

G̃_{pq}^{(k)} = ∑_{r≠p,q}(| ã_{pr}^{(k)} |^{2} + | ã_{rp}^{(k)} |^{2} + | ã_{qr}^{(k)} |^{2} + | ã_{rq}^{(a)} |^{2}),
H̃_{pq}^{(k)} = −Re(K̃_{pq}^{(k)}) sin β_{k} + Im(K̃_{pq}^{(k)}) cos β_{k},
K̃_{pq}^{(k)} = 2 ∑_{r≠p,q}(ã_{pr}^{(k)}ã_{qr}^{(k)∗} − ã_{rp}^{(k)∗}ã_{rq}^{(k)}).

Note that generally, z^{∗} denotes the complex conjugate of z. Also, Re(y) and Im(z) denote the real and the imaginary parts of z.

In [1] Eberlein has proved that the choice

\begin{matrix}tanh y_{k} & = & \frac{1}{2} \frac{2 Im(ξ̃_{pq}^{(k)}D̃_{pq}^{(k)∗}) − H̃_{pq}^{(k)}}{G̃_{pq}^{(k)} + 2(| ξ̃_{pq}^{(k)} |^{2} + | D̃_{pq}^{(k)} |^{2})}, \\ tan β_{k} & = & −\frac{Re(c̃_{pq}^{(k)})}{Im(c̃_{pq}^{(k)})}, \end{matrix} \}  (2.3)

implies

Δ_{k} = ∥A^{(k)}∥^{2} − ∥A^{(k+1)}∥^{2} = ∥Ã^{(k)}∥^{2} − ∥A^{(k+1)}∥^{2}
≥ \frac{1}{3} \frac{| c̃_{pq}^{(k)} |^{2}}{∥A^{(k)}∥^{2}} , k ≥ 1.

Since for k ≥ 1, ∥A^{(k)}∥ ≥ ∥A^{(k+1)}∥ ≥ 0, the sequence (∥A^{(k)}∥, k ≥ 1) is convergent. It implies (we return to notation p_{k}, q_{k}) that

c̃_{p_{k}q_{k}}^{(k)} → 0 as k → ∞.  (2.4)

The relation (2.4) plays an essential part in the proof of the following theorem.

Theorem 2.1 Let A be a matrix of order n and A^{(1)} = A, A^{(2)}, … be a sequence of matrices defined by the relations (2.1)–(2.3). If the pivot strategy is cyclic and weakly-equivalent to the row-cyclic one then the assertions I to III hold.

I C(A^{(k)}) → 0 as k → ∞.

II B^{(k)} → diag(Re λ_{1}, …, Re λ_{n}) as k → ∞ , where Re λ_{1}, … Re λ_{n} , is an ordering of the real parts of the eigenvalues of A.

III a_{rs}^{(k)} → 0 and a_{rs}^{(k)} → 0 as k → ∞, for every pair (r, s) satisfying Re λ_{r} ≠ Re λ_{s}.

Proof. The complete proof can be found in [11]. It is very similar to the proof of Theorem 2.1 of [5]. However, it can be also deduced from Theorem 4.3 in this paper, by assuming w = N, i.e. a cyclic strategy weakly equivalent to the modulus (cyclic) strategy.

The choice α_{k} = β_{k} = 0 (α_{k} = π, β_{k} = π/2) yields the known method of Eberlein for complex symmetric (general real) matrices. Hence, Theorem 1.2 holds for these methods as well.

To ensure that A^{(k)} always tends to a diagonal matrix, Eberlein [2] has proposed a more sophisticated choice for α_{k} and x_{k}. For the choice in question, however, the above considerations can ensure (without further investigation) only the convergence to normality, i.e., the assertion I.

3 The Parallelized Algorithm

In order to parallelize the methods of Eberlein we must modify the algorithm to cope with parallel processing. In addition we modify it in such a way that the convergence proof becomes feasible. Again we concentrate to the case of a general complex matrix.

The matrix T^{[τ]} of the relation (1.3), is sought in the form

T^{[τ]} = R^{[τ]}M^{[τ]}S^{[τ]}, τ ≥ 1,  (3.1)

where R^{[τ]}, M^{[τ]} and S^{[τ]} are defined as follows:

(a)  R^{[τ]} = ∏_{(p,q)∈P iv(τ)} R_{pq}^{[τ]},

where each R_{pq}^{[τ]} is a unitary plane matrix defined by its (p,q)-restriction

R̂_{pq}^{[τ]} = [ \begin{matrix}cos x_{pq}^{[τ]} & −e^{iα_{pq}^{[τ]}} sin x_{pq}^{[τ]} \\ e^{−iα_{pq}^{[τ]}} sin x_{pq}^{[τ]} & cos x_{pq}^{[τ]} \end{matrix} ] .  (3.2)

(b)  M^{[τ]} = ∏_{(p,q)∈P iv(τ)} M_{pq}^{[τ]},

where each M_{pq}^{[τ]} is a unitary diagonal plane matrix defined by

M̂_{pq}^{[τ]} = [ \begin{matrix}σ_{pq}^{[τ]} \\ & 1 \end{matrix} ] .

(c)  S^{[τ]} = ∏_{(p,q)∈P iv(τ)} S_{pq}^{[τ]},

where each S_{pq}^{[τ]} is nonsingular plane matrix defined by

Ŝ_{pq}^{[τ]} = [ \begin{matrix}cosh y^{[τ]} & −ie^{iβ^{[τ]}} sinh y^{[τ]} \\ ie^{−iβ^{[τ]}} sinh y^{[τ]} & cosh y^{[τ]} \end{matrix} ] .

Note that Ŝ_{pq}^{[τ]} does not depend on (p, q) ∈ P iv(τ). The idea for this choice is due to Sameh [12]. This choice does not guarantee the maximal norm-reduction at each parallel step, but it facilitates the convergence considerations.

Using the factorization (3.1), we can rewrite the relation (1.2) in the form

A^{[τ+1]} = S^{[τ]−1}Ã^{[τ]}S^{[τ]},
Ã^{[τ]} = M^{[τ]∗}A^{[τ]′}A^{[tau]′}M^{[τ]},
A^{[τ]′} = R^{[τ]∗}A^{[τ]}R^{[τ]}, τ ≥ 1.

To define the algorithm we fix τ and omit the superscript τ.

The parameters α_{pq} and x_{pq} are chosen to annihilate the pivot elements b_{pq} of B^{[τ]} = (A^{[τ]} + A^{[τ]∗})/2 = (b_{rs}). Thus

α_{pq} = arg(b_{pq}), tan 2x_{pq} = \frac{2 | b_{pq} |}{b_{pp} − b_{qq}} , x ∈ [−\frac{π}{4} , \frac{π}{4} ]  (3.3)

holds for (p, q) ∈ P iv(τ).

Let C(A^{[τ]′}) = (c′_{rs}), C(Ã^{[τ]}) = (c̃_{rs}) where generally C(X) = XX^{∗}−X^{∗}X is the commutator of X.

The elements σ_{pq} of the matrices M̂_{pq}^{[τ]} are chosen to meet the requirement

Re(c̃_{pq}) ≥ 0, Im(c̃_{pq}) ≥ 0, (p, q) ∈ P iv(τ).  (3.4)

Since C(Ã^{[τ]}) = M^{[τ]∗}C(A^{[τ]′})M^{[τ]} we obtain

σ_{pq} = \{ \begin{matrix}− i sign(Im(cpq^{′})) & if Re(c′_{pq}) Im(c′_{pq}) < 0 \\ sign(Re(c′_{pq}) + Im(c′_{pq})) & otherwise \end{matrix}  (3.5)

for (p, q) ∈ P iv(τ). Here

sign(x) = \{ \begin{matrix}1 & if x ≥ 0 \\ −1 & otherwise. \end{matrix}

Let us consider the transformation Ã^{[τ]} → S^{[τ]−1}Ã^{[τ]}S^{[τ]} = A^{[τ+1]}. To this end let L_{τ} be a set of indices involved at time τ, i.e.,

L_{τ} = {i; (i, j) ∈ P iv(τ) or (j, i) ∈ P iv(τ) for some j}.

Obviously, L_{τ} ⊆ {1, 2, , ⋯, n} and the inclusion can be proper. To express the elements of A^{[τ+1]} in terms of the elements of Ã^{[τ]} we note that some elements of Ã^{[τ]} are transformed twice, some once, and some may remain unchanged. Let (p, q), (r, s) ∈ P iv(τ) and j, k ∉ L_{τ}. Then a straightforward calculation yields

a_{jk}^{[τ+1]} = ã_{jk} ( = ã_{jk}^{[τ]})
a_{pk}^{[τ+1]} = ã_{pk} cosh y + i e^{iβ}ã_{qk} sinh y
a_{kp}^{[τ+1]} = ã_{kp} cosh y + i e^{−iβ}ã_{kq} sinh y
a_{qk}^{[τ+1]} = ã_{qk} cosh y − i e^{−iβ}ã_{pk} sinh y
a_{kq}^{[τ+1]} = ã_{kq} cosh y − i e^{iβ}ã_{kp} sinh y
a_{pr}^{[τ+1]} = \frac{1}{2}(ã_{pr} + ã_{qs} + D̃_{pq,rs} cosh 2y + iξ̃_{pq,rs} sinh 2y)  (3.6)

a_{qs}^{[τ+1]} = \frac{1}{2}(ã_{pr} + ã_{qs} − D̃_{pq,rs} cosh 2y − iξ̃_{pq,rs} sinh 2y)
a_{ps}^{[τ+1]} = \frac{1}{2}e^{iβ}(η̃_{pq,rs} − iD̃_{pq,rs} sinh 2y + ξ̃_{pq,rs} cosh 2y)
a_{qr}^{[τ+1]} = \frac{1}{2}e^{−iβ}(−η̃_{pq,rs} − iD̃_{pq,rs} sinh 2y + ξ̃_{pq,rs} cosh 2y)

where

ξ̃_{pq,rs} = (ã_{ps} + ã_{qr}) cos β − i(ã_{ps} − ã_{qr}) sin β
η̃_{pq,rs} = (ã_{ps} − ã_{qr}) cos β − i(ã_{ps} + ã_{qr}) sin β  (3.7)
D̃_{pq,rs} = ã_{pr} − ã_{qs}.

The formulas for a_{rp}^{[τ+1]}, a_{sq}^{[τ+1]}, … (a_{rk}^{[τ+1]}, a_{kr}^{[τ+1]}, …) can be obtained from the given ones by interchanging (replacing) the indices p, q by r, s, respectively. Note that the case i = p and j = q is contained in the relations (3.6) and (3.7).

A straightforward calculation (the details can be found in [11]) yields

Δ = Δ^{[τ]} = ∥A^{[τ]}∥^{2} − ∥A^{[τ+1]}∥^{2}
= G̃(1 − cosh 2y) − H̃ sinh 2y
+ \frac{1}{2}ρ̃_{1}(1 − cosh 4y) + ρ̃_{2} sinh 4y,  (3.8)

where

G̃ = ∑_{(p,q)} ∑_{k∉L_{τ}}(|ã_{pk}|^{2} + |ã_{qk}|^{2} + |ã_{kp}|^{2} + |ã_{kq}|^{2})
K̃ = 2 ∑_{(p,q)} ∑_{k∉L_{τ}}(ã_{pk} ã_{qk}^{∗} − ã_{kp}^{∗}ã_{kq})
H̃ = −Re(K̃) sin β + Im(K̃) cos β  (3.9)
ρ̃_{1} = ∑_{(p,q)} ∑_{(r,s)}(|D̃_{pq,rs}|^{2} + |ξ̃_{pq,rs}|^{2})
ρ̃_{2} = ∑_{(p,q)} ∑_{(r,s)} Im(ξ̃_{pq,rs} D̃_{pq,rs}^{∗})

In the relation (3.9) and later on ∑_{(p,q)}, ∑_{(r,s)}, ∑_{k∉L_{τ}} denote ∑_{(p,q)∈P iv(τ)},

∑_{(r,s)∈P iv(τ)}, ∑n ; k∉L_{τ}^{k=1} , respectively.

The relations (3.8) and (3.9) show that Δ depends only on y and β. Our aim is to define y and β so that Δ could be bounded from below by a suitable nonnegative quantity. The choice is

tanh y = \frac{ρ̃_{2} − H̃/2}{G̃ + 2ρ̃_{1}},  (3.10)
tanh β = −\frac{Re(c̃_{τ})}{Im(c̃_{τ})}, sin β ≥ 0  (3.11)

where

c̃_{τ} = ∑_{(p,q)∈P iv(τ)} c̃_{pq}.  (3.12)

In particular, if Im(c̃_{τ}) = 0 we assume (even when c̃_{τ} = 0), β = \frac{π}{2}. The relations (3.11), (3.4) and (4.2) imply

ρ̃_{2} − H̃/2 = |c̃_{τ}|,  (3.13)

yielding the simpler form for tanh y.

The relations (3.1)—(3.3), (3.5), (3.10)— (3.12) together with the definitions (3.7) and (3.9) define our norm-reducing algorithm. This algorithm generalizes the algorithm of Section 2 since for the case w = N the two algorithms are almost identical.

Remark 3.1 A similar algorithm can be obtained by assuming M̂_{pq}^{[τ]} = diag(1, σ_{pq}^{[τ]}). Our choice for α_{pq} and x_{pq} is the same as that for the sequential method of Section 2. A more sophisticated choice, analogous to that of Eberlein [2] could have been assumed, but then our convergence result would be weaker. A similar argument could be stated for the choice of matrices Ŝ_{pq}^{[τ]} (cf. [12]).

It is easily seen that the choice α_{pq} = β_{pq} = 0 (α_{pq} = π, β_{pq} = π/2) for all (p, q) ∈ P iv(τ) makes the above algorithm suitable for complex symmetric (general real) matrices.

4 Convergence

Here we prove convergence properties of a GC Jacobi-type norm-reducing method defined by the algorithm of Section 3 and by a pivot strategy which is weakly equivalent to the modulus one. In the sequel A is a general matrix of order n and A^{[1]} = A, A^{[2]}, … matrices defined by the recursion (1.2). First we prove some auxiliary results.

Lemma 4.1 Let y, β, c̃_{τ} and G̃, ρ̃_{1} be defined by the relations (3.10), (3.11), (3.12) and (3.9), respectively. Then Δ in (3.8) satisfies

Δ ≥ \frac{4}{3} \frac{|c̃_{τ}|^{2}}{G̃ + 2ρ̃_{1}} .  (4.1)

Proof. First we prove the relation

ρ̃_{2} − H̃/2 = sin β Re(c̃_{τ}) − cos β Im(c̃_{τ}).  (4.2)

Let

c̃_{τ} = \frac{1}{2}K̃ + χ̃  (4.3)

where

χ̃ = ∑_{(p,q)} ∑_{k∈L_{τ}}(ã_{pk}ã_{qk}^{∗} − ã_{kp}^{∗}ã_{kq}).

From the definition of L_{τ} it follows that

χ̃ = ∑_{(p,q)} ∑_{(rs)} χ̃_{pq,rs},  (4.4)

where

χ̃_{pq,rs} = ã_{pr}ã_{qr}^{∗} − ã_{rp}^{∗}ã_{rq} + ã_{ps}ã_{qs}^{∗} − ã_{sp}^{∗}ã_{sq}.  (4.5)

Let

ω̃_{pq,rs} = ã_{qr}^{∗}D̃_{pq,rs} − ã_{ps}D̃_{pq,rs}^{∗},  (4.6)

where D̃_{pq,rs}^{∗} is defined by the relation (3.7). By a simple calculation we obtain

χ̃_{pq,rs} + χ̃_{rs,pq} = ω̃_{pq,rs} + ω̃_{rs,pq}, (p, q), (r, s) ∈ P iv(τ).  (4.7)

The relations (4.4)-(4.7) imply

χ̃ = \frac{1}{2} ∑_{(p,q)} ∑_{(r,s)}(χ̃_{pq,rs} + χ̃_{rs,pq})
= \frac{1}{2} ∑_{(p,q)} ∑_{(r,s)}(ω̃_{pq,rs} + ω̃_{rs,pq})
= \frac{1}{2} ∑_{(p,q)} ∑_{(r,s)} ω̃_{pq,rs}.  (4.8)

From the relations (4.6) and (3.7) we obtain

ω̃_{pq,rs} = −Re([ã_{ps} − ã_{qr}]D̃_{pq,rs}^{∗}) − i Im([ã_{ps} + ã_{qr}]D̃_{pq,rs}^{∗}).  (4.9)

Using the relations (4.9) and (3.7) we obtain

sin β Re(ω̃_{pq,rs}) − cos β Im(ω̃_{pq,rs}) = Im(ξ̃_{pq,rs}D̃_{pq,rs}^{∗}).  (4.10)

The relations (3.9), (4.10) and (4.8) yield

ρ̃_{2} = sin β Re(χ̃) − cos β Im(χ̃).

The obtained equality, together with the relations (4.3) and (3.9) imply the relation (4.2).

The rest of the proof is quite similar to the proof of Lemma 1 of [3], so we discuss it very briefly. Setting

Θ = tanh y, ch = cosh y, sh = sinh y,  (4.11)

one obtains

Δ = 2 (2 ρ̃_{2} − H̃) sh ch − 2 G̃ sh^{2} − 4 ρ̃_{1} (sh^{4} + sh^{2}) + 8 ρ̃_{2} sh^{3} ch. (4.12)

Since sh ch = Θ ch^{2}, sh^{2} = Θ^{2} ch^{2} the relations (3.10) and (4.12) imply

Δ = 2 ch^{2} \frac{|c̃_{τ}|^{2}}{G̃ + 2ρ̃_{1}} ρ  (4.13)

where

ρ = 1 − \frac{2 ρ̃_{1} sh^{2} − 4 ρ̃_{2} sh ch}{G̃ + 2ρ̃_{1}}.

Using the corresponding part of the proof of [3], one obtains

ρ ≥ \frac{2}{3}.  (4.14)

This completes the proof of Lemma 4.1, since the inequality (4.1) follows from the relations (4.13), (4.14) and the inequality ch^{2} ≥ 1.

Lemma 4.2 . If y, β and c̃_{τ} are defined by the relations (3.10), (3.11) and (3.12), respectively, then

| a_{jk}^{[τ+1]} − ã_{jk}^{[τ]} |≤| c̃_{τ} |^{1/2}, 1 ≤ j, k ≤ m.  (4.15)

Proof. The proof is similar to that of Veselić [14]. For the sake of simplicity we omit the superscript τ and write a′′_{st} for a_{st}^{[τ+1]}.

Using the Cauchy-Schwarz inequality and the definitions from the relation (3.9), we have

| H̃ |≤| K̃ |≤ ∑_{(p,q)} ∑_{k∉L_{τ}}(2 | ã_{pk} || ã_{qk} | +2 | ã_{kp} || ã_{kq} |) ≤ G̃

and

2 | ρ̃_{2} |≤ ρ̃_{1}.

Thus, from the definition (3.10) of y we conclude that | tanh y| ≤ 1/2. The relation (4.11) and the estimates from [14] imply

Θ^{2} ≤ Θ/2, ch^{2} ≤ 4/3,

hence

\begin{matrix}(ch − 1)^{2} + sh^{2} ≤ ch sh^{2} = ch^{3} Θ^{2} ≤| Θ |, \\ sh^{2}(sh^{2} + ch^{2}) = ch^{4}Θ^{2}(1 + Θ^{2}) ≤ \frac{16}{9}(1 + \frac{1}{4})\frac{| Θ |}{2} ≤ \frac{10}{9} | Θ | . \end{matrix} \} (4.16)

For (p, q), (r, s) ∈ P iv(τ) and k ∉ L_{τ} we have

\begin{matrix}| ã_{pk} |^{2} + | ã_{qk} |^{2} + | ã_{kp} |^{2} + | ã_{kq} |^{2}≤ G̃ \\ | D̃_{pq,rs} |^{2} + | ξ̃_{pq,rs} |^{2}≤ ρ_{1}. \end{matrix} \}  (4.17)

Using the relations (3.6), (3.9), (4.16), (4.17) and the Cauchy-Schwarz inequality we obtain

| a′′_{pk} − ã_{pk} | ≤ | ã_{pk} || ch − 1 | + | ã_{qk} || sh |
≤ [(ch − 1)^{2} + sh^{2}]^{1/2}[| ã_{pk} |^{2} + | ã_{qk} |^{2}]^{1/2}
≤ [|Θ|G̃]^{1/2} ≤| c̃_{τ} |^{1/2} .

The last inequality follows directly from the relations (3.10) and (3.13). A similar proof holds for the estimates involving ã_{qk}, ã_{kp} and ã_{kq}, where (p, q) ∈ P iv(τ), k ∉ L_{τ}.

Using the relations (3.6), (3.7), (4.16), (4.17), (3.10) and (3.13) we obtain

| a′′_{pr} − ã_{pr} | ≤ | D̃_{pq,rs} | sh^{2}+ | ξ̃_{pq,rs} |^{2} | ch sh |
≤ [sh^{2}(sh^{2} + ch^{2})]^{1/2}[|D̃_{pq,rs}|^{2} + |ξ̃_{pq}|^{2}]^{1/2}
≤ [\frac{10}{9}|Θ|ρ̃_{1}]^{1/2} ≤ [\frac{10}{18}|c̃_{τ}|]^{1/2} ≤| c̃_{τ} |^{1/2},

where (p, q), (r, s) ∈ P iv(τ). In a similar way we prove the estimates involving ã_{ps} ,ã_{qr} and ã_{qs}.

The following result is a proper generalization of Theorem 1.2.

Theorem 4.3 Let A be a matrix of order n and let A^{[1]} = A, A^{[2]}, … be the sequence of matrices defined by the relations (1.2), (3.1), (3.3), (3.5), (3.10) and (3.11). If the GC strategy is weakly equivalent to the modulus one, then as τ → ∞.

I C(A^{[τ]}) → 0,

II A^{[τ]} + A^{[τ]∗} → 2 diag(Reλ_{1}, ⋯, Reλ_{n}), where Reλ_{1}, ⋯, Reλ_{n} is an ordering of the real parts of the eigenvalues of A,

III a_{rs}^{[τ]} → 0 and a_{sr}^{[τ]} → 0, provided that Reλ_{r} ≠ Reλ_{s}.

Proof. The relation (1.2) can be written as

A^{[τ+1]} = U^{[τ]−1}A^{[τ]}U^{[τ]} + E^{[τ]}, τ ≥ 1  (4.18)

with

U^{[τ]} = R^{[τ]}M^{[τ]}, E^{[τ]} = A^{[τ+1]} − Ã^{[τ]}, τ ≥ 1.

By Lemma 4.2 we have

∥E^{[τ]}∥^{2} = ∑_{r,s=1}^{n} | a_{rs}^{[τ+1]} − ã_{rs}^{[τ]}]^{2} ≤ n^{2} | c̃_{τ} |, τ ≥ 1.  (4.19)

From Lemma 4.1 we conclude that (∥A^{[τ]}∥, τ ≥ 1) is a nonincreasing sequence. Since it is bounded below by 0 it is convergent. The relation (4.1) implies | c̃_{τ} |→ 0 as τ → ∞. Hence, from the relation (4.19) we obtain

∥E^{[τ]}∥ → 0 as τ → ∞.  (4.20)

Since U^{[τ]} are unitary matrices, the relations (4.18) and (4.20) imply that for τ ≥ 1

\begin{aligned}B^{[τ+1]} & = & U^{[τ]−1}B^{[τ]}U^{[τ]} + F^{[τ]} \\ C(A^{[τ+1]}) & = & U^{[τ]−1}C(A^{[τ]})U^{[τ]} + W^{[τ]} \end{aligned}  (4.21)

holds with

∥F^{[τ]}∥ ≤ ∥E^{[τ]}∥ → 0 as τ → ∞
∥W^{[τ]}∥ ≤ 4∥A^{[τ]}∥∥E^{[τ]}∥ + 2∥E^{[τ]}∥^{2}  (4.22)
≤ 4∥A∥∥E^{[τ]}∥ + 2∥E^{[τ]}∥^{2} → 0 as τ → ∞.

Next we apply Theorem 1.1 to the sequences (B^{[τ]}, τ ≤ 1) and (C(A^{[τ]}), τ ≥ 1). In order to obtain

∥B^{[τ]}∥_{off} → 0 as τ → ∞  (4.23)

and

∥C(A^{[τ]})∥_{off} → 0 as τ → ∞,  (4.24)

we must check the conditions (i) to (v) for each sequence. The conditions (i) and (iii) are trivial. The condition (ii) is implied by the relation (4.22) whereas the condition (iv) holds since

u_{kk}^{[τ]} = 1 if k ∉ L_{τ}
| u_{pp}^{[τ]} | = | u_{qq}^{[τ]} | = | cos x_{pq}^{[τ]} | ≥ \frac{\sqrt{2}}{2} if (p, q) ∈ P iv(τ)

holds for U^{[τ]} = (u_{rs}^{[τ]}). Finally, the condition (v) is implied by Lemma 4.2 and the choice of angles which implies

(U^{[τ]−1} B^{[τ]}U^{[τ]})_{pq} = 0 and | (U^{[τ]−1} C(A^{[τ]}) U^{[τ]})_{pq} |≤| c̃_{τ} | for all (p, q) ∈ P iv(τ).

In conclusion, the relations (4.23) and (4.24) hold.

Let us now prove the assertion I. It remains to prove that diag(c_{11}^{[τ]}, ⋯, c_{nn}^{[τ]}) → O as τ → ∞, where C(A^{[τ]}) = (c_{rs}^{[τ]}). Setting

A^{[τ]} = B^{[τ]} + G^{[τ]}, τ ≥ 1,

we have B^{[τ]∗} = B^{[τ]}, G^{[τ]∗} = −G^{[τ]} and consequently

C(A^{[τ]}) = 2(G^{[τ]}B^{[τ]} − B^{[τ]}G^{[τ]}), τ ≥ 1.  (4.25)

Hence

max_{1≤r≤n} | c_{rr}^{[τ]} |≤ 2∥G^{[τ]}∥ ∥B^{[τ]}∥_{off} ≤ 2∥A∥ ∥B^{[τ]}∥_{off}, τ ≥ 1.

The relation (4.23) shows that c_{rr}^{[τ]} → 0 as τ → ∞ for all 1 ≤ r ≤ n. To prove the assertion II it remains to show that diag(b_{11}^{[τ]}, …, b_{nn}^{[τ]}) → diag(Reλ_{1}, …, Reλ_{n}) as τ → ∞. The proof is almost identical to the corresponding part of the proof of Theorem 1.1 of [5]. In [5] it is shown that

∑_{r=1}^{n} |b_{rr}^{[τ]} − Reλ_{r}|^{2} ≤ 2∥B^{[τ]}∥_{off}^{2} + \sqrt{\frac{n^{3} − n}{3}} ∥C(A^{[τ]})∥,  (4.26)

holds for an ordering of λ_{1}, …, λ_{n}. By the assertion I and by the relation (4.23) the right-hand side of the inequality (4.26) tends to zero. Hence the sequence of vectors ((b_{11}^{[τ]}, …, b_{nn}^{[τ]})^{T}, τ ≥ 1) has only finitely many accumulation points and remains to prove that for large τ the changes in each b_{rr}^{[τ]} are arbitrarily small.

Let (p, q) ∈ P iv(τ), τ ≥ 1. The choice of angles x_{pq}^{[τ]}, α_{pq}^{[τ]} and the first equation in the relation (4.21) give

\begin{matrix}b_{pp}^{[τ+1]} = b_{pp}^{[τ]} − tan x_{pq}^{[τ]} | b_{pq}^{[τ]} | +f_{pp}^{[τ]} \\ b_{qq}^{[τ+1]} = b_{qq}^{[τ]} + tan x_{pq}^{[τ]} | b_{pq}^{[τ]} | +f_{qq}^{[τ]} \end{matrix} \}  (4.27)

where F^{[τ]} = (f_{rs}^{[τ]}). Since | tan x_{pq}^{[τ]} |≤ 1 , the relations (4.22), (4.23) and (4.24) show that

| b_{rr}^{[τ+1]} − b_{rr}^{[τ]} |→ 0 as τ → ∞

holds for r ∈ L_{τ}. For r ∉ L_{τ} we have b_{rr}^{[τ+1]} = b_{r}^{[τ]}, hence (b_{11}^{[τ]}, ⋯, b_{nn}^{[τ]})^{T} has only one accumulation point. This completes the proof of II.

To prove the assertion III we recall the relations (4.25) and (4.23). They imply

0 = lim_{τ→∞} c_{rs}^{[τ]} = 2 lim_{τ→∞}(g_{rs}^{[τ]}b_{ss}^{[τ]} − b_{rr}^{[τ]}g_{rs}^{[τ]})
= 2 (Reλ_{s} − Reλ_{r}) lim_{τ→∞} g_{rs}^{[τ]}, 1 ≤ r, s ≤ n.

If Reλ_{s} ≠ Reλ_{r}, then g_{rs}^{[τ]} → 0 as τ → ∞. Since b_{rs}^{[τ]} → 0 as τ → ∞ because of the assertion II, we have

a_{rs}^{[τ]} = b_{rs}^{[τ]} + g_{rs}^{[τ]} → 0,
a_{rs}^{[τ]} = b_{rs}^{[τ] ∗} − g_{rs}^{[τ] ∗} → 0

as τ → ∞. This proves assertion III and Theorem 4.3.

The convergence results stated by Theorem 4.3 concern the diagonalization method for general complex matrices. This result can be used in connecction with the GC Jacobi-type methods for complex- symmetric and general real matrices.

In the first case the appropriate choice is α_{pq}^{[τ]} = 0 for (p, q) ∈ P iv(τ) and β^{[τ]} = 0, τ ≥ 1. Here the assertion I of Theorem 4.3 holds for all x_{pq}^{[τ]}, (p, q) ∈ P iv(τ) provided that x_{pq}^{[τ]} is in a closed interval interior to (−\frac{π}{2}, \frac{π}{2}) or (\frac{π}{2}, \frac{3}{2}π). If however, x_{pq}^{[τ]} is chosen as indicated by the relation (3.3) then the assertions II and III of Theorem 4.3 also hold.

In the second case the appropriate choice is α_{pq}^{[τ]} = π for (p, q) ∈ P iv(τ) and β^{[τ]} = \frac{π}{2}, τ ≥ 1. In this case Theorem 4.3 can be extended by the following assertion

(iv) If Reλ_{r} = Reλ_{s} for a fixed pair r ≠ s and Reλ_{t} ≠ Reλ_{s} for all t ≠ r, s, then a_{rs}^{[τ]} → Imλ_{r}, a_{sr}^{[τ]} → −Imλ_{s} as τ → ∞. The proof is identical to that in [5].

References

[1] Eberlein P. J.: A Jacobi method for automatic computation of eigenvalues and eigenvectors of an arbitrary matrix. Siam J. 10 (1962), 74-88.

[2] Eberlein P. J.: Solution to the complex eigenproblem by a norm- reducing Jacobi-type method. Numer. Math. 14 (1970), 232-245.

[3] Eberlein P. J.: On the diagonalization of complex symmetric matrices. J. Inst. Math. Applics. 7 (1971), 337-383.

[4] Eberlein P. J. and Boothroyd J.: Solution to the eigenproblem by a norm-reducing Jacobi-type method. Numer. Math. 11 (1968), 1-12.

[5] Hari V.: On the global convergence of Eberlein method for real matrices. Numer. Math. 39 (1982), 361-369.

[6] Hari V.: On the convergence of cyclic Jacobi-like processes.

Linear Algebra and Its Appl. 81 (1986), 105-127.

[7] Hari V. and Veselić K.: On Jacobi methods for singular value decompositions. SIAM J. Sci. Stat. Comput. Vol.8, No.5 (1987).

[8] Hari V.: On the convergence of certain parallel Jacobi methods. Unpublished paper.

[9] Henrici P.: On the speed of convergence cyclic and quasi-cyclic Jacobi methods for computing eigenvalues of Hermitian matrices. J. Ass. comp. Mach. 6 (1958) 144—162.

[10] Luk F. and Park H.: On the equivalence and convergence of parallel Jacobi SVD algorithms. IEEE Computer (1987).

[11] Pupovci D.: The convergence of parallel norm-reducing methods. M.S. Thesis, University of Zagreb 1989. (Croatian language).

[12] Sameh A.H.: On Jacobi and Jacobi-like algorithms for parallel computer. Math. Comp. 25 (1971), 579-590.

[13] Shroff G. and Schreiber R.: On the convergence of the cyclic Jacobi method for parallel block orderings. SIAM Journal on Matrix Analysis and Applications 10 (1989) 326—346.

[14] Veselić K.: A convergent Jacobi method for solving the eigenproblem of arbitrary matrices. Numer. Math. 25 (1976), 179-184.

[15] Voevodin, V. V.: Cislennye metody linejnoj algebry. Nauka, Moscow 1966.

O KONVERGENCIJI PARALELIZIRANIH METODA OD P. EBERLEIN

(Dukagjin Pupovci, Priština, Vjeran Hari, Zagreb)

S A D R Ž A J

Dobro poznate metode od Eberlein za dijagonalizaciju opće kompleksne, opće realne i kompleksne simetrične matrice su modificirane za rad na paralelnom računalu. Konvergencija je dokazana za sve pivotne strategije slabo ekvivalentne s modularnom strategijom. Rezultati su prilično slični poznatim rezultatima za sekvencijalne metode pod serijalnom strategijom.