A quadratically convergent parallel Jacobi process for diagonally dominant matrices with distinct eigenvalues
type: Item
instance of: scholarly article
title: A quadratically convergent parallel Jacobi process for diagonally dominant matrices with distinct eigenvalues
zbMATH Open document ID: 0679.65024
DOI: 10.1016/0377-0427(89)90358-0
author: M. H. C. Paardekooper
published in: Journal of Computational and Applied Mathematics
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 65F15
Mathematics Subject Classification ID: 65Y05
zbMATH DE Number: 4113853
zbMATH Keywords: quadratic convergence
zbMATH Keywords: parallel algorithm
zbMATH Keywords: parallel processor
zbMATH Keywords: Jacobi algorithm
zbMATH Keywords: symmetric eigenvalue problem
zbMATH Keywords: singular-value problem
zbMATH Keywords: diagonalization
zbMATH Keywords: nonnormal diagonal dominant matrix
zbMATH Keywords: numerical examples
MaRDI profile type: Publication
full work available at URL: 0377-0427(89)90358-0
OpenAlex ID: W3023459790
cites work: Norms and exclusion theorems
cites work: The Solution of Singular-Value and Symmetric Eigenvalue Problems on Multiprocessor Arrays
cites work: Q3730938
cites work: A Jacobi-Like Method for the Automatic Computation of Eigenvalues and Eigenvectors of an Arbitrary Matrix
cites work: On the Schur Decomposition of a Matrix for Parallel Computation
cites work: On measures of nonnormality of matrices
cites work: On the convergence of the classical Jacobi method for real symmetric matrices with non-distinct eigenvalues
cites work: On the quadratic convergence of the special cyclic Jacobi method
cites work: Q5607531
cites work: An eigenvalue algorithm for skew-symmetric matrices
cites work: On the quadratic convergence of a generalization of the Jacobi Method to arbitrary matrices
cites work: On Jacobi and Jacobi-Like Algorithms for a Parallel Computer
cites work: Zur quadratischen Konvergenz des Jacobi-Verfahrens.(On quadrative convergence of the Jacobi method)
cites work: A Jacobi-Like Algorithm for Computing the Schur Decomposition of a Nonhermitian Matrix
cites work: Note on the quadratic convergence of the cyclic Jacobi process
cites work: Almost diagonal matrices with multiple or close eigenvalues
description: scientific article; zbMATH DE number 4113853