Convergence of iterative solver with initial guess

Question

Hello there, Fenics newbie here.

I'm interested in solving a linear variational problem iteratively, to be precise: i need to access the solution of the k-th iteration cycle and to specify an initial guess for the (k+1)-th iteration cycle.

In my understanding this could be achieved by setting the maximum_iterations to 1 and error_on_noconvergence' to False, and just provide the k-th solution as initial guess for the next cycle (which is again the invocation of a solver with 1 iteration).

I've read this question, and used the provided code for some testing.

A solver (without maximum iterations, default initial guess) converges in 32 iterations.
Now i run (just for testing) solver1 (max. 5 iterations, default initial guess), and provide this solution as initial guess to
solver2 (only one iteration, nonzero initial guess) as solver2.solve(U.vector(), bb) (as described in the linked answer).

Now this last result (returned by solver2) is different from the 6th cycle of the solver without iteration-restrictions (see log below).
I don't quite understand this behavior as I expected the solutions to be the same.

Any thought welcome!
Thanks, andreas

# Call solver without initial guess and iteration restriction
Solving linear system of size 112724 x 112724 (PETSc Krylov solver).
  0 KSP preconditioned resid norm 5.013482974928e+02 true resid norm 1.438923047556e+02 ||r(i)||/||b|| 1.000000000000e+00
  1 KSP preconditioned resid norm 3.627499850684e+02 true resid norm 7.012509237923e+01 ||r(i)||/||b|| 4.873442850077e-01
  1 KSP preconditioned resid norm 4.284493438921e+02 true resid norm 4.916420670210e+01 ||r(i)||/||b|| 3.416736342198e-01
  2 KSP preconditioned resid norm 1.453576783933e+02 true resid norm 2.836341898893e+00 ||r(i)||/||b|| 1.971156069611e-02
  2 KSP preconditioned resid norm 6.665851481251e+01 true resid norm 1.313506692609e+02 ||r(i)||/||b|| 9.128401236187e-01
  3 KSP preconditioned resid norm 3.149081533498e+01 true resid norm 4.175727828253e+01 ||r(i)||/||b|| 2.901981336213e-01
  3 KSP preconditioned resid norm 3.349907518979e+01 true resid norm 2.638011919338e+01 ||r(i)||/||b|| 1.833323834668e-01
  4 KSP preconditioned resid norm 1.980048300408e+01 true resid norm 9.000928921285e+00 ||r(i)||/||b|| 6.255323338225e-02
  4 KSP preconditioned resid norm 2.456755478025e+01 true resid norm 4.251850126511e+01 ||r(i)||/||b|| 2.954883608080e-01
  5 KSP preconditioned resid norm 1.321389278831e+01 true resid norm 1.524133242368e+01 ||r(i)||/||b|| 1.059218034597e-01
  5 KSP preconditioned resid norm 1.223459075120e+01 true resid norm 8.356328766457e+00 ||r(i)||/||b|| 5.807349309368e-02
  6 KSP preconditioned resid norm 7.839782981707e+00 true resid norm 3.877443353249e+00 ||r(i)||/||b|| 2.694684305624e-02
  6 KSP preconditioned resid norm 1.072776447532e+01 true resid norm 9.200977999033e+00 ||r(i)||/||b|| 6.394350284862e-02
 ... until convergence at iteration 32
 32 KSP preconditioned resid norm 1.926136259430e-03 true resid norm 6.334961622827e-05 ||r(i)||/||b|| 4.402571515960e-07
 32 KSP preconditioned resid norm 3.184299649979e-04 true resid norm 2.828744231551e-05 ||r(i)||/||b|| 1.965875962830e-07


# Call solver1 and afterwards solver 2
Solving linear system of size 112724 x 112724 (PETSc Krylov solver).
  0 KSP preconditioned resid norm 5.013482974928e+02 true resid norm 1.438923047556e+02 ||r(i)||/||b|| 1.000000000000e+00
  1 KSP preconditioned resid norm 3.627499850684e+02 true resid norm 7.012509237923e+01 ||r(i)||/||b|| 4.873442850077e-01
  1 KSP preconditioned resid norm 4.284493438921e+02 true resid norm 4.916420670210e+01 ||r(i)||/||b|| 3.416736342198e-01
  2 KSP preconditioned resid norm 1.453576783933e+02 true resid norm 2.836341898893e+00 ||r(i)||/||b|| 1.971156069611e-02
  2 KSP preconditioned resid norm 6.665851481251e+01 true resid norm 1.313506692609e+02 ||r(i)||/||b|| 9.128401236187e-01
  3 KSP preconditioned resid norm 3.149081533498e+01 true resid norm 4.175727828253e+01 ||r(i)||/||b|| 2.901981336213e-01
  3 KSP preconditioned resid norm 3.349907518979e+01 true resid norm 2.638011919338e+01 ||r(i)||/||b|| 1.833323834668e-01
  4 KSP preconditioned resid norm 1.980048300408e+01 true resid norm 9.000928921285e+00 ||r(i)||/||b|| 6.255323338225e-02
  4 KSP preconditioned resid norm 2.456755478025e+01 true resid norm 4.251850126511e+01 ||r(i)||/||b|| 2.954883608080e-01
  5 KSP preconditioned resid norm 1.321389278831e+01 true resid norm 1.524133242368e+01 ||r(i)||/||b|| 1.059218034597e-01
  5 KSP preconditioned resid norm 1.223459075120e+01 true resid norm 8.356328766457e+00 ||r(i)||/||b|| 5.807349309368e-02
*** Warning: Krylov solver did not converge in 5 iterations (PETSc reason DIVERGED_ITS, residual norm ||r|| = 1.223459e+01).

>>> solver2.solve(U.vector(), bb)
Solving linear system of size 112724 x 112724 (PETSc Krylov solver).
  0 KSP preconditioned resid norm 1.145878366857e+01 true resid norm 8.356328766457e+00 ||r(i)||/||b|| 5.807349309368e-02
  1 KSP preconditioned resid norm 1.125109499208e+01 true resid norm 1.024485918804e+01 ||r(i)||/||b|| 7.119810336930e-02
  1 KSP preconditioned resid norm 1.590081379635e+01 true resid norm 1.082499790634e+01 ||r(i)||/||b|| 7.522985975331e-02
*** Warning: Krylov solver did not converge in 1 iterations (PETSc reason DIVERGED_ITS, residual norm ||r|| = 1.590081e+01).

umberto · Answer 1 · May 26, 2015

At iteration k, Krylov-subspace methods find the best x_k (here the definition of best depends on the Krylov method, e.g. GMRES and MINRES will find x_k that minimize the norm of the residual) in the subspace spanned by:
{ r, Ar, A^2r, ... A^kr }, r = b- Ax_0

Now, when you restart a Krylov method you lose all the previous information.

That is in the first linear solver (the one with 32 iterations) will find the best x_6 in the subspace:
{b, Ab, A^2b, ... , A^5b}. (assuming x_0 = 0}
In the second case (when you restart the solver) the second Krylov method will look for the best x_{1restart} in the subspace spanned by
{ r }, r = b - Ax_5 (where x_5 was the 5th iterate before restarting the solver).

Clearly x_6 and x_{1restart} are different since the subspaces are different.

As reference I would suggest you to have a look to Saad’s book on Iterative methods.

Hope this help

Thank you for your answer!
It helps indeed, but i should have known that by myself :-/
I think i will use a restarted GMRES which fits my needs. — adoll, May 26, 2015

Convergence of iterative solver with initial guess

1 Answer