On the Convergence of the Cyclic Jacobi Method for Parallel Block Orderings
Gautam M. Shroff, Robert Schreiber · SIAM Journal on Matrix Analysis and Applications · 1989
Convergence of the cyclic Jacobi method for diagonalizing a symmetric matrix has never been conclusively settled. Forsythe and Henrici [Trans. Amer. Math. Soc., 94(1960), pp. 1–23] proved convergence for a cyclic by rows ordering. Here orderings are investigated that can be obtained from the cyclic by rows ordering through convergence preserving combinatorial transformations. First the class of “cyclic wavefront” orderings is introduced and it is shown that the class consists of exactly those orderings that are “equivalent” to the cyclic by rows ordering. It is also shown that certain block Jacobi methods are cyclic wavefront orderings when viewed as cyclic Jacobi methods. While discussing convergence proofs for parallel implementations of Jacobi methods and block Jacobi methods, the notions of “weak equivalence” and “P-equivalence” of Jacobi orderings is developed. Next the class of “P-wavefront” orderings is introduced that includes all orderings related to the cyclic by rows ordering through any known convergence preserving transformations. Finally, it is shown that the “P-wavefront” orderings are characterized by simple properties that can be verified efficiently (in polynomial time).