A quadratically convergent parallel Jacobi process for diagonally dominant matrices with distinct eigenvalues (Q1822898)

Some algorithms, considered unfavorable on a single processor sequential computer, may be excellent on a distributed computing system. In the Jacobi algorithm the computational capacity can be increased by exploiting it inherent parallelism. Especially the Jacobi algorithms for the symmetric eigenvalue problem and those for the singular-value problem are particularly amenable to parallel implementation. This paper describes a new Jacobi-like process for diagonalization of a nonnormal diagonal dominant matrix \(A\in {\mathbb{C}}^{n\times n}\) with distinct eigenvalues, where n is assumed to be even. In each iteration \(A^{(k+1)}=S_ k^{-1}A^{(k)}S,\) \(k\geq 0\), n/2 pairs of symmetrically placed off-diagonal elements are annihilated in a parallel fashion. Divide \(A^{(k)}\) into a diagonal and a nondiagonal part, \(D^{(k)}\) and \(E^{(k)}\), respectively. Set \(\epsilon_ k=\| E^{(k)}\|_ F\) and \(\theta_ k=\min_{i\neq j}| a^{(k)}_{i,i}-a^{(k)}_{j,j}|.\) The separation of the eigenvalues \(\lambda_ 1,...,\lambda_ n\) is denoted by \(\eta\) : \(\eta\) \(=\min_{i\neq j}| \lambda_ i-\lambda_ j|\). Matrix \(A\in {\mathbb{C}}^{n\times n}\) is called to be diagonally dominant with respect to separation \(\eta\) if \(\| E^{(0)}\|_ F\leq c\eta\) for some \(c<1/2.\) Section 2 presents the parallel annihilators together with their properties and effects during the first step. Section 3 describes the consequences of the annihilations in a complete sweep and proves the quadratic convergence property: if \(\epsilon_ 0\leq (1/10)\eta /n\), then \(\epsilon_{n-1}\leq (1.7n+0.6)\epsilon^ 2_ 0/\eta \leq 0.2\epsilon_ 0.\) Section 4 discusses numerical examples and Section 5 gives concluding remarks about parallelism and implementation.