CONVERGENCE OF A BLOCK-ORIENTED QUASI-CYCLIC JACOBI METHOD

VJERAN HARI^{∗}

Abstract. This paper proves the global convergence of a block-oriented, quasi-cyclic Jacobi method for symmetric matrices. The result applies to the new fast one-sided Jacobi method, proposed by Drmač and Veselić, for computing the singular value decomposition. There is no restriction on the matrix block-partition which defines the pivot strategy.

Key words. eigenvalues, Jacobi method, global convergence.

AMS subject classification. 65F15

1. Introduction. Recently, Drmač and Veselić [5, 6] have proposed an improved modification of the one-sided Jacobi method for computing the singular value decomposition (SVD) of rectangular matrices. It is fast (somewhat faster than QR and somewhat slower than Divide and Conquer (DC), see [6]) and relatively accurate (what cannot be said about QR and DC, see [1]). It also requires less memory work space and applies to a wider class of matrices (the matrix elements can vary in a wider range of magnitudes) than its competitors. The modified Jacobi first prepares the initial matrix for the iteration by applying to it one or two QR factorizations (cf. [18, 4, 5]). In the iterative part, many ideas from [3] have been implemented. In addition, to better exploit the computer resources, like the cache memory, it uses a new block-oriented, quasi-cyclic pivot strategy. This strategy mimics the blas blocking, thus exploiting contiguous memory benefits. It also takes into account the fact that after QR factorization, the larger elements lie typically in the vicinity of the diagonal, so more work has to be done within the diagonal blocks.

What is still lacking, is the global and the asymptotic convergence proof of their modification. The latter is less critical, since it is well known that Jacobi methods are quadratically convergent per sweep under usual cyclic strategies (see [19, 11]), and therefore, the quasicyclic methods should be (at least, see [16]) quadratically convergent per quasi-sweep.

The aim of this paper is to fill the missing gap, i.e. to prove the global convergence of the Jacobi method, defined by the pivot strategy proposed in [6]. The proof presented here covers the main algorithm from [6, Algorithm 1, case k = 1]. The other cases (k = 0 is trivial and the case k = 2 is even more complicated), can be proved by the same technique.

Note that the global convergence of a one-sided SVD Jacobi method for the matrix G actually means the global convergence of the corresponding two-sided Jacobi method for the non-negative definite Gram matrix G^{T} G. For this reason, we consider here the two-sided Jacobi method for general symmetric matrices, under the special quasi-cyclic pivot strategy which has been used in [6].

For any quadratic matrix X = (x_{ij}), the function Off(X) = ∥X − diag(X)∥_{F}, where diag(X) is the diagonal part of X and ∥ · ∥_{F} is the Frobenius norm, is referred to as departure from the diagonal form of X. Then, for any symmetric A, a useful measure of almost diagonality is

S(A) = Off(A)/\sqrt{2} = \sqrt{∑_{i=1}^{n−1} ∑_{j=i+1}^{n}(a_{ij})^{2}}.

In [14] Mascarenhas has proved that the diagonal elements of the iterated symmetric matrix A^{(k)}, obtained by the Jacobi method under any pivot strategy, converge. Therefore, it is

∗Department of Mathematics, University of Zagreb, Croatia

sufficient to prove that for any initial symmetric matrix A, S(A^{(k)}) → 0 as k → ∞. Actually, we shall prove that under the pivot strategy used in [6],

S^{2}(A^{(M)}) ≤ t_{n}S^{2}(A), 0 ≤ t_{n} < 1.  (1.1)

Here A^{(M)} is obtained from A after one quasi-sweep and t_{n} depends just on n. This is sufficient for the proof since the sequence S(A^{(k)}) is non-increasing.

The paper is divided into three sections. In Section 2 we introduce notation, the quasicyclic strategy and we formulate the main theorem. In Section 3 we prove the theorem.

2. The Quasi-cyclic Jacobi Method J_{M}. Although, the method and the proof can be considered for complex Hermitian matrices, for simplicity we restrict our considerations to real symmetric matrices.

2.1. Simple Symmetric Quasi-Cyclic Jacobi Methods. A (two-sided) Jacobi method for diagonalizing a symmetric n × n matrix A performs a sequence of similarity transformations

A^{(k+1)} = [R^{(k)}]^{T} A^{(k)}R^{(k)}, V^{(k+1)} = V^{(k)}R^{(k)} k ≥ 0 ,  (2.1)

where A^{(0)} = A, V^{(0)} = I_{n} and R^{(0)}, R^{(1)}, … are plane rotations. For each k, R^{(k)} is defined by a pair of indices (p, q) = (p(k), q(k)) called pivot pair and by four essential elements R_{pp}^{(k)} = R_{qq}^{(k)} = cos ϕ_{k}, R_{pq}^{(k)} = −R_{qp}^{(k)} = sin ϕ_{k}. All other elements of R^{(k)} are as in the identity matrix I_{n}. The process (2.1) is defined by a rule for computing the elements of R^{(k)} and by a way of selecting pivot pairs (pivot strategy). We assume the standard angle choice

tan 2ϕ_{k} = \frac{2a_{pq}^{(k)}}{a_{qq}^{(k)} − a_{pp}^{(k)}} , ϕ_{k} ∈ [\frac{−π}{4} , \frac{π}{4} ] ,  (2.2)

which makes the pivot element a_{pq}^{(k)} zero, i.e. a_{p(k)q(k)}^{(k+1)} = 0, k ≥ 0 holds. Consequently, we have

S^{2}(A^{(k+1)}) = S^{2}(A^{(k)}) − (a_{p(k)q(k)}^{(k)})^{2}, k ≥ 0

and lim_{k→∞} a_{p(k)q(k)}^{(k)} = 0. Here we have assumed A^{(k)} = (a_{ij}^{(k)}).

If A is 1 × 1 matrix we set S(A) = 0 and if A is 2 × 2 the process is completed for k = 1 since S(A^{(1)}) = 0. So, we assume n ≥ 3.

Let N = n(n − 1)/2, P_{n} = {(i, j) : 1 ≤ i < j ≤ n} and N_{0} = {0, 1, 2, …}. Each pivot strategy can be identified with a function I from N_{0} to P_{n}, defined by I(k) = (p(k), q(k)), k ≥ 0. If I is periodic, then I is called a periodic strategy. Let I be a periodic strategy with period M. If {I(k) : 0 ≤ k ≤ M − 1} = P_{n} and M > N (M = N), then I is called a quasi-cyclic (cyclic) strategy.

Let S be a subset of P_{n} and let ν(S) denote its cardinality. By O(S) we mean a collection of all finite sequences made of the elements from S. If O ∈ O(S), we assume that each element of S appears at least once in O (otherwise S is replaced by some of its proper subsets). Thus, each sequence from O(S) contains at least ν(S) terms. If S is an empty set, ν(S) = 0 and O(S) consists of a singleton, which is an empty sequence.

A cyclic or a quasi-cyclic strategy can be specified in the following way. For any O = {(i_{r}, j_{r})}_{r=0}^{M−1} ∈ O(P_{n}), the cyclic or the quasi-cyclic strategy I_{O}, generated by O, is given by

I_{O}(k) ≡ (p(k), q(k)) = (i_{r}, j_{r}), 0 ≤ r ≤ M − 1, k ≥ 0,

provided that k ≡ r (mod M). Thus,

(p(0), q(0)) = (i_{0}, j_{0}), (p(1), q(1)) = (i_{1}, j_{1}), …
(p(M − 1), q(M − 1)) = (i_{M−1}, j_{M−1}), (p(M), q(M)) = (i_{0}, j_{0}),
(p(M + 1), q(M + 1)) = (i_{1}, j_{1}), …

We denote the Jacobi method, which defines ϕ_{k} by (2.2) and uses the pivot strategy I by J(I). J(I) is called quasi-cyclic/ cyclic (Jacobi) method if I is the quasi-cyclic/ cyclic strategy. Since n is fixed, in the sequel we write P for P_{n}.

Let S be any subset of P. By O_{R}(S) we denote the “row-wise ordering” of S, that is the sequence satisfying the following two conditions: (i) each element (i, j) ∈ S appears exactly once in O_{R}(S); (ii) for any two terms (i_{1}, j_{1}) and (i_{2}, j_{2}) in O_{R}(S), (i_{1}, j_{1}) precedes (i_{2}, j_{2}) if i_{1} < i_{2} or i_{1} = i_{2} and j_{1} < j_{2}. In an obvious manner we can define the “column-wise” ordering of S denoted by O_{C}(S).

Let S_{i}, 1 ≤ i ≤ σ, be subsets of P and let O_{i} ∈ O(S_{i}), 1 ≤ i ≤ σ be arbitrary sequences. By [O_{1}, O_{2}, …, O_{σ}], we mean the sequence which is obtained by the concatenation of the sequences O_{1},O_{2}, …, O_{σ}. Often, we shall omit the brackets.

2.2. Quasi-cyclic Strategies. To prove the convergence theorem (Theorem 2.1 below), we need the notion of equivalent strategies. This notion is extended from cyclic [8, 9, 17] to quasi-cyclic strategies, as it has been done in [16]. In the sequel, strategy means quasi-cyclic pivot strategy.

Let S be a subset of P. Let O = {(i_{r}, j_{r})}_{r=0}^{s} ∈ O(S). An admissible transposition on O is any transposition of two adjacent terms (i_{r}, j_{r}), (i_{r+1}, j_{r+1}) → (i_{r+1}, j_{r+1}), (i_{r}, j_{r}), provided that the sets {i_{r}, j_{r}} and {i_{r+1}, j_{r+1}} are disjoint. Such two pairs will also be called interchangeable or commuting.

The sequences O, O′ ∈ O(S) are equivalent if one can be obtained from the other by a finite number of admissible transpositions. In this case we write O ∼ O′. For example, if S = {(1, 2), (2, 3), (1, 4)}, then O = (1, 2), (1, 2), (1, 4), (2, 3), (2, 3) ∈ O(S) and O′ = (1, 2), (1, 2), (2, 3), (2, 3), (1, 4) ∈ O(S) are equivalent.

Let I be a strategy with period M. By O_{I} we mean the sequence {I(k)}_{k=0}^{M−1}. If I and I′ are two strategies with the same period M, then I and I′ are equivalent if O_{I} ∼ O_{I} ′. In such a case we write I ∼ I′.

For a given symmetric matrix A and a given strategy I, the sequence {R^{(k)}} is well defined. Let T_{I(k)}(X) mean [R^{(k)}]^{T} XR^{(k)}. Then the recursion in (2.1) can be written A^{(k+1)} = T_{I(k)}(A^{(k)}), implying

A^{(k+1)} = T_{I(k)}T_{I(k−1)} ⋯ T_{I(0)}(A), k ≥ 0,

where T_{I(k)}T_{I(k−1)} ⋯ T_{I(0)} denotes the composition of the underlying linear operators. Let

T_{k}^{I} = T_{I(k−1)}T_{I(k−2)} ⋯ T_{I(0)}, k ≥ 1; T_{0}^{I} = E,

where E is the identity operator. Note that T_{I(k)} commutes with T_{I(k+1)} if (p(k), q(k)) and (p(k + 1), q(k + 1)) are commuting. Hence using the same argument as in [11, Lemma 1.1], we obtain the following implication (see also [8]):

If I ∼ I′, then T_{kM}^{I}(A) = T_{kM}^{I′}(A), k ≥ 0.  (2.3)

That is, equivalent strategies give the same matrices at the end of each quasi-sweep consisting of M iterations of the form (2.1). Since {S(A^{(k)})}_{k=0}^{∞} makes a non-increasing sequence, (2.3) implies that J(I) is convergent iff J(I′) is convergent, provided that I ∼ I′. In particular, if the relation (1.1) holds for I′ and I ∼ I′, then it holds for I.

2.3. The Special Quasi-cyclic Block-oriented Method. Let A = (a_{rs}) be a real symmetric matrix of order n. The starting point in describing the method is the following blockpartition of A,

A = [ \begin{matrix}A_{11} & A_{12} & ⋯ & A_{1m} \\ A_{21} & A_{22} & ⋯ & A_{2m} \\ ⋮ & ⋮ & ... & ⋮ \\ A_{m1} & A_{m2} & ⋯ & A_{mm} \end{matrix} ] \} n_{1} ; \} n_{2} ; ⋮ ; \} n_{m} ,

where A_{ij} is an n_{i} × n_{j} block of A. Since n_{1} + ⋯ + n_{m} = n, M = (n_{1}, n_{2}, …, n_{m}) is a partition of n. In practical computations, it is desirable that no n_{i} exceeds some n_{0} which depends on the machine and its available fast (cache) memory. The cache memory is several times (according to [2, Section 1.3.2] 5 to 10 times) faster than the main computer memory.

With each submatrix B contained in the upper-triangle of A (or with each principal submatrix B of A) one can associate the set S(B) ⊆ P of those pairs which are subscripts of the elements of B (and of the upper triangle of B). By abuse of notation, the row- and the column-wise orderings of S(B) are denoted by O_{R}(B) (= O_{R}(S(B))) and O_{C}(B) (= O_{C}(S(B))), respectively. We shall also use S_{ij} = S(A_{ij}) and R_{ij} = O_{R}(A_{ij}) (= O_{R}(S_{ij})), C_{ij} = O_{C}(A_{ij}) (= O_{C}(S_{ij})) for i ≤ j.

Let O_{M} denote the sequence of pairs which defines one quasi-sweep of the method from [6]. It is defined as follows.

First, define sequences

R_{i} = [R_{i+1,i+1}, R_{ii}, R_{i,i+1}, R_{i,i+2}, …, R_{im}]. 1 ≤ i ≤ m − 1.

Then,

O_{M} = [R_{11}, R_{1}, R_{2}, …, R_{m−1}, R_{mm}].  (2.4)

The quasi-cyclic Jacobi method from [6], is defined by the strategy I_{M} = I_{O_{M}} and we denote it by J_{M}. Its pivot strategy I_{M} uses the row-wise ordering within each block A_{ij}. I_{M} fetches the blocks in a row-wise fashion, and all the diagonal blocks A_{ii} are operated twice. Therefore, we call it the special quasi-cyclic block-oriented method. The quasi-sweep contains M ordinary Jacobi steps, where M is the number of pairs in the sequence O_{M} from (2.4). The aim of the paper is to prove the global convergence of J_{M}. In particular, we shall prove

Theorem 2.1. Let m ≥ 1 be an integer. Then for all n ≥ max{m, 2} the following assertion holds.

Let M = (n_{1}, …, n_{m}) be any partition of n into m positive integers. Let A be any symmetric matrix of order n. Let (A_{ij}) be the corresponding block-partition of A, consisting of m block-rows and m block-columns, such that A_{ii} is n_{i} × n_{i}, 1 ≤ i ≤ m. Let the quasicyclic Jacobi method J_{M} be applied to A, generating the sequence of iterates A^{(0)} = A, A^{(1)}, A^{(2)}, … Then after one quasi-sweep consisting of

M = n(n − 1)/2 + ∑_{i=1}^{m} n_{i}(n_{i} − 1)/2

Jacobi steps, the relation

S^{2}(A^{(M)}) ≤ t_{n}^{(M)} S^{2}(A), 0 ≤ t_{n}^{(M)} < 1,  (2.5)

holds, where for the given partition M, the bound t_{n}^{(M)} depends only on n.

3. Proof of Theorem 2.1. To prove Theorem 2.1, it is sufficient to prove (2.5) for some strategy I which is equivalent to I_{M}. We shall find such an I with the special property that it fetches the matrix elements by block-columns and within each block-column by columns, plus some extra work within the diagonal blocks.

3.1. Obtaining I. We call two sets S_{1} and S_{2} from P commuting if each pair from S_{1} commutes with all the pairs from S_{2}. In the same way we define two commuting sequences made of the elements from P. Obviously, if S_{1} and S_{2} are commuting, then each sequence made of the elements from S_{1} commutes with all the sequences made of the elements from S_{2} and vice versa. If the two commuting subsequences take adjacent positions in the sequence which defines some pivot strategy, then we can interchange the positions of these two subsequences, obtaining an equivalent (sequence and) pivot strategy.

To define I, we start with the sequence O_{M} and transform it using admissible transpositions. We divide the process into several stages. In the first stage, we transform O_{M} into O_{1}, in the second stage we transform O_{1} into O_{2} and finally, we transform O_{2} into O which defines I.

We shall illustrate the transitions for the case m = 5. After this illustration, we shall provide the result which holds for general m. Except for the first line, we shall omit writing [ ] which denotes the concatenation of sequences. Vertical bars | are used only to better recognize the obtained subsequences. We have

O_{M} = [R_{11}, R_{1}, R_{2}, R_{3}, R_{4}, R_{55}]
= R_{11}, | R_{22}, R_{11}, R_{12}, R_{13}, R_{14}, R_{15}, | R_{33}, R_{22}, R_{23}, R_{24}, R_{25}, |
R_{44}, R_{33}, R_{34}, R_{35}| R_{55}, R_{44}, R_{45}, | R_{55} .

Note that R_{ii} commutes with R_{i+1,i+1} and that R_{ij} commutes with R_{pq} provided that (i, j) and (p, q) are commuting. Using these facts, we can “move left” the subsequence R_{22} from its 9th position to the 5th position, just behind R_{12} and we can “move right” R_{22} from the second position to the third position. Continuing this process, we obtain the following equivalent sequences

O_{M} ∼ R_{11}, | R_{11}, | R_{22}, R_{12}, R_{22}, | R_{13}, R_{14}, R_{15}, R_{33}, R_{23}, R_{24}, R_{25},
R_{44}, R_{33}, R_{34}, R_{35}, | R_{55}, R_{44}, R_{45}, | R_{55}
∼ R_{11}, R_{11}, | R_{22}, R_{12}, R_{22}, | R_{13}, R_{33}, R_{23}, R_{33}, | R_{14}, R_{15}, R_{24}, R_{25},
R_{44}, R_{34}, R_{35}, R_{55}, R_{44}, R_{45}, | R_{55}
∼ R_{11}, R_{11}, | R_{22}, R_{12}, R_{22}, | R_{13}, R_{33}, R_{23}, R_{33}, | R_{14}, R_{24}, R_{44}, R_{34}, |
R_{15}, R_{25}, R_{35}, R_{55}, R_{44}, R_{45}, | R_{55}
∼ R_{11}, R_{11}, | R_{22}, R_{12}, R_{22}, | R_{13}, R_{33}, R_{23}, R_{33}, |
R_{14}, R_{24}, R_{44}, R_{34}, R_{44}, | R_{15}, R_{25}, R_{35}, R_{55}, R_{45}, R_{55} .

Using the same technique, we can conclude that for general m, O_{M} ∼ O_{1}, where

O_{1} = R_{11}, R_{11}, | R_{22}, R_{12}, R_{22}, | R_{13}, R_{33}, R_{23}, R_{33}, | …
| R_{1m}, R_{2m}, R_{3m}, …, R_{m−2,m}, R_{mm}, R_{m−1,m}, R_{mm} .

We see that O_{1} is obtained by the concatenation of m subsequences, the jth one having the form

R_{1j}, R_{2j}, R_{3j}, …, R_{j−2,j}, R_{jj}, R_{j−1,j}R_{jj}, 3 ≤ j ≤ m.

Note that the first subsequence R_{11}, R_{11} and the second one R_{22}, R_{12}, R_{22} also fit in this pattern. Therefore, we can write

O_{M} ∼ □ _{j=1}^{m} R_{1j}, R_{2j}, R_{3j}, …, R_{j−2,j}, R_{j,j}, R_{j−1,j}R_{j,j} ,  (3.1)

where □ stands for the concatenation. Now, remember that (see [8, 9]) the row-cyclic and the column-cyclic orderings are equivalent. This means that we can replace each R_{ii} by C_{ii}. Furthermore, the row-wise ordering of each rectangular block is equivalent to the columnwise ordering of that block. Hence, for 3 ≤ j ≤ m, we have

R_{1j}, R_{2j}, R_{3j}, …, R_{j−2,j} ∼ O_{R}(B_{j}) ∼ O_{C}(B_{j}) ≡ C_{j} , where B_{j} = [ A_{1j} ; A_{2j} ; ⋮ ; A_{j−2,j} ] .

Note that B_{j} ∈ R^{s_{j−2}×n_{j}}, where

s_{j} = n_{1} + n_{2} + ⋯ + n_{j}, 1 ≤ j ≤ m, s_{0} = 0.

Let

c_{jk} = O_{C}(B_{j}e_{k}) = (1, s_{j−1} + k), (2, s_{j−1} + k), …, (s_{j−2}, s_{j−1} + k), 1 ≤ k ≤ n_{j},

where e_{k} is the k’th column of the identity matrix, so that B_{j}e_{k} is the k’th column of B_{j}. Then

C_{j} = c_{j1}, c_{j2}, …, c_{jn_{j}} 3 ≤ j ≤ m .

Furthermore, we can write

R_{1j}, R_{2j}, R_{3j}, …, R_{j−2,j}, R_{jj}, R_{j−1,j}R_{jj} ∼ C_{j}, C_{jj}, C_{j−1,j}, C_{jj} ≡ C_{j} .  (3.2)

If we set

c′_{jk} = O_{C}(A_{j−1,j}e_{k}), 1 ≤ k ≤ n_{j} and
c′′_{jk} = O_{C}([e_{1}, …, e_{k−1}]^{T} A_{jj}e_{k}), 2 ≤ k ≤ n_{j}.

Then

C_{j−1,j} = c′_{j1}, c′_{j2}, …, c′_{jn_{j}} and C_{jj} = c′′_{j2}, c′′_{j3}, …, c′′_{jn_{j}}.

Hence, we can write for 3 ≤ j ≤ m,

C_{j} = c_{j1}, c_{j2}, …, c_{jn_{j}}, c′′_{j2}, …, c′′_{jn_{j}}, c′_{j1}, c′_{j2}, …, c′_{jn_{j}}, c′′_{j2}, …, c′′_{jn_{j}}.  (3.3)

For j = 1 the above formula reduces to c′′_{12}, …, c′′_{1n_{1}}, c′′_{12}, …, c′′_{1n_{1}} and for j = 2 to c′′_{22}, …, c′′_{2n_{2}}, c′_{21}, c′_{22}, … c′_{2n_{2}}, c′′_{22}, …, c′′_{2n_{2}}.

Lemma 3.1. The following assertions hold:

(i) C_{j} ∼ C_{j} = c_{j1}, c_{j2}, c′′_{j2}, c_{j3}, c′′_{j3}, …, c_{jn_{j}}, c′′_{jn_{j}}, c′_{j1}, c′_{j2}, c′′_{j2}, …, c′_{jn_{j}}, c′′_{jn_{j}},

3 ≤ j ≤ m.

(ii) If we set C_{1} = C_{11}, C_{11}, C_{2} = C_{22}, c′_{21}, c′_{22}, c′′_{22}, …, c′_{2n_{2}}, c′′_{2n_{2}}, then

O_{M} ∼ O = □ _{j=1}^{m} C_{j} .  (3.4)

Proof. (i) We start from the sequence C_{j} in the relation (3.3) and transform it by admissible transformations into C_{j}. Since c′′_{j2} commutes with the subsequence c_{j3}, …,c_{jn_{j}}, we can move it left to the position just behind c_{j2}. In a similar fashion, we move c′′_{j3} just behind c_{j3} and so on. Note that, c′_{j1}, …,c′_{jn_{j}}, c′′_{j2}, …,c′′_{jn_{j}}, can be replaced by c′_{j1}, c′_{j2}, c′′_{j2}, …, c′_{jn_{j}}, c′′_{jn_{j}}, which is the column-wise ordering of [A_{j−1,j}^{T}, A_{jj}^{T}]^{T}.

(ii) As has been shown in the lines after the relation (3.3),

R_{11}R_{11} ∼ C_{1} = C_{11}C_{11} = C_{1}
R_{22}R_{12}R_{22} ∼ C_{2} = C_{22}C_{12}C_{22} ∼ C_{2} .

Using (3.1), (3.2), (3.3) and (i), we obtain (3.4).

Thus, in considering the off-norm reduction after one quasi-sweep of the original method J_{M}, we can replace the initial pivot strategy defined by O_{M} with the pivot strategy defined by O.

To prove Theorem 2.1, we use mathematical induction with respect to m.

The Induction Basis. For m = 1, O_{M} = R_{11}R_{11} ∼ C_{11}C_{11} = O and by the wellknown result of Henrici and Zimmermann [13], we have

S^{2}(A^{(M)}) ≤ (1 − 2^{− \frac{(n_{1}−1)(n_{1}−2)}{2}} )^{2} S^{2}(A) .

Since for m = 1, n = n_{1}, we can take t_{n}^{(M)} = (1 − 2^{−n^{2}/2})^{2}, which is smaller than one for all n ≥ 2.

For m = 2, O_{M} = R_{11}R_{22}R_{11}R_{12}R_{22} ∼ O, hence by the same result

S^{2}(A^{(M)}) ≤ (1 − 2^{− \frac{(n−1)(n−2)}{2}} ) S^{2}(A^{( \frac{n_{1}(n_{1}−1)}{2} + \frac{n_{2}(n_{2}−1)}{2} )}) ≤ (1 − 2^{− \frac{(n−1)(n−2)}{2}} ) S^{2}(A) ,

so we can take t_{n}^{(M)} = 1 − 2^{−n^{2}/2}, n ≥ 2.

The Induction Hypothesis. Let us assume that the assertion of the Theorem 2.1 holds for m′ = m − 1. This means that (2.5) holds for any partition M′ = (n′_{1}, …, n′_{m′}) of n′, n′ ≥ max{2, m′}, and for any symmetric matrix A′ of order n′ such that:

(a) A′ is partitioned into m′ block-rows and block-columns, according to the partition M′.

(b) the sequence A^{(0)} = A′, A^{(1)},… is generated by the Jacobi method which is defined by the quasi-cyclic strategy I_{O_{M′}} and O_{M′} is defined by (2.4) provided that m and M are replaced by m′ and M′, respectively.

Since O_{M′} ∼ O′, where O′ is defined as in (3.4), the induction hypothesis implies that (2.5) holds for the strategy defined by O′.

3.2. The Induction Step. To prove the induction step, we assume that M = (n_{1}, …, n_{m}) is an arbitrary partition of n, n ≥ m ≥ 3 and A = (A_{ij}) is an arbitrary symmetric matrix of order n, partitioned into m block-rows and m block-columns, according to the partition M. We have to prove Theorem 2.1 for A and J_{M} defined by O_{M}, provided the induction hypothesis holds.

Since O_{M} ∼ O, the same matrix A^{(M)} is obtained if the quasi-cyclic Jacobi method J_{M} is replaced by J which is defined by O. So, from here on, we assume that A = A^{(0)}, A^{(1)}, …, A^{(M)} are generated by J.

Notation. Let I_{n} = [e_{1}, …, e_{n}] be the column-partition of the identity matrix. Using the coordinate vectors e_{j}, we define

E_{j} = [e_{1}, …, e_{j}], 1 ≤ j ≤ n,
so that E_{n} = I_{n}. Let
ñ = s_{m−1} = n_{1} + n_{2} + … + n_{m−1}
M̃ = \frac{ñ(ñ − 1)}{2} + ∑_{i=1}^{m−1} \frac{n_{i}(n_{i} − 1)}{2}
Ã = A^{(M̃)}, B = ET ; ñ AEñ, B̃ = ET ; ñ ÃEñ
Σ^{2} = S^{2}(A) , S^{2}(B) = εΣ^{2} , 0 ≤ ε ≤ 1 .

Note that after M̃ steps, one full quasi-sweep is performed on B. The underlying strategy is defined by Õ, which is defined via M̃ = (n_{1}, …, n_{m−1}). This Õ is one of those O′ described above, and the induction hypothesis can be applied to B. We obtain

S^{2}(B̃) ≤ t(M̃) ; ñS^{2}(B) = t(M̃) ; ñεΣ^{2}, 0 ≤ t(M̃) ; ñ < 1 .

Hence,

S^{2}(Ã) = S^{2}(B̃) + (1 − ε)Σ^{2} ≤ t(M̃) ; ñεΣ^{2} + (1 − ε)Σ^{2} = [1 − ε(1 − t(M̃) ; ñ)]Σ^{2} .

Although S^{2}(A^{(M)}) ≤ S^{2}(Ã), we cannot set t_{n}^{(M)} = 1 − ε(1 − t(M̃) ; ñ), since ε can be arbitrarily small or even zero. Therefore, we have to estimate the contribution to the further off-norm reduction coming from the last M − M̃ steps.

Let

\begin{matrix}ε_{1}Σ^{2} = S^{2}(E_{ñ−n_{m−1}}^{T} ÃE_{ñ−n_{m−1}}), \\ ε_{2}Σ^{2} = ∑_{i=1}^{m−2} ∥Ã_{i,m−1}∥_{F}^{2} , \\ ε_{3}Σ^{2} = S^{2}(Ã_{m−1,m−1}) . \end{matrix}  (3.5)

Then

ε_{1} + ε_{2} + ε_{3} ≤ t(M̃) ; ñε ≤ ε .  (3.6)

In Figure 1, the areas of Ã which have contributed to ε_{1}Σ^{2}, ε_{2}Σ^{2} and ε_{3}Σ^{2} are colored , and , respectively.

3.2.1. The Case n_{m} = 1. In this case, the proof of the induction step immediately follows from the third assertion of the following proposition. One just has to set Γ = Σ

(= S(A^{(0)})) and μ = t(M̃) ; ñ.

The first and third assertions of this proposition are modifications of a similar result from [12].

Proposition 3.2. Let A = (a_{pq}) be a symmetric matrix of order n ≥ 3 and let B = E_{n−1}^{T}AE_{n−1}. Suppose that r, 1 ≤ r ≤ n − 1, Jacobi steps are applied to the last column of A, to successively annihilate the elements at positions (1, n), (2, n), …,(r, n). For the obtained sequence of iterates A^{(0)} = A, A^{(1)}, …, A^{(n−1)}, the following assertions hold.

(i) [∑_{i=1}^{r} |a_{in}^{(i−1)}|^{2}]^{1/2} ≥ [\frac{2^{1−r}}{r} ∑_{i=1}^{r} |a_{in}|^{2}]^{1/2}−[\frac{r − 1}{4} ∑_{i=1}^{r} ∑_{k=1}^{i−1} |a_{ik}|^{2}]^{1/2}, r ≤ n−1.

(ii) [ ∑_{i=r+1}^{t} |a_{in}^{(r)}|^{2}]^{1/2} ≥ [\frac{2^{−r}}{t − r} ∑_{i=r+1}^{t} |a_{in}|^{2}]^{1/2} − [\frac{r}{2} ∑_{i=r+1}^{t} ∑_{k=1}^{r} |a_{ik}|^{2}]^{1/2}, t > r.

(iii) Suppose there exist real numbers 0 ≤ μ < 1, 0 ≤ α ≤ 1 and Γ, such that

S^{2}(B) ≤ μ(αΓ^{2}) and ∑_{i=1}^{n−1} |a_{in}|^{2} = (1 − α)Γ^{2} .  (3.7)

Then there exists μ′, 0 ≤ μ′ < 1, depending on n and μ, such that

S^{2}(A^{(n−1)}) ≤ μ′ Γ^{2} .

Proof. (i) Let us denote the rotation angle which is used to annihilate the element at position (k, n) by ϕ_{kn}. Consider the history of the element at position (i, n), i > 1 up to its annihilation. We have

a_{in}^{(1)} = cos ϕ_{1n} a_{in} + sin ϕ_{1n} a_{i1}
a_{in}^{(2)} = cos ϕ_{2n} a_{in}^{(1)} + sin ϕ_{2n} a_{i2}
⋮
a_{in}^{(i−1)} = cos ϕ_{i−1,n} a_{in}^{(i−2)} +
+ sin ϕ_{i-1,n} a_{i,i−1}

These relations imply a_{in} a_{i1}  ∗ sin ϕ_{1n} a_{i2}  ∗ sin ϕ_{2n} ·  · a_{i,i-1}  ∗ sin ϕ_{i-1,n}

a_{in}^{(i−1)} = a_{in} cos ϕ_{1n} cos ϕ_{2n} ⋯ cos ϕ_{i−1,n} + a_{i,i−1} sin ϕ_{i−1,n}

+a_{i,i−2} sin ϕ_{i−2,n} cos ϕ_{i−1,n} + ⋯ + a_{i1} sin ϕ_{1n} cos ϕ_{2n} ⋯ cos ϕ_{i−1,n} .

Note that z = x + y implies |z| ≥ |x| − |y|. Applying this to the above relation, one obtains

|a_{in}^{(i−1)}| ≥ cos ϕ_{1n} cos ϕ_{2n} ⋯ cos ϕ_{i−1,n}|a_{in}|

− ∑_{k=1}^{i−1} |a_{ik}| | sin ϕ_{kn}| cos ϕ_{k+1,n} ⋯ cos ϕ_{i−1,n}

≥ |a_{in}| · (2^{− \frac{1}{2}} )^{i−1} − ∑_{k=1}^{i−1} |a_{ik}| | sin ϕ_{kn}| .

This inequality holds for i = 1 provided that an empty sum is defined zero.

Summing up over 1 ≤ i ≤ r and using the Cauchy-Schwarz inequality, we obtain

∑_{i=1}^{r} |a_{in}^{(i−1)}| ≥ ∑_{i=1}^{r} 2^{− \frac{i−1}{2}} |a_{in}| − ∑_{i=1}^{r} ∑_{k=1}^{i−1} |a_{ik}| | sin ϕ_{kn}|

≥ 2^{− \frac{r−1}{2}} ∑_{i=1}^{r} |a_{in}| − [∑_{i=1}^{r} ∑_{k=1}^{i−1} |a_{ik}|^{2}]^{1/2} [\frac{1}{2} \frac{r(r − 1)}{2}]^{1/2}

≥ \sqrt{2^{1−r}} [∑_{i=1}^{r} |a_{in}|^{2}]^{1/2} − \frac{\sqrt{r(r − 1)}}{2} [∑_{i=1}^{r} ∑_{k=1}^{i−1} |a_{ik}|^{2}]^{1/2} .

10 V. Hari

Since by the Cauchy-Schwarz inequality

∑_{i=1}^{r} |a_{in}^{(i−1)}| ≤ \sqrt{r} [∑_{i=1}^{r} |a_{in}^{(i−1)}|^{2}]^{1/2} ,

the first assertion easily follows. (ii) In this case we have for r + 1 ≤ i ≤ t, t ≤ n − 1,

a_{in}^{(r)} = a_{in} cos ϕ_{1n} cos ϕ_{2n} ⋯ cos ϕ_{rn} + a_{ir} sin ϕ_{rn} + a_{i,r−1} sin ϕ_{r−1,n} cos ϕ_{rn}
+ ⋯ + a_{i1} sin ϕ_{1n} cos ϕ_{2n} ⋯ cos ϕ_{rn}

and

|a_{in}^{(r)}| ≥ cos ϕ_{1n} ⋯ cos ϕ_{rn}|a_{in}| − ∑_{k=1}^{r} |a_{ik}| | sin ϕ_{kn}| cos ϕ_{k+1,n} ⋯ cos ϕ_{rn}
≥ |a_{in}| · (2^{− \frac{1}{2}} )^{r} − ∑_{k=1}^{r} |a_{ik}| | sin ϕ_{kn}| .

Hence,

∑_{i=r+1}^{t} |a_{in}^{(r)}| ≥ ∑_{i=r+1}^{t} 2^{− \frac{r}{2}} |a_{in}| − ∑_{i=r+1}^{t} ∑_{k=1}^{r} |a_{ik}| | sin ϕ_{kn}|
≥ 2^{− \frac{r}{2}} [ ∑_{i=r+1}^{t} |a_{in}|^{2}]^{1/2} − [ ∑_{i=r+1}^{t} ∑_{k=1}^{r} |a_{ik}|^{2}]^{1/2} [\frac{r(t − r)}{2}]^{1/2} ,

and an application of the Cauchy-Schwarz inequality yields (ii). (iii) Using (i) with r = n − 1 and the assumption (3.7), we obtain

[∑_{i=1}^{n−1} |a_{in}^{(i−1)}|^{2}]^{\frac{1}{2}} ≥ \{[\frac{2^{2−n}}{n − 1}]^{1/2} \sqrt{1 − α} − \frac{\sqrt{n − 2}}{2}\sqrt{α}\} Γ .  (3.8)

The function

f_{n}(α) = [\frac{2^{2−n}}{n − 1}]^{1/2} \sqrt{1 − α} − \frac{\sqrt{n − 2}}{2}\sqrt{α}

is continuous and decreasing on the segment [0, 1] with the only root

ξ_{n} = \frac{1}{1 + 2^{n−4}(n − 1)(n − 2)} .

In the above relation, note that n ≥ 3. If we take

ζ_{n} = \frac{ξ_{n}}{2} = \frac{1}{2 + 2^{n−3}(n − 1)(n − 2)} ,

we obtain from the relation (3.8)

∑_{i=1}^{n−1} |a_{in}^{(i−1)}|^{2} ≥ η_{n}Γ^{2} , η_{n} = [f_{n}(ζ_{n})]^{2} > 0, α ∈ [0, ζ_{n}] .

Thus, during the last n − 1 steps S^{2}(A) = S^{2}(B) + (1 − α)Γ^{2} ≤ μ(αΓ^{2}) + (1 − α)Γ^{2} = [1 − α(1 − μ)]Γ^{2} ≤ Γ^{2}, has decreased by an amount not smaller than η_{n}Γ^{2}, η_{n} > 0. Hence

S^{2}(A^{(n−1)}) ≤ \{ \begin{matrix}(1 − η_{n})Γ^{2} if α ∈ [0, ζ_{n}] \\ [1 − α(1 − μ)]Γ^{2} if α ∈ [ζ_{n} , 1] \end{matrix} .

So, we can complete the proof by setting

μ′ = max{1 − ζ_{n}(1 − μ) , 1 − η_{n}} .

Note that μ′ depends only on n and μ.

Remark 3.3. Proposition 3.2(iii) provides a basis of the simplest proof of global convergence of the serial symmetric Jacobi method. Indeed, the proof uses induction with respect to n. The induction basis takes advantage of the fact that for n = 2, S(A^{(1)}) = 0. The induction hypothesis assumes that S(A^{( \frac{(n−1)(n−2)}{2} )}) ≤ μS(A) for any initial symmetric matrix of order n − 1, where 0 ≤ μ < 1 depends only on n − 1 (that is on n). The induction step is then proved by Proposition 3.2(iii) and the assumption that Γ = S(A).

However, the proof presented here can easily be generalized for strategies, slightly more general than the column-cyclic strategy. We can consider any strategy which annihilates the elements in column-wise fashion, so that in the jth column, 2 ≤ j ≤ n, the annihilation ordering is (π_{j−1}(1), j), (π_{j−1}(2), j), …, (π_{j−1}(j − 1), j), for any permutation π_{j−1} of the set {1, 2, …, j − 1}. The proof of the induction step is almost the same as that of Proposition 3.2. Just consider the history of the element at position (π_{n−1}(i), n), i > 1 up to its annihilation. This means that at step i − 1 (of the last n − 1 steps) the element at position (π_{n−1}(i), n) is annihilated. Now, follow the proof of Proposition 3.2(iii) and replace all the subscripts i and k (but not the superscript i) by π(i) and π(k), respectively.

Remark 3.4. The first proof of global convergence of the serial methods is given by Forsythe and Henrici [13] and the first estimate of the form S(A^{(N)}) ≤ t_{n}S(A) by Henrici and Zimmermann [13] who obtained the known estimate

t_{n} = [1 − ∏_{i=1}^{n−2} ∏_{j=i+2}^{n} cos ϕ_{ij}^{2}]^{1/2} .

See also similar results in [15, 10, 7].

3.2.2. The Case n_{m} ≥ 2. Note that m ≥ 3, n ≥ m and n_{m} ≥ 2, hence n ≥ 4. We assume Σ > 0, since otherwise there is nothing to prove. According to the pivot strategy, during the subsequent

μ = n_{m}(ñ − n_{m−1}) + n_{m}(n_{m} − 1)/2  (3.9)

Jacobi steps defined by the pivot pairs sequence c_{m1}, c_{m2}, c′′_{m2}, …,c_{m,n_{m}}, c′′_{m,n_{m}}, we have

∥A_{m−1,m}^{(M̃+k)}∥_{F}^{2} + ∑_{i=1}^{m−2} ∥A_{i,m−1}^{(M̃+k)}∥_{F}^{2} = ∥Ã_{m−1,m}∥_{F}^{2} + ε_{2}Σ^{2} , 0 ≤ k ≤ μ .

Therefore, for 0 ≤ k ≤ μ, we split A^{(M̃+k)},

A^{(M̃+k)} = H^{(M̃+k)} + T^{(M̃+k)},

where

H^{(M̃+k)} = [ \begin{matrix}B_{ñ−n_{m−1}}^{(M̃+k)} & 0 & Γ^{(M̃+k)} \\ 0 & 0 & 0 \\ [Γ^{(M̃+k)}]^{T} & 0 & A_{mm}^{(M̃+k)} \end{matrix} ] , Γ^{(M̃+k)} = [ A_{1m}^{(M̃+k)} ; ⋮ ; A_{m−2,m}^{(M̃+k)} ] , 0 ≤ k ≤ μ .

j^{1} ^{2} ^{3} ^{4} ñ  ñ − n_{m−1} n_{m−1} n_{m}
Fig. 1. Matrices Ã and B̃ for the case n_{i} = 4, 1 ≤ i ≤ m, m = 6.

Since the off-norm of T^{(M̃+k)} is invariant under Jacobi transformations during all these μ steps, we shall use the matrix

W^{(M̃+k)} = [ \begin{matrix}B_{ñ−n_{m−1}}^{(M̃+k)} & Γ^{(M̃+k)} \\ [Γ^{(M̃+k)}]^{T} & A_{mm}^{(M̃+k)} \end{matrix} ] , 0 ≤ k ≤ μ .  (3.10)

Since the annihilations advance in a block-column wise fashion, we have

(1 − ε)Σ^{2} = S^{2}(A_{mm}) + ∑_{i=1}^{m−1} ∥A_{im}∥_{F}^{2} = S^{2}(Ã_{mm}) + ∑_{i=1}^{m−1} ∥Ã_{im}∥_{F}^{2} .  (3.11)

This follows from the fact that the Frobenius norm is invariant under orthogonal transformations. Recall that ε can be arbitrarily small. Because of (3.11), we consider the following two cases:

(a) S^{2}(Ã_{mm}) + ∑_{i=1}^{m−2} ∥Ã_{im}∥_{F}^{2} ≥ \frac{2^{−n}}{1 − 2^{−2n}} Σ^{2}

(b) ∥Ã_{m−1,m}∥_{F}^{2} > (1 − ε − \frac{2^{−n}}{1 − 2^{−2n}} ) Σ^{2}.

We start with case (a).

(a) In this case, there exists ȷ, 1 ≤ ȷ ≤ n_{m}, such that

∑_{i∈N_{ȷ}} |ã_{i,ñ+ȷ}|^{2} ≥ 2^{−(2(n_{m}−ȷ)+1)n} · Σ^{2}  (3.12)

where

N_{j} = {1, 2, …, ñ + j − 1} \ {ñ − n_{m−1} + 1, …, ñ}, 1 ≤ j ≤ n_{m} ,

and Ã = (ã_{ij}). Indeed, if (3.12) were false, then we would have

S^{2}(Ã_{mm}) + ∑_{i=1}^{m−2} ∥Ã_{im}∥_{F}^{2} = ∑_{j=1}^{n_{m}} ∑_{i∈N_{j}} |ã_{i,ñ+j}|^{2} < ∑_{j=1}^{n_{m}} 2^{−(2(n_{m}−j)+1)n}Σ^{2}

= (2^{−n} + 2^{−3n} + ⋯ + 2^{−(2n_{m}−1)n}) Σ^{2} = \frac{2^{−n}}{1 − 2^{−2n}} (1 − 2^{−2n_{m}n}) Σ^{2}

< \frac{2^{−n}}{1 − 2^{−2n}} Σ^{2} ,

which contradicts (a). If there are more than one ȷ satisfying (3.12), we define ȷ as the smallest one.

Let Â = (â_{ij}), Â = A^{(M̂)}, Ŵ = W^{(M̂)}, where W^{(M̂)} is given by (3.10), and

M̂ = M̃ + (ñ − n_{m−1}) + (ñ − n_{m−1} + 1) + ⋯ + (ñ − n_{m−1} + ȷ − 2) .

In other words, Â is the matrix iterate at stage just before the annihilations in column ȷ of the m’th block-column have begun. Thus, Â is obtained from Ã by applying

μ_{ȷ} = (ȷ − 1)(ñ − n_{m−1}) + (ȷ − 2)(ȷ − 1)/2

additional Jacobi steps. They are defined by the sequence of pivot pairs c_{m1}, c_{m2}, c′′_{m2}, …, c_{m,ȷ−1}, c′′_{m,ȷ−1}. Now, consider the matrices Ŵ_{ñ−n_{m−1}+ȷ} and W_{ñ−n_{m−1}+ȷ}^{(k)}, where

Ŵ_{i} = E_{i}^{T} Ŵ E_{i} and W_{i}^{(k)} = E_{i}^{T} A^{(k)}E_{i}, k ≥ M̃ .

Since all the Jacobi steps involved in the transition from Ã to Â cannot increase the off-norm of any W_{ñ−n_{m−1}+ȷ−1}^{(k)}, M̃ ≤ k ≤ M̂, we have

S^{2}(Ŵ_{ñ−n_{m−1}+ȷ−1}) ≤ S^{2}(W_{ñ−n_{m−1}+ȷ−1}^{(M̃)}) ≤ S^{2}(B̃_{ñ−n_{m−1}}) + ∑_{j=1}^{ȷ−1} ∑_{i∈N_{j}} |ã_{i,ñ+j}|^{2}

≤ ε_{1}Σ^{2} + (2^{−(2n_{m}−1)n} + 2^{−(2n_{m}−3)n} + ⋯ + 2^{−(2(n_{m}−ȷ)+3)n}) Σ^{2}

≤ (ε_{1} + \frac{2^{(−2n_{m}+2ȷ−3)n}}{1 − 2^{−2n}} ) Σ^{2} .  (3.13)

We also know that none of these μ_{ȷ} Jacobi steps has changed the sum of squares of the affected elements in the last column of W_{ñ−n_{m−1}+ȷ}^{(M̃+k)}, M̃ ≤ k ≤ M̂. Therefore

∑_{i∈N_{ȷ}} |â_{i,ñ+ȷ}|^{2} = ∑_{i∈N_{ȷ}} |ã_{i,ñ+ȷ}|^{2} .  (3.14)

In order to estimate the contribution to the off-norm reduction, coming from the annihilations in the (ñ − n_{m−1} + ȷ)’th column, we apply Proposition 3.2(i) to Ŵ_{ñ−n_{m−1}+ȷ} with r = ñ − n_{m−1} + ȷ − 1. This, together with (3.12), (3.13) and (3.14), implies

[ ∑_{i∈N_{ȷ}} |â_{i,ñ+ȷ}^{(M̂+i−1)}|^{2}]^{1/2} ≥ \frac{2}{\sqrt{(ñ − n_{m−1} + ȷ − 1)2^{ñ−n_{m−1}+ȷ}}} [ ∑_{i∈N_{ȷ}} |â_{i,ñ+ȷ}|^{2}]^{1/2}

− \frac{\sqrt{ñ − n_{m−1} + ȷ − 2}}{2} [ε_{1} + \frac{2^{(−2n_{m}+2ȷ−3)n}}{1 − 2^{−2n}} ]^{1/2} Σ

≥ \frac{2 · 2^{−(n_{m}−ȷ)n− \frac{n}{2}} · 2^{− \frac{n−n_{m−1}}{2}}}{\sqrt{n − n_{m−1} − 1}} Σ − \frac{\sqrt{n − n_{m−1} − 2}}{2} [ε_{1} + \frac{2^{(−2n_{m}+2ȷ−3)n}}{1 − 2^{−2n}} ]^{1/2} Σ

≥ \{\frac{2\sqrt{2} · 2^{−(n_{m}−ȷ+1)n}}{\sqrt{n − n_{m−1}}} − \frac{\sqrt{n − n_{m−1}}}{2} [ε_{1} + \frac{2^{(−2n_{m}+2ȷ−3)n}}{1 − 2^{−2n}} ]^{1/2}\} Σ .

We can write

[ ∑_{i∈N_{ȷ}} |â_{i,ñ+ȷ}^{(M̂+i−1)}|^{2}]^{1/2} ≥ g_{n,n_{m},n_{m−1},ȷ}(ε_{1})Σ,

where

g_{n,n_{m},n_{m−1},ȷ}(x) = \frac{\sqrt{n − n_{m−1}}}{2} \{\frac{4\sqrt{2} · 2^{−(n_{m}−ȷ+1)n}}{n − n_{m−1}} − [x + \frac{2^{(−2n_{m}+2ȷ−3)n}}{1 − 2^{−2n}} ]^{1/2} \} .

The function g_{n,n_{m},n_{m−1},ȷ} is decreasing and convex for 0 ≤ x ≤ 1,

g_{n,n_{m},n_{m−1},ȷ}(0) = \frac{\sqrt{n − n_{m−1}}}{2} 2^{−(n_{m}−ȷ+1)n} [\frac{4\sqrt{2}}{n − n_{m−1}} − \frac{2^{− \frac{n}{2}}}{\sqrt{1 − 2^{−2n}}} ]
> \frac{\sqrt{3}}{2}2^{−(n−2)n} [\frac{4\sqrt{2}}{n − 1} − 2^{− \frac{n}{2}} ] > \frac{4}{n}2^{−(n−2)n} ,

and with the positive root

η_{n,n_{m},n_{m−1},ȷ} = 2^{(−2n_{m}+2ȷ−2)n} (\frac{32}{(n − n_{m−1})^{2}} − \frac{2^{−n}}{1 − 2^{−2n}} ) .

Let

ζ_{n,n_{m},ȷ} = \frac{16}{n^{2}} · 2^{−2(n_{m}−ȷ+1)n}

Then

\frac{1}{2}η_{n,n_{m},n_{m−1},ȷ} > ζ_{n,n_{m},ȷ} > \frac{16}{n^{2}} 2^{−2(n−2)n} ≡ ξ_{n} ,

and we have

∑_{i∈N_{ȷ}} |â_{i,ñ+ȷ}^{(M̂+i−1)}|^{2} ≥ [g_{n,n_{m},n_{m−1}}(ζ_{n,n_{m},ȷ})]^{2}Σ^{2} whenever 0 ≤ ε_{1} ≤ ζ_{n,n_{m},ȷ} .

Note that

[g_{n,n_{m},n_{m−1}}(ζ_{n,n_{m},ȷ})]^{2} = \frac{n − n_{m−1}}{4} 2^{−2(n_{m}−ȷ+1)n} \{\frac{2\sqrt{2}}{n − n_{m−1}}

−\frac{4}{n} [1 − \frac{n^{2}}{16} \frac{2^{−n}}{1 − 2^{−2n}} ]^{1/2}\}^{2} > \frac{1}{2} 2^{−2(n−2)n} \{\frac{2\sqrt{2}}{n − n_{m−1}} − \frac{4}{n} [1 − \frac{n^{2}}{16} \frac{2^{−n}}{1 − 2^{−2n}} ]^{1/2}\}^{2}.

Hence, if 0 ≤ ε_{1} ≤ ζ_{n,n_{m},ȷ}, we have

∑_{i∈N_{ȷ}} |â_{i,ñ+ȷ}^{(M̂+i−1)}|^{2} > ϱ_{n}Σ^{2} ρ_{n} = \frac{8}{n^{2}} \{\sqrt{2} − [1 − \frac{n^{2}}{16} \frac{2^{−n}}{1 − 2^{−2n}} ]^{1/2}\}^{2} 2^{−2(n−2)n} .

This inequality certainly holds for 0 ≤ ε_{1} ≤ ξ_{n}. Thus, during the last M − M̃ Jacobi steps S^{2}(Ã) = S^{2}(B̃) + (1 − ε)Σ^{2} has decreased by an amount not smaller than ϱ_{n}Σ^{2}, ϱ_{n} > 0, provided that ε ≤ ξ_{n}. Hence

S^{2}(A^{(M)}) ≤ \{ \begin{matrix}(1 − ϱ_{n})Σ^{2} if ε ∈ [0, ξ_{n}] \\ [1 − ε(1 − t(M̃) ; ñ)]Σ^{2} if ε ∈ [ξ_{n} , 1] \end{matrix} .

So, we can complete the proof of the theorem by setting

t_{n}^{(M)} = max{[1 − ξ_{n}(1 − t(M̃) ; ñ) , 1 − ϱ_{n}} .

(b) In this case we begin the proof by assuming

ε < \frac{2^{−n}}{1 − 2^{−4n}} .  (3.15)

This implies

∥Ã_{m−1,m}∥_{F}^{2} > (1 − \frac{2^{−n}}{1 − 2^{−4n}} − \frac{2^{−n}}{1 − 2^{−2n}} ) Σ^{2} > (1 − \frac{2^{−n+1}}{1 − 2^{−2n}} ) Σ^{2} . (3.16)

Let F̃ = [Ã_{m−1,1}, Ã_{m−1,2}, …, Ã_{m−1,m}] and let [f̃_{1}, f̃_{2}, …, f̃_{n}] be the column partition of F̃. We claim that there exists ȷ, 1 ≤ ȷ ≤ n_{m}, not necessarily the same as above, such that

∥f̃_{ñ+j}∥ > \{ \begin{matrix}2^{−2(n_{m}−ȷ)n} Σ, if 1 ≤ ȷ ≤ n_{m} − 1 \\ (1 − 2^{−n+1}) Σ, if ȷ = n_{m} . \end{matrix} .  (3.17)

In fact, if (3.17) were false, we would have

∥Ã_{m−1,m}∥_{F}^{2} = ∑_{j=1}^{n_{m}} ∥f̃_{ñ+j}∥^{2} ≤ [2^{−4(n_{m}−1)n} + 2^{−4(n_{m}−2)n} + ⋯ + 2^{−4n}] Σ^{2}

+ (1 − 2^{−n+2} + 2^{−2n+2}) Σ^{2} = \frac{1 − 2^{−4n_{m}n}}{1 − 2^{−4n}} Σ^{2} − (2^{−n+2} + 2^{−2n+2})Σ^{2}

= [1 − 2^{−n+2} (1 − 2^{−n} − \frac{2^{−3n−2} − 2^{−4n_{m}n+n−2}}{1 − 2^{−4n}} )] Σ^{2} < (1 − \frac{2^{−n+1}}{1 − 2^{−2n}} ) Σ^{2} ,

which contradicts (3.16).

Recall that c_{m1}, c_{m2}, c′′_{m2}, c_{m3}, c′′_{m3}, …, c_{mn_{m}}, c′′_{mn_{m}} ∼ c_{m1}, c_{m2}, c_{m3}, …,c_{mn_{m}},

c′′_{m2}, c′′_{m3}, …, c′′_{mn_{m}}. Hence the same matrix A^{(M̃+μ)} (thus, the same block A_{m−1,m}^{(M̃+μ)}, where μ is given by (3.9)) is obtained if we assume that the annihilation ordering is defined by c_{m1}, c_{m2}, c_{m3}, …, c_{mn_{m}}, c′′_{m2}, c′′_{m3}, …, c′′_{mn_{m}}. Accepting that, note that the rotations which annihilate the elements in the diagonal block A_{mm}^{(k)} do not change the Frobenius norm of A_{m−1,m}^{(k)}.

Therefore we divide the proof into two stages. In Stage I we estimate the weight remaining in A_{m−1,m}^{(k)} after all Jacobi steps defined by the sequence c_{m1},c_{m2}, …,c_{mn_{m}} are com-

pleted. Actually, we shall compute a lower bound of ∥A_{m−1,m}^{(M̃+n_{m}(ñ−n_{m−1}))}∥_{F} = ∥A_{m−1,m}^{(M̃+μ)}∥_{F}.

In Stage II, we use a similar proof as in the case (a), but we apply it only to the part of the m’th block-column consisting of the blocks A_{m−1,m}^{(k)} and A_{mm}^{(k)}. In this second part, the annihilation ordering is defined by the sequence of pairs c′_{j1}, c′_{j2}, c′′_{j2} …,c′_{jn_{j}}, c′′_{jn_{j}}.

Stage I.

Let ȷ be the first (smallest) index for which (3.17) holds. Let Â = (â_{ij}) be the matrix A^{(M̂)}, where

M̂ = M̃ + μ̃_{ȷ}, μ̃_{ȷ} = (ñ − n_{m−1})(ȷ − 1) .

Thus, Â is obtained from Ã by applying additional μ̃_{ȷ} Jacobi steps according to the sequence of pivot pairs c_{m1}, c_{m2}, …,c_{m,ȷ−1}. Let F̂ = [Â_{m−1,1}, Â_{m−1,2}, …, Â_{m−1,m}] and let F̂ = [f̂_{1}, f̂_{2}, …, f̂_{n}] be its column partition. More generally, for 0 ≤ k ≤ μ̃_{j}, let

F̃^{(k)} = [A_{m−1,1}^{(M̃+k)}, A_{m−1,2}^{(M̃+k)}, …, A_{m−1,m}^{(M̃+k)}] = [f̃_{1}^{(k)}, f̃_{2}^{(k)}, …, f̃_{n}^{(k)}].

The Jacobi transformations involved in the transition from F̃ to F̂ do not change the Frobenius norm of any F̃^{(k)}E_{ñ+ȷ−1}, 0 ≤ k ≤ μ̃_{j} and they do not transform any element of Ã_{m−1,m−1}. Therefore, we have

∑_{j=1}^{ñ−n_{m−1}} ∥f̂_{j}∥^{2} + ∑_{j=ñ+1}^{ñ+ȷ−1} ∥f̂_{j}∥^{2} = ∑_{j=1}^{ñ−n_{m−1}} ∥f̃_{j}∥^{2} + ∑_{j=ñ+1}^{ñ+ȷ−1} ∥f̃_{j}∥^{2}

+ (2^{−4(n_{m}−1)n} + ⋯ + 2^{−(4(n_{m}−ȷ+1)n}) Σ^{2} ≤ (ε_{2} + \frac{2^{−4(n_{m}+1−ȷ)n}}{1 − 2^{−4n}} ) Σ^{2} . (3.18)

We know that none of these μ̃_{ȷ} Jacobi transformations has affected any of the elements of f̃_{ñ+ȷ}^{(k)}. Therefore

f̂_{n̂+ȷ} = f̃_{ñ+ȷ} .  (3.19)

We also know that the later transformations, defined by c_{m,ȷ+1}, …,c_{m,n_{m}}, will not affect the

ȷ’th column of A_{m−1,m}^{(M̂+ñ−n_{m−1})}.

So, let us consider the transformations which do affect f̂_{n̂+ȷ} and these are those which annihilate the elements at positions given in c_{m,ȷ}.

For 1 ≤ k ≤ ñ − n_{m−1}, let

F̂^{(k)} = [A_{m−1,1}^{(M̂+k)}, A_{m−1,2}^{(M̂+k)}, …, A_{m−1,m}^{(M̂+k)}] = [f̂_{1}^{(k)}, f̂_{2}^{(k)}, …, f̂_{n}^{(k)}].

We can apply Proposition 3.2(ii) to E_{ñ+ȷ}^{T}ÂE_{ñ+ȷ}, with r = ñ − n_{m−1}, to obtain

∥f̂_{ñ+ȷ}^{(ñ−n_{m−1})}∥ ≥ [\frac{2^{−(ñ−n_{m−1})}}{n_{m−1}} ]^{1/2} ∥f̂_{ñ+ȷ}∥ − [\frac{ñ − n_{m−1}}{2} ]^{1/2} [ ∑_{i=1}^{ñ−n_{m−1}} ∥f̂_{i}∥^{2}]^{1/2}

≥ \frac{2^{− \frac{n−3}{2}}}{\sqrt{n_{m−1}}} ∥f̃_{ñ+ȷ}∥ − [\frac{ñ − n_{m−1}}{2} ]^{1/2} [ε_{2} + \frac{2^{−4(n_{m}+1−ȷ)n}}{1 − 2^{−4n}} ]^{1/2} Σ .

Here we have used (3.19), (3.18) and ñ − n_{m−1} = n − n_{m} − n_{m−1} ≤ n − 2 − 1. If we require

ε_{2} + \frac{2^{−4(n_{m}+1−ȷ)n}}{1 − 2^{−4n}} ≤ 2 · 2^{−4(n_{m}+1−ȷ)n},  (3.20)

we obtain

∥f̂_{ñ+ȷ}^{(ñ−n_{m−1})}∥ ≥ \frac{2^{− \frac{n−3}{2}}}{\sqrt{n_{m−1}}} ∥f̃_{ñ+ȷ}∥ − \sqrt{ñ − n_{m−1}} 2^{−2(n_{m}+1−ȷ)n} Σ .

Now, we consider the two possible cases: ȷ < n_{m} and ȷ = n_{m}.

If ȷ < n_{m}, then (3.17) implies

∥f̂_{ñ+ȷ}^{(ñ−n_{m−1})}∥ ≥ \frac{2^{−2(n_{m}+1−ȷ)n}}{\sqrt{n_{m−1}}} [2^{− \frac{n−3}{2}} 2^{2n} − \frac{ñ}{2}]Σ ≥ \frac{2^{−2(n_{m}+1−ȷ)n}}{\sqrt{n_{m−1}}} [2^{\frac{3}{2} n+ \frac{3}{2}} − \frac{n − 2}{2}]Σ .

Here we have used the fact that n_{m−1}(ñ − n_{m−1}) ≤ ñ^{2}/4 and ñ ≤ n − 2.

If ȷ = n_{m}, then (3.17) implies

∥f̂_{ñ+ȷ}^{(ñ−n_{m−1})}∥ ≥ \frac{2^{− \frac{n−3}{2}} (1 − 2^{−n+1})}{\sqrt{n_{m−1}}}Σ − \sqrt{ñ − n_{m−1}}2^{−2n}Σ
≥ \frac{2^{−2n}}{\sqrt{n_{m−1}}} [\frac{7}{8}2^{\frac{3}{2} n+ \frac{3}{2}} − \frac{n − 2}{2}] Σ .

Here we have used the inequality 2^{−n+1} ≤ 1/8 since n ≥ 4.

Taking into account (3.20), we can conclude that, if

ε_{2} ≤ \frac{1 − 2^{−4n+1}}{1 − 2^{−4n}} 2^{−4n_{m}n},  (3.21)

then

∥f̂_{ñ+ȷ}^{(ñ−n_{m−1})}∥ ≥ α_{n,m_{n},n_{m−1}}Σ , α_{n,m_{n},n_{m−1}} = \frac{2^{−2n_{m}n}}{\sqrt{n_{m−1}}} [\frac{7\sqrt{2}}{4}2^{\frac{3}{2} n} − \frac{n − 2}{2}]

holds for all possible choices of ȷ.

As we have noted, the later transformations, defined by c_{m,ȷ+1}, …,c_{m,n_{m}} do not af-

fect the ȷ’th column of A_{m−1,m}^{(M̂+ñ−n_{m−1})}, so f̃_{ñ+ȷ}^{((ñ−n_{m−1})n_{m})} = f̂_{ñ+ȷ}^{(ñ−n_{m−1})}. The subsequent

n_{m}(n_{m} − 1)/2 rotations which annihilate the off-diagonal elements of A_{mm}^{(k)} do not change the Frobenius norm of Ã^{((ñ−n_{m−1})n_{m})}. Therefore, if (3.21) holds, then

∥A_{m−1,m}^{(M̄)}∥_{F} ≥ α_{n,m_{n},n_{m−1}}Σ ,  (3.22)

where

M̄ = M − n_{m−1}n_{m} − \frac{n_{m}(n_{m} − 1)}{2} .

We complete the considerations in Stage 1 by making some preparations for Stage 2. Let r be the smallest positive integer such that

α_{n,m_{n},n_{m−1}}^{2} ≥ \frac{2^{−rn}}{1 − 2^{−2n}} .

Obviously, r depends on n_{m−1} and n_{m}. Since n_{m} ≤ n − 2, we have

α_{n,m_{n},n_{m−1}} ≥ \frac{2^{−2(n−2)n}}{\sqrt{n − 2}} [\frac{7\sqrt{2}}{4} · 2^{\frac{3}{2} n} − \frac{n − 2}{2}] .

Running in MATLAB the following simple program (m-file),

 format long e;
   for n=4:100
   x=2^(n);
   y=((7/4)*sqrt(2/(n-2))*x*sqrt(x)-sqrt(n-2)/2);
   z=x^(1.46)/sqrt(1-x^(-2));
   display([n,y,z,y-z])
 end

one finds out that all y-z are positive. Since for larger n, (n−2)/2 is negligible compared to 2^{(3/2)n}, we have shown that r ≤ 4n − 10.

Now, we can conclude that there is some ȷ, not necessarily the same as earlier, such that

∥f̄_{ñ+ȷ}∥^{2} ≥ 2^{−(2(n_{m}−ȷ)+r)n} Σ^{2} .  (3.23)

Indeed, on the contrary we would have

∥A_{m−1,m}^{(M̄)}∥_{F}^{2} = ∑_{j=1}^{n_{m}} ∥f̄_{ñ+j}∥^{2} < ∑_{j=1}^{n_{m}} 2^{−(2(n_{m}−ȷ)+r)n} · Σ^{2}
= 2^{−rn} [2^{−2(n_{m}−1)n} + 2^{−2(n_{m}−2)n} + ⋯ + 1] Σ^{2}
= 2^{−rn} \frac{1 − 2^{−2n_{m}n}}{1 − 2^{−2n}} Σ^{2} < \frac{2^{−rn}}{1 − 2^{−2n}} Σ^{2} ≤ α_{n,m_{n},n_{m−1}}^{2}Σ^{2} ,

which contradicts (3.22). Let ȷ be the smallest index satisfying (3.23).

For 1 ≤ k ≤ M − M̄, let Ā^{(k)} = (A_{ij}^{(M̄+k)}). Then Ā = Ā^{(0)} is the matrix appearing at the beginning of Stage II.

Stage II

Note that the rotations applied to A^{(k)} for M̃ ≤ k ≤ M̄ have not changed any element of A_{m−1,m−1}^{(k)}, so S^{2}(Ā_{m−1,m−1}) = ε_{3}Σ^{2}. Let G^{(k)} = (g_{pq}^{(k)}) with 1 ≤ p, q ≤ n_{m−1} + n_{m}, be defined by

G^{(k)} = [ \begin{matrix}G_{11}^{(k)} & G_{12}^{(k)} \\ G_{21}^{(k)} & G_{22}^{(k)} \end{matrix} ] = [ \begin{matrix}Ā_{m−1,m−1}^{(k)} & Ā_{m−1,m}^{(k)} \\ Ā_{m,m−1}^{(k)} & Ā_{mm}^{(k)} \end{matrix} ] , 0 ≤ k ≤ M − M̄,

and let G = G^{(0)}. We shall now estimate the contribution to the off-norm reduction coming from the last M − M̄ Jacobi steps. We can pay our attention to the matrices G^{(k)}, since the sum of squares of other off-diagonal elements of Ā^{(k)} remains invariant during these transformations.

The method applies Jacobi rotations in a column-wise fashion, following the ordering defined by c′_{j1}, c′_{j2}, c′′_{j2} …, c′_{jn_{j}}, c′′_{jn_{j}}. Let

ν_{j} = ν_{j−1} + n_{m−1} + j − 1, 1 ≤ j ≤ n_{m}, ν_{0} = 0,

and let G_{j}^{(k)} be the leading j × j submatrix of G^{(k)}. Let g_{2}^{(k)}, g_{3}^{(k)}, …,g_{n_{m−1}+n_{m}}^{(k)} be the

columns of the strictly upper-triangle of G^{(k)}, i.e. g_{j}^{(k)} = [g_{1j}^{(k)}, g_{2j}^{(k)}, …, g_{j−1,j}^{(k)}]^{T} and let g_{j} = g_{j}^{(0)}. Because of (3.23), it is obvious that

∥g_{n_{m−1}+ȷ}∥^{2} ≥ ∥f̄_{ñ+ȷ}∥^{2} ≥ 2^{−(2(n_{m}−ȷ)+r)n}Σ^{2} ,

holds. Note that ȷ is the smallest integer satisfying the second inequality. Let us redefine ȷ, to be the smallest of the numbers in the set {1, 2, …, n_{m}}, satisfying

∥g_{n_{m−1}+ȷ}∥^{2} ≥ 2^{−(2(n_{m}−ȷ)+r)n}Σ^{2} .

Since the Jacobi rotations cannot increase the off-norm, this assumption yields

S^{2}(G_{n_{m−1}+ȷ−1}^{(ν_{ȷ−1})}) ≤ S^{2}(G_{11}^{(0)}) + ∑_{j=1}^{ȷ−1} ∥g_{n_{m−1}+j}∥^{2} ≤ ε_{3}Σ^{2} + \frac{2^{−(2(n_{m}−ȷ+1)+r)n}}{1 − 2^{−2n}} Σ^{2} .

Here, the empty sum is considered zero.

Now, consider the contribution to the off-norm reduction coming from the annihilations in the vector g_{n_{m−1}+ȷ}^{(ν_{ȷ−1})}. Applying Proposition 3.2(i) to G_{n_{m−1}+ȷ}^{(ν_{ȷ−1})}, we obtain

[ ∑_{i=1}^{n_{m−1}+ȷ−1} |g_{i,n_{m−1}+ȷ}^{(ν_{j−1}+i−1)}|^{2}]^{1/2} ≥ \{[\frac{2^{−(n_{m−1}+ȷ−2)}}{n_{m−1} + ȷ − 1} 2^{−(2(n_{m}−ȷ)+r)n}]^{1/2}

− [\frac{n_{m−1} + ȷ − 2}{4} (ε_{3} + \frac{2^{−(2(n_{m}−ȷ+1)+r)n}}{1 − 2^{−2n}} )]^{1/2} \} Σ ≥ \frac{2^{−(n_{m}−ȷ+1+ \frac{r}{2} )n}}{\sqrt{n_{m−1} + n_{m} − 1}}

· \{2^{n+1− \frac{n_{m−1}+nm}{2}} − \frac{n_{m−1}+n_{m}-1}{2} [2^{(2(n_{m}−ȷ+1)+r)n}ε_{3} + \frac{1}{1 − 2^{−2n}} ]^{1/2}\} Σ .

To simplify the expression under the square root, we can require

ε_{3} ≤ \frac{1 − 2^{−2n+1}}{1 − 2^{−2n}} 2^{−(2n_{m}+r)n} .  (3.24)

Then the expression under the square root is not larger than 2 and we have

[ ∑_{i=1}^{n_{m−1}+ȷ−1} |g_{i,n_{m−1}+ȷ}^{(ν_{j}+i−1)}|^{2}]^{1/2} ≥ \frac{2^{−(n_{m}−ȷ+1+ \frac{r}{2} )n}}{\sqrt{n_{m−1} + n_{m}}} [2^{\frac{n}{2} +1} − \frac{n_{m−1} + n_{m}}{\sqrt{2}} ] Σ

≥ \frac{2^{−(n_{m}+ \frac{r}{2} )n}}{\sqrt{n_{m−1} + n_{m}}} [2^{\frac{n}{2} +1} − \frac{n_{m−1} + n_{m}}{\sqrt{2}} ] Σ ≡ \sqrt{θ_{n_{m−1},n_{m}}(n)} Σ > 0 , (3.25)

with θ_{n_{m−1},n_{m}}(n) > 0. Looking back at the relations (3.5), (3.6), (3.15), (3.21) and (3.24), we can conclude that (3.25) holds provided that

ε ≤ 2^{−(2n_{m}+r+1)n} .

Thus, during the last M − M̄ Jacobi steps, S^{2}(Ā) has decreased by the amount not smaller than θ_{n_{m−1},n_{m}}(n)Σ^{2}. Hence

S^{2}(A^{(M)}) ≤ \{ \begin{matrix}[1 − θ_{n_{m−1},n_{m}}(n)] Σ^{2} if ε ∈ [0, 2^{(−2n_{m}+r+1)n}] \\ [1 − ε(1 − t(M̃) ; ñ)] Σ^{2} if ε ∈ [2^{(−2n_{m}+r+1)n} , 1] \end{matrix} .

Since r < 4n − 10, we can complete the proof by setting

t_{n}^{(M)} = max{[1 − 2^{−(4n+2n_{m}−9)n}(1 − t(M̃) ; ñ) , 1 − θ_{n_{m−1},n_{m}}(n)} .

Remark 3.5. Theorem 2.1 holds even if in [6, Algorithm 1] one dynamically combines the cases k = 0 and k = 1, that is to say if some diagonal blocks are operated twice and some are operated once. Indeed, the proof can use the same induction per block-columns. If A_{rr} is operated once, then the appropriate equivalent pivot strategy within this block-column is simply the column-wise one and the proof of the induction step is similar as in the case (a).

Acknowledgements. The author is thankful to Z. Drmač and D. Kressner, and especially to N. Higham and the anonymous referees for reading and improving the paper.

REFERENCES

[1] J. Demmel and K. Veselić, Jacobi’s method is more accurate than QR, SIAM J. Matrix Anal. Appl. 13 (1992), pp. 1204–1245.

[2] J. Dongarra, I. Duff, D. Sorensen and H. van der Vorst, Solving Linear Systems on Vector and Shared Memory Computers, SIAM 1991.

[3] Z. Drmač, Implementation of Jacobi rotations for accurate singular value computation in floating-point arithmetic, SIAM J. Sci. Comp. 18 (1997), pp. 1200–1222.

[4] Z. Drmač, A posteriori computation of the singular vectors in a preconditioned Jacobi SVD algorithm, IMA J. Numer. Anal. 19 (1999), pp. 191-213.

[5] Z. Drmač and K. Veselić, New fast and accurate Jacobi SVD algorithm I, LAPACK Working note 169, 2005.

[6] Z. Drmač and K. Veselić, New fast and accurate Jacobi SVD algorithm II, LAPACK Working note 170, 2005.

[7] K. V. Fernando, Linear Convergence of the Row Cyclic Jacobi and Kogbetliantz Methods, Numer. Math. 56 (1989) 73–94.

[8] E. R. Hansen, On Jacobi Methods and Block Jacobi Methods for Computing Matrix Eigenvalues, Ph. D. thesis, Stanford University 1960.

[9] E. R. Hansen, On cyclic Jacobi methods, SIAM J. Appl. Math. 11 (1963), pp. 449–459.

[10] V. Hari, On the Convergence of Cyclic Jacobi–like Processes, Linear Algebra and Its Applications 81 (1986), pp. 105–127.

[11] V. Hari, On sharp quadratic convergence bounds for the serial Jacobi methods, Numer. Math. 60 (1991), pp. 375–406.

[12] V. Hari and K. Veselić, On Jacobi Methods for Singular Value Decompositions, SIAM J. Sci. Stat. Comp., Vol. 8, No.5 (1987), pp. 741–754.

[13] P. Henrici and K. Zimmermann, An Estimate for the Norms of Certain Cyclic Jacobi Operators, Linear Algebra and Its Applications 1 (1968), pp. 489–501.

[14] Mascarenhas W.: On the convergence of the Jacobi method for arbitrary orderings. SIAM J. Matrix Anal. Appl., Vol. 16, No.˙4, (1995), pp. 1197-1206.

[15] L. Nazareth, On the Convergence of the Cyclic Jacobi Method, Linear Algebra and Its Applications 12 (1975), pp. 151–164.

[16] N. Rhee and V. Hari, On the global and cubic convergence of a quasy-cyclic Jacobi method, Numer. Math. 66 (1993), pp. 97–122.

[17] G. Shroff and R. Schreiber, On the Convergence of the Cyclic Jacobi Method for Parallel Block Orderings, SIAM J. Matrix Anal. Appl. 10 (1989), pp. 326–346.

[18] K. Veselić and V. Hari, A note on a one-sided Jacobi algorithm, Numer. Math. 56 (1989), pp. 627-633.

[19] J. Wilkinson, Note on the quadratic convergence of the cyclic Jacobi process, Numer. Math. 4 (1962), pp. 296–300.