2
$\begingroup$

What are the general algorithms used for diagonalization of large Hermitian matrices and Unitary matrices? ($>5000 \times 5000$)

LAPACK seems to diagonalize Hermitian matrices almost 20 times as fast as unitary matrices, and as far as I know, the routines are also different. How is the computational complexity calculated in each case?

If there is a review article which answers my questions please point me in that direction.

Improve this question
$\endgroup$
1
  • $\begingroup$ The one who downvoted me, please help me out to find a proper forum to ask this question. I really need a reference. $\endgroup$
    – Roopayan Ghosh
    Commented Oct 30, 2020 at 15:48

1 Answer 1

Reset to default
4
$\begingroup$

LAPACK doesn't have a specialized routine for computing the eigenvalues of a unitary matrix, so you'd have to use a general-purpose eigenvalue routine for complex non-hermitian matrices. This is slower than using a routine for the eigenvalues of a complex hermitian matrix, although I'm surprised that you're seeing a factor of 20 difference in run times.

However, there are algorithms that have been developed for the efficient computation of the eigenvalues of a unitary matrix. See for example:

Gragg, William B. "The QR algorithm for unitary Hessenberg matrices." Journal of Computational and Applied Mathematics 16, no. 1 (1986): 1-8.

David, Roden JA, and David S. Watkins. "Efficient implementation of the multishift QR algorithm for the unitary eigenvalue problem." SIAM journal on matrix analysis and applications 28, no. 3 (2006): 623-633.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for the references, I shall check them out. Yes I know I have to use the diagonalization for general purpose matrices for LAPACK. Barring the official documentation of LAPACK which I am sure is there somewhere, are there any references which discuss the routines in a verbose manner? $\endgroup$
    – Roopayan Ghosh
    Commented Nov 1, 2020 at 7:58
  • $\begingroup$ The LAPACK user's guide is online at: netlib.org/lapack/lug/lapack_lug.html $\endgroup$
    – Brian Borchers
    Commented Nov 1, 2020 at 16:16
  • $\begingroup$ Actually reading the documentation, I think what was happening is it was using the RRR method for the hermitian matrix which gave a huge speedup. I was using Mathematica so while I know they are using LAPACK, I did not know what particular algorithm they were using. Thank you for the help. $\endgroup$
    – Roopayan Ghosh
    Commented Nov 3, 2020 at 5:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.