Block recursive algorithm to generate Jacobi-sets (Q1801367): Difference between revisions

Complete Jacobi sets are used in the parallel implementation for Jacobi- type methods which describe algorithms to find either singular values or eigenvalues of arbitrary matrices. In a Jacobi-type method, in each iteration, an off-diagonal element of the matrix is annihilated by a similar transformation with a unitary matrix, until the transformated matrix converges to a canonical form. The order in which the index pairs are chosen is an important aspect of the algorithm. The pairs in the set \(\{(i,j)\mid 1\leq i<j\leq n\}\) can be distributed into \(n-1\) sets (Jacobi sets), such that each contains exactly \(n/2\) disjoint pairs. The paper presents an recursive algorithm for the exchanges of elements on a hypercube configuration to generate complete Jacobi sets. The algorithm is referred to the block recursive algorithm. This is an improvement of the Gao-Thomas algorithm. The new algorithm will return to its initial state after the last Jacobi set has been generated. The algorithm generates all the Jacobi sets in a minimum number of communication steps. The paper also present a comparative study on the effect of different orderings on the convergence, in a Jacobi-type method for a real non- symmetric matrix. The tests indicate that the ordering defined by the block recursive algorithm is as good as the odd-even ordering.