4
$\begingroup$

I'm using SIMD processor arrays to compute the eigen-decomposition for large numbers of small (up to $32\times 32$) matrices. For assorted technical reasons, Jacobi iteration maps well to the SIMD architecture and gives excellent results for diagonalisation of symmetric, Hermitian and normal matrices using unitary similarity transformations.

I've extended the technique to compute the Schur triangular form of general complex matrices using the same unitary similarity transformations in order to obtain the eigenvalues from the diagonal. Again, convergence to the Schur form is typically excellent for most random complex matrices up to $32\times 32$ size but I observe very poor convergence for a small number of random matrices. As I increase the size of the number of random matrices tested to thousands, tens of thousands, millions, the number of Jacobi iterations required increases indefinitely.

Is there some form of pre-conditioning that can improve convergence? I've tried an initial reduction to upper Hessenberg (i.e. almost triangular) with no improvement.

$\endgroup$
  • $\begingroup$ Can you clarify the last sentence: do you increase the number of matrices tested or the size of them? Also, is it possible to have some info about the matrices that behave well, and ones that do not? For example, plot of their singular values. $\endgroup$ – Anton Menshov Nov 29 '18 at 15:37
  • 1
    $\begingroup$ The SIMD array processes 256 matrices in parallel but due to the nature of SIMD one cannot converge each matrix individually. The entire batch of 256 matrices are given the same over-cautious number of Jacobi iterations selected to ensure convergence of all the matrices. It is this "worst case" number of iterations that increases the more matrices of any size I look at. $\endgroup$ – Mark Pedley Nov 29 '18 at 15:42
  • 1
    $\begingroup$ The Jacobi scan pattern is also relevant but doesn't solve the worst case convergence problem: see "On Asymptotic Convergence of Nonsymmetric Jacobi Algorithms”, Christian Mehl, SIAM J. Matrix Anal. & Appl., 30(1), 291–311 ". . I haven't characterized the troublesome random matrices by singular values. $\endgroup$ – Mark Pedley Nov 29 '18 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.