Block recursive algorithm to generate Jacobi-sets

DOI10.1016/0167-8191(93)90001-2MaRDI QIDQ1801367zbMATH OpenOpenAlexFDO

Authors Mythili Mantharam, P. J. Eberlein

Publication date 9 December 1993

Published in Parallel Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-8191(93)90001-2

zbMATH Keywords

block recursive algorithmcomplete Jacobi setsconvergenceeigenvaluesGao-Thomas algorithmhypercubeJacobi-type methodsodd-even orderingparallel implementationrecursive algorithmsingular values

Mathematics Subject Classification ID

Iterative numerical methods for linear systems (65F10) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Parallel numerical computation (65Y05)

Review text

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.

Recommendations

• Block recursive computation of generalized inverses
• On block recursions, Askey's sieved Jacobi polynomials and two related systems
• Block-iterative algorithms
• AN ALGORITHM FOR CONSTRUCTING BLOCKING SETS FOR PROJECTIVE PLANES
• On Jacobi-Perron algorithm
• Algorithm for solving Jordan problem of block Schur form
• scientific article; zbMATH DE number 1283876
• The Jacobi symbol algorithm
• scientific article; zbMATH DE number 3107753
• scientific article; zbMATH DE number 3104004

Cited in

(7)

• New Jacobi-sets for parallel computations
• On Parallel Jacobi Orderings
• scientific article; zbMATH DE number 782082 (Why is no real title available?)
• scientific article; zbMATH DE number 1424567 (Why is no real title available?)
• The LAPW method with eigendecomposition based on the Hari-Zimmermann generalized hyperbolic SVD
• Vectorization of a Thread-Parallel Jacobi Singular Value Decomposition Method
• On convergence and accuracy of the J-Jacobi method under the de Rijk pivot strategy

This page was built for publication: Block recursive algorithm to generate Jacobi-sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1801367)