1
$\begingroup$

https://stackoverflow.com

Krylov solvers for iterative computation of the smallest singular value and the corrensponding singular vectors of a matrix

Edit:

This is a follow-up question to How to implement flexible gmres in matlab?.

I am a student and I am working for the topic of "Krylov solvers for iterative computation of the smallest singular value and the corrensponding singular vectors of a matrix". I have found many materials among them and your material. I would like to ask if you can give me the relation between GMRES and the smallest singular value , or the relation between GMRES and the topic.I should do a comparison of GMRES method and LU factorization, but I do not understand. Thank you!

Improve this question
$\endgroup$
3
  • $\begingroup$ Have you taken a look at the book by Saad on iterative solvers for linear systems? $\endgroup$
    – Wolfgang Bangerth
    Jul 9 '20 at 2:31
  • 1
    $\begingroup$ "I have found many materials among them and your material. " Which sources did you check and whose material? $\endgroup$
    – Abdullah Ali Sivas
    Jul 9 '20 at 3:53
  • $\begingroup$ GMRES +ILU find the smallest singular value and the corrensponding vectors? Can you give me an example about GMRES+ ILU? Code in matlab? $\endgroup$
    – Luljeta Hoda
    Jul 9 '20 at 19:32
4
$\begingroup$

How GMRES method finds smallest singular value and the corresponding singular vectors of a matrix?

It doesn't. GMRES solves linear systems. Your citation probably refers to other Krylov methods: restarted Arnoldi, Golub-Kahan bidiagonalization.

Improve this answer
$\endgroup$
0
1
$\begingroup$

I kinda see what you are asking. There is a relationship between singular values of a matrix $A$ and the matrix $A^HA$: $\sigma_i^2(A)=\lambda_i(A^HA)$. So in theory, you can use inverse power method to find $i$-th smallest eigenvalue of the matrix $A^HA$ and the corresponding eigenvector. To 'invert' the matrix $A^HA$ (during inverse power method algorithm) you can use GMRES + some preconditioner. Similarly, you can use LOBPCG, which is a CG method designed to find generalized eigenvalues and eigenvectors. Check the book Numerical Methods for Large Eigenvalue Problems - 2nd Edition by Yousef Saad for more information.

There is also an indirect relationship between singular values of a matrix and GMRES. Turns out that the eigenvalues of a matrix is not a good predictor of convergence of GMRES, it actually might be even deceptive. There is a huge body of work surrounding this idea. Some alternatives suggested are pseudospectra and field of values, both are better predictors. Latter is a set that includes singular values and here is some reading about field of values (or numerical range):

  1. Horn, R.; Johnson, C.R. Matrix Analysis; Cambridge University Press: New York, NY, USA, 1985
  2. Zachlin, P.F. On the Field of Values of the Inverse of a Matrix. Ph.D. Thesis, Case Western Reserve University, Cleveland, OH, USA, 2007.

If anyone else has any references to suggest, you can comment below and I will add to this list.

Improve this answer
$\endgroup$
5
  • $\begingroup$ thank you so much $\endgroup$
    – Luljeta Hoda
    Jul 10 '20 at 7:44
  • $\begingroup$ @LuljetaHoda -- no, restart and preconditioning have nothing to do with each other. You really need to read more before you will be able to use whatever the people here on this forum suggest. I feel like you are still missing of the basics of the area. $\endgroup$
    – Wolfgang Bangerth
    Jul 10 '20 at 15:18
  • $\begingroup$ @abdullah ali sivas: I don't think that the suggestion is to use GMRES as the basis for finding eigenvalues is directed at solving linear systems in an inverse iteration. Rather, there is a relationship between the eigenvalues of the matrix $A$ and the Hessenberg matrix that the GMRES method builds in the course of the iteration. $\endgroup$
    – Wolfgang Bangerth
    Jul 10 '20 at 15:19
  • $\begingroup$ @Wolfgang Bangerth Thank you $\endgroup$
    – Luljeta Hoda
    Jul 10 '20 at 15:27
  • $\begingroup$ @WolfgangBangerth, that is true. In Yousef Saad's book, it is covered under Lanczos method. I was responding the question about GMRES+ILU, I can not imagine another way that would help finding eigenvalues of the original matrix. Because using ILU preconditioning will change the eigenvalues, and the eigenvalues you get from the Hessenberg matrix will not be the eigenvalues of the original matrix. $\endgroup$
    – Abdullah Ali Sivas
    Jul 11 '20 at 5:51

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.