I have some results from applying right-preconditioned CGLS to the damped normal equations $(A^TA + \alpha^2I)\ \mathbf{x}=A^T\mathbf{b}$. I'm trying to find the condition numbers of the preconditioned systems, or even better, their eigenvalues. My matrix $A$ is a $65,536\times 65,536$ Kronecker product $A_1\otimes A_2$ where $A_1\ \text{and} \ A_2$ are $256\times 256$. All my matrices are sparse.

The preconditioners I have applied have been the diagonals of both $A^TA$ and $A^TA + \alpha^2I$, and incomplete Cholesky factorizations of these same two matrices.

Attempted solutions

I can't calculate a lower bound on the condition number in any good time by using the function 'condest' in Matlab. Using the 'eigs' function, although I can get the largest eigenvalue, the smallest still isn't found within 30 minutes.

  • I have tried to write $A^TA + \alpha^2I$ as a Kronecker product, which would allow me to easily find eigenvalues of at least some of the preconditioned systems (in particular the incomplete Cholesky ones). However, I haven't had any success nor discovered any standard identities that could help me.
  • I've tried storing the inverse of $A^TA+\alpha^2I$ (which is easily obtained using the SVD of $A$) in Matlab, so as to use 'eigs' to calculate the largest magnitude eigenvalue of said inverse. Unfortunatley though I run into memory limitations.

Is there a computational or analytical workaround for this problem I face?

  • $\begingroup$ You could perhpas use the simple iteration $y_{n+1} := Ay_n$. For some nonzero $y_0$ this series converges to the eigenvector with the largest eigenvalue, but it is not very efficient (depending on the distribution of the eigenvalues) $\endgroup$ – flawr Dec 27 '16 at 23:49
  • $\begingroup$ If you can "invert" $A$ using a cholesky decomposition or something similar you could use the same iteration but just on $A^{-1}$ to get the smallest eigenvalue of $A$. $\endgroup$ – flawr Dec 28 '16 at 0:26
  • 1
    $\begingroup$ If $A = U\Sigma V^\top$ then $B = A^\top A + \alpha^2 I = V (\Sigma^2 + \alpha^2 I) V^\top$ and the condition number of $B$ is simply $\kappa = \frac{\sigma_{\max}^2 + \alpha^2}{\sigma_{\min}^2 + \alpha^2}$ $\endgroup$ – uranix Dec 28 '16 at 23:10

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.