# Left and right eigenspaces of the product of Gramians

I solve the Lyapunov equations :

$$A W_C E^T + E W_C A^T + B B^T = 0$$ $$A^T W_O E^T + E W_O A + C^T C = 0$$

to obtain $W_C$ and $W_O$. My aim is to get the left and right eigenspaces of $W_C W_O$. This is basically for model order reduction through balanced truncation.

Currently I am explicitly generating $W_C$ and $W_O$, and calculating the schur decomposition as

W_c = lyap(A,B*B',[],E);
W_o = lyap(A',C'*C,[],E);
W_j = W_c*W_o;
[Vs,Ts] = schur(W_j);
Vst = Vs';
V_lk = Vst(:,1:ordr);
V_rk = Vs(:,1:ordr);


How can I optimize the process of calculating the dominant eigenspaces? Links to some theory behind any techniques will be very helpful.

Additional Information : I am aware of ADI, and read quite a few of the papers based on it. However, there are 2 problems with it being applicable to my case.

1. My original system is dense, a product of another model reduction. Isn't ADI specific to Sparse systems?
2. My grammians will NOT be positive definite, because its not fully controllable/observable. They are in-fact indefinite (negative and positive) eigenvalues. Therefore Cholesky factor is not applicable. Is there a different factorization I could use with ADI?
• To clarify, by "dominant" you mean the eigenvalues of largest magnitude? And you only want a few of the biggest ones, for which computing the Schur decomposition is overkill? – Daniel Shapero Jun 4 '13 at 14:08
• Yes. To be exact, I want to obtain the vectors representing spaces spanned by the eigenvectors corresponding to some k largest eigenvalues. If not Schur, how best? Can you point me to some smarter methods? Thanks. – Milind R Jun 8 '13 at 11:41
• The input to this reduction is a system originally of order ~10k, reduced to 200 by a different method. – Milind R Jun 17 '13 at 16:35
• Regarding (2) @FedericoPoloni is right. Semi-definiteness is even welcomed in ADI, as one looks for low-rank factors. However, I am not sure about indefiniteness. Peter Benner does not give conditions for convergence but refers the reader to earlier papers by Wachspress on ADI. – Jan Jun 19 '13 at 7:25
• Maybe I am making a silly mistake, but this should be a proof that ADI works also if the Gramian is semidefinite: (1) use Kalman decomposition $A=\begin{bmatrix}A_{11} & A_{12}\\\\ 0 & A_{22}\end{bmatrix}$, $B=\begin{bmatrix}B_1\\\\0\end{bmatrix}$; (2) notice that the second block never gets altered, so you could as well work on $(A_{11}, B_1)$ (3) This pair is controllable, so ADI works. As for indefinite, I don't know. – Federico Poloni Jun 19 '13 at 7:48

One of the best-performing methods for solving large-scale Lyapunov equations is ADI. It is an iterative algorithm that returns an approximate low-rank decomposition $X \approx VV^T$ of the solution $X$. In this case, you can work with this decomposition of both Gramians to reduce the eigenproblem to a smaller one.
However, as a basic assumption they have $A$ always Hurwitz, what would render the Gramians definite (if E is positive definite).