4
$\begingroup$

I have a set of left and right eigenvectors from an nonsymmetric eigenproblem, and I'd like to biorthogonalize them.

I tried Gram-Schmidt, but this fails for most cases.

I then read that the SVD is the best way to get an orthonormal basis for a matrix, where U would be my basis.

How can I extend the SVD to the case of two sets of eigenvectors? Or is there a better way to biorthogonalize my left and right eigenvectors?

EDIT: More details

I have a complex, non-Hermitian matrix,

$\qquad\mathbf{M} = \left[\begin{array}{cc} \mathbf{A} & \mathbf{B} \\ -\mathbf{B^*} & -\mathbf{A^*}\end{array}\right]$

Where $*$ indicates conjugate transpose. I solve via ZGEEV for the left and right eigenvectors, so I have

$\qquad\mathbf{MX_R} = \mathbf{X_RE}\qquad$ and $\qquad \mathbf{X_LM} = \mathbf{EX_L}\qquad$

Where $\mathbf{E}$ is a diagonal matrix of eigenvalues, and $\mathbf{X_L}$ and $\mathbf{X_R}$ are matrices containing my left and right eigenvectors, respectively.

I can easily orthogonalize the right and left eigenvectors among themselves, i.e. $\mathbf{X_R^*}\cdot\mathbf{X_R} = \mathbf{I}$ or $\mathbf{X_L^*}\cdot\mathbf{X_L} = \mathbf{I}$, but what I want is to biorthonormalize them to each other, e.g. obtain:

$\qquad\mathbf{X_L}\cdot\mathbf{X_R} = \mathbf{I}$

I have written my own modified Gram-Schmidt to accomplish this, but like I said, it does not work for many cases. I cannot see any way of using LAPACK routines (i.e. ZGEQRF followed by ZUNGQR) to accomplish this, nor does using the SVD seem apparent to me.

$\endgroup$
  • $\begingroup$ What is exactly that you want? An orthogonal set of right eigenvectors does not exist in general. Can you write down a formula? $\endgroup$ – Federico Poloni Jan 23 '15 at 8:18
  • $\begingroup$ @FedericoPoloni I've updated my question to explain what I am trying to solve, hopefully this clarifies what I am trying to do! $\endgroup$ – jjgoings Jan 23 '15 at 17:01
  • $\begingroup$ Do you confirm that it's $X_L^*X_R$ and not $X_LX_R$ (which would mean that the left and right eigenvectors are orthogonal to each other)? $\endgroup$ – Federico Poloni Jan 23 '15 at 19:20
  • $\begingroup$ @FedericoPoloni Yes, you are correct. What happens is that the left and right eigenvectors are orthogonal to each other for each unique eigenvalue. Among degenerate eigenvalues, however, the corresponding eigenvectors are not orthogonal to each other. $\endgroup$ – jjgoings Jan 23 '15 at 21:02
  • $\begingroup$ I still don't understand. If you require the columns of $X_R$ and the rows of $X_L$ to be eigenvectors, then in the generic case (distinct eigenvalues) the only freedom you have is scaling, and that won't make non-orthogonal vectors orthogonal. Or do you want to allow linear combinations of eigenvectors (preserving only their span)? What is exactly the allowed set of transformations? $\endgroup$ – Federico Poloni Jan 23 '15 at 21:19
1
$\begingroup$

I guess, the final result is suffering from instability (relative) of Gram-Schmidt, even in modified/stabilized forms. In this case, instead of going from the start: modifying the orthogonalization process, we can start with the final result instead.

So, after solving a non-Hermitian eigenvalue problem (with a reliable algorithm), we obtained $X_L$ and $X_R$, matrices of left and right eigenvectors, respectively.

We desire $$X_LX_R=I$$ however, $$X_LX_R=Y$$ where matrix $Y$ is unfortunately different from the identity $I$. Now, we can compute the LU decomposition (which is supposed to be much more numerically stable than Gram-Schmidt) for $Y=L_YU_Y$. $$ X_LX_R=L_YU_Y $$

Now, by solving two triangular systems with multiple RHSs via forward- (for $L_Y$) and back-substitution (for $U_Y$): $$ L_YX_L^\prime=X_L\\ X_R^\prime U_Y = X_R $$ we can solve for the biorthogonalized $X_L^\prime$ and $X_R^\prime$ via an also relatively stable numerical process.

So, the algorithm (definitely not the best in terms of computational complexity):

  1. Compute $Y=X_LX_R$
  2. Compute LU-decomposition of $Y$
  3. Solve 2 triangular systems with multiple RHSs to obtain the final result of biorthogonolized matrices.

There is a small question of what happens if a set of eigenvectors is degenerate, but I don't see why LU should fail in that case either.

$\endgroup$
  • $\begingroup$ Only problem is, in general $X_L'$ and $X_R'$ will no longer be matrices of eigenvectors. For that to be the case one would have to ensure that $Y$ is block-diagonal with the diagonal blocks corresponding to eigenspaces. $\endgroup$ – Dr. Lutz Lehmann May 4 '18 at 9:16

Your Answer

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

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