[petsc-users] Condition Number and GMRES iteration

[Fande Kong]

Thanks, Matt,

It is a great paper. According to the paper, here is my understanding: for
normal matrices, the eigenvalues of the matrix together with the
initial residual completely determine the GMRES convergence rate. For
non-normal matrices, eigenvalues are NOT the relevant quantities in
determining the behavior of GMRES.

What quantities we should look at for non-normal matrices? In other words,
how do we know one matrix is easier than others to solve?  Possibly they
are still open problems?!

Thanks,

Fande,

On Fri, Feb 7, 2020 at 6:51 AM Matthew Knepley <knepley at gmail.com> wrote:

> On Thu, Feb 6, 2020 at 7:37 PM Fande Kong <fdkong.jd at gmail.com> wrote:
>
>> Hi All,
>>
>> MOOSE team, Alex and I are working on some variable scaling techniques to
>> improve the condition number of the matrix of linear systems. The goal of
>> variable scaling is to make the diagonal of matrix as close to unity as
>> possible. After scaling (for certain example), the condition number of the
>> linear system is actually reduced, but the GMRES iteration does not
>> decrease at all.
>>
>> From my understanding, the condition number is the worst estimation for
>> GMRES convergence. That is, the GMRES iteration should not increases when
>> the condition number decreases. This actually could example what we saw:
>> the improved condition number does not necessary lead to a decrease in
>> GMRES iteration. We try to understand this a bit more, and we guess that
>> the number of eigenvalue clusters of the matrix of the linear system
>> may/might be related to the convergence rate of GMRES.  We plot eigenvalues
>> of scaled system and unscaled system, and the clusters look different from
>> each other, but the GMRRES iterations are the same.
>>
>> Anyone know what is the right relationship between the condition number
>> and GMRES iteration? How does the number of eigenvalue clusters affect
>> GMRES iteration?  How to count eigenvalue clusters? For example, how many
>> eigenvalue clusters we have in the attach image respectively?
>>
>> If you need more details, please let us know. Alex and I are happy to
>> provide any details you are interested in.
>>
>
> Hi Fande,
>
> This is one of my favorite papers of all time:
>
>   https://epubs.siam.org/doi/abs/10.1137/S0895479894275030
>
> It shows that the spectrum alone tells you nothing at all about GMRES
> convergence. You need other things, like symmetry (almost
> everything is known) or normality (a little bit is known).
>
>   Thanks,
>
>       Matt
>
>
>> Thanks,
>>
>> Fande Kong,
>>
>>
>>
>
> --
> What most experimenters take for granted before they begin their
> experiments is infinitely more interesting than any results to which their
> experiments lead.
> -- Norbert Wiener
>
> https://www.cse.buffalo.edu/~knepley/
> <http://www.cse.buffalo.edu/~knepley/>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-users/attachments/20200207/4ff6c85c/attachment-0001.html>