<div dir="ltr">I accidentally forgot to reply to the list; resending.<div class="gmail_extra"><br><br><div class="gmail_quote">On Tue, Apr 22, 2014 at 4:55 PM, Peter Brune <span dir="ltr"><<a href="mailto:prbrune@gmail.com" target="_blank">prbrune@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote"><div class="">On Tue, Apr 22, 2014 at 4:40 PM, Fischer, Greg A. <span dir="ltr"><<a href="mailto:fischega@westinghouse.com" target="_blank">fischega@westinghouse.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div lang="EN-US" link="blue" vlink="purple"><div><p class="MsoNormal" style="margin-left:.5in"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"><u></u> <u></u></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"><u></u> <u></u></span></p><p class="MsoNormal" style="margin-left:.5in"><b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif"">From:</span></b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif""> Peter Brune [mailto:<a href="mailto:prbrune@gmail.com" target="_blank">prbrune@gmail.com</a>] <br>
<b>Sent:</b> Tuesday, April 22, 2014 12:44 PM</span></p><div><br><b>To:</b> Fischer, Greg A.<br><b>Cc:</b> <a href="mailto:petsc-users@mcs.anl.gov" target="_blank">petsc-users@mcs.anl.gov</a><br><b>Subject:</b> Re: [petsc-users] SNES: approximating the Jacobian with computed residuals?<u></u><u></u></div>
<p></p><p class="MsoNormal" style="margin-left:.5in"><u></u> <u></u></p><p class="MsoNormal" style="margin-left:.5in"><u></u> <u></u></p><p class="MsoNormal" style="margin-right:0in;margin-bottom:12.0pt;margin-left:.5in">
<u></u> <u></u></p><div><div><p class="MsoNormal" style="margin-left:.5in">On Tue, Apr 22, 2014 at 10:56 AM, Fischer, Greg A. <<a href="mailto:fischega@westinghouse.com" target="_blank">fischega@westinghouse.com</a>> wrote:<u></u><u></u></p>
<div><div><p class="MsoNormal" style="margin-left:1.0in"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"> </span><u></u><u></u></p><p class="MsoNormal" style="margin-left:1.0in">
<b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif"">From:</span></b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif""> Peter Brune [mailto:<a href="mailto:prbrune@gmail.com" target="_blank">prbrune@gmail.com</a>] <br>
<b>Sent:</b> Tuesday, April 22, 2014 10:16 AM<br><b>To:</b> Fischer, Greg A.<br><b>Cc:</b> <a href="mailto:petsc-users@mcs.anl.gov" target="_blank">petsc-users@mcs.anl.gov</a><br><b>Subject:</b> Re: [petsc-users] SNES: approximating the Jacobian with computed residuals?</span><u></u><u></u></p>
<div><div><p class="MsoNormal" style="margin-bottom:12.0pt;margin-left:1.0in"> <u></u><u></u></p><div><div><p class="MsoNormal" style="margin-left:1.5in">On Tue, Apr 22, 2014 at 8:48 AM, Fischer, Greg A. <<a href="mailto:fischega@westinghouse.com" target="_blank">fischega@westinghouse.com</a>> wrote:<u></u><u></u></p>
<p class="MsoNormal" style="margin-left:1.5in">Hello PETSc-users,<br><br>I'm using the SNES component with the NGMRES method in my application. I'm using a matrix-free context for the Jacobian and the MatMFFDComputeJacobian() function in my FormJacobian routine. My understanding is that this effectively approximates the Jacobian using the equation at the bottom of Page 103 in the PETSc User's Manual. This works, but the expense of computing two function evaluations in each SNES iteration nearly wipes out the performance improvements over Picard iteration.<u></u><u></u></p>
<div><p class="MsoNormal" style="margin-left:1.0in"> <u></u><u></u></p></div><div><p class="MsoNormal" style="margin-left:1.0in">Try -snes_type anderson. It's less stable than NGMRES, but requires one function evaluation per iteration. The manual is out of date. I guess it's time to fix that. It's interesting that the cost of matrix assembly and a linear solve is around the same as that of a function evaluation. Output from -log_summary would help in the diagnosis.<u></u><u></u></p>
</div></div><div><p class="MsoNormal" style="margin-left:.5in"><span style="color:#1f497d"> </span><u></u><u></u></p><p class="MsoNormal" style="margin-left:.5in"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">I tried the –snes_type anderson option, and it seems to be requiring even more function evaluations than the Picard iterations. I’ve attached –log_summary output. This seems strange, because I can use the NLKAIN code (<a href="http://nlkain.sourceforge.net/" target="_blank">http://nlkain.sourceforge.net/</a>) to fairly good effect, and I’ve read that it’s related to Anderson mixing. Would it be useful to adjust the parameters?</span><u></u><u></u></p>
</div></div></div></div></div></div><div><p class="MsoNormal" style="margin-left:.5in"><u></u> <u></u></p></div><div><p class="MsoNormal" style="margin-left:.5in">If I recall correctly, NLKAIN is yet another improvement on Anderson Mixing. Our NGMRES is what's in O/W and is built largely around being nonlinearly preconditionable with something strong like FAS. What is the perceived difference in convergence? (what does -snes_monitor say?) Any multitude of tolerances may be different between the two methods, and it's hard to judge without knowing much, much more. Seeing what happens when one changes the parameters is of course important if you're looking at performance.<u></u><u></u></p>
</div></div><div><p class="MsoNormal"><u></u> <u></u></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">I’m not looking to apply a preconditioner, so it sounds like perhaps NGMRES isn’t a good choice for this application.<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"><u></u> </span></p></div></div></div></div></blockquote><div><br></div></div><div>It all depends on the characteristics of your problem.</div>
<div class="">
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div lang="EN-US" link="blue" vlink="purple"><div><div><div><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">I tried a different problem (one that is larger and more realistic), and found the SNESAnderson performance to be substantially better. NLKAIN still converges faster, though. (NLKAIN: ~1350 function calls; SNESAnderson: ~1800 function calls; fixed-point: ~2550 function calls). The –snes_monitor seems to indicate steadily decreasing function norms.<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"><u></u> </span></p></div></div></div></div></blockquote><div><br></div></div><div>Playing around with -snes_anderson_beta will in all likelihood yield some performance improvements; perhaps significant. If I run snes/examples/tutorials/ex5 with -snes_anderson_beta 1 and snes_anderson_beta 0.1 the difference is 304 to 103 iterations. I may have to go look and see what NLKAIN does for damping; most Anderson Mixing implementations seem to do nothing complicated for this. Anything adaptive would take more function evaluations.</div>
<div class="">
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div lang="EN-US" link="blue" vlink="purple"><div><div><div><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">The –snes_anderson_monitor option doesn’t seem to produce any output. I’ve tried passing “-snes_anderson_monitor” and “-snes_anderson_monitor true” as options, but don’t see any output analogous to “-snes_gmres_monitor”. What’s the correct way to pass that option?<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"><u></u></span></p></div></div></div></div></blockquote><div><br></div></div><div>in the -snes_ngmres_monitor case, the monitor prints what happens with the choice between the candidate and the minimized solutions AND if the restart conditions are in play. In Anderson mixing, the first part doesn't apply, so -snes_anderson_monitor only prints anything if the method is restarting; the default is no restart, so nothing will show up. Changing to periodic restart or difference restart (which takes more reductions) will yield other output.</div>
<div class="">
<div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div lang="EN-US" link="blue" vlink="purple"><div><div><div><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"> <u></u></span></p>
</div><div><div><p class="MsoNormal" style="margin-left:.5in">By Picard, you mean simple fixed-point iteration, right? What constitutes a Picard iteration is a longstanding argument on this list and therefore requires clarification, unfortunately. :) This (without linesearch) can be duplicated in PETSc with -snes_type nrichardson -snes_linesearch_type basic. For a typical problem one must damp this with -snes_linesearch_damping <damping parameter> That's what the linesearch is there to avoid, but this takes more function evaluations.<u></u><u></u></p>
</div></div><div><p class="MsoNormal"> <span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"> <u></u><u></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">Yes, I mean fixed-point iteration.</span></p>
</div></div></div></div></blockquote><div><br></div></div><div>Cool.</div><div class=""><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div lang="EN-US" link="blue" vlink="purple">
<div><div><div><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"> <u></u><u></u></span></p></div><div><blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<div><div><div><div><div><div><p class="MsoNormal" style="margin-left:60.45pt"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"> </span><u></u><u></u></p><p class="MsoNormal" style="margin-left:60.45pt">
<span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">I’ve also attached –log_summary output for NGMRES. Does anything jump out as being amiss?</span><u></u><u></u></p></div>
</div>
</div></div></div></div></blockquote><div><p class="MsoNormal" style="margin-left:60.45pt"><u></u> <u></u></p></div><div><p class="MsoNormal" style="margin-left:60.45pt"><span style="font-size:10.0pt;font-family:"Courier New""> ##########################################################<br>
# #<br> # WARNING!!! #<br> # #<br> # This code was compiled with a debugging option, #<br>
# To get timing results run ./configure #<br> # using --with-debugging=no, the performance will #<br> # be generally two or three times faster. #<br> # #<br>
##########################################################</span><u></u><u></u></p></div><div><p class="MsoNormal" style="margin-left:60.45pt"> <u></u><u></u></p></div><div><p class="MsoNormal" style="margin-left:60.45pt">
Timing comparisons aren't reasonable with debugging on.<u></u><u></u></p></div></div><div><p class="MsoNormal"><span style="color:#1f497d"><u></u> <u></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">Yes, I understand. At this point, I’m just comparing numbers of function evalautions.</span></p>
</div></div></div></div></blockquote><div><br></div></div><div>OK.</div><span class="HOEnZb"><font color="#888888"><div><br></div><div>- Peter</div></font></span><div class=""><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div lang="EN-US" link="blue" vlink="purple">
<div><div><div><p class="MsoNormal"> </p></div></div></div></div></blockquote><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div lang="EN-US" link="blue" vlink="purple">
<div><div><div><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"><u></u><u></u></span></p></div><div><blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<div><div><div><div><div><div><p class="MsoNormal" style="margin-left:24.45pt"> <u></u><u></u></p><p class="MsoNormal" style="margin-left:24.45pt"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"> </span><u></u><u></u></p>
</div><div><blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0in;margin-bottom:5.0pt"><p class="MsoNormal" style="margin-left:48.9pt">
<br>Based on my (limited) understanding of the Oosterlee/Washio SIAM paper ("Krylov Subspace Acceleration of Nonlinear Multigrid..."), they seem to suggest that it's possible to approximate the Jacobian with a series of previously-computed residuals (eq 2.14), rather than additional function evaluations in each iteration. Is this correct? If so, could someone point me to a reference that demonstrates how to do this with PETSc?<u></u><u></u></p>
</blockquote><div><p class="MsoNormal" style="margin-left:48.9pt"> <u></u><u></u></p></div><div><p class="MsoNormal" style="margin-left:48.9pt">What indication do you have that the Jacobian is calculated at all in the NGMRES method? The two function evaluations are related to computing the quantities labeled F(u_M) and F(u_A) in O/W. We already use the Jacobian approximation for the minimization problem (2.14).<u></u><u></u></p>
</div><div><p class="MsoNormal" style="margin-left:48.9pt"> <u></u><u></u></p></div></div><div><p class="MsoNormal" style="margin-left:48.9pt">- Peter<u></u><u></u></p><p class="MsoNormal" style="margin-left:24.45pt"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"> </span><u></u><u></u></p>
<p class="MsoNormal" style="margin-left:24.45pt"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">Thanks for the clarification.</span><u></u><u></u></p><p class="MsoNormal" style="margin-left:24.45pt">
<span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"> </span><span style="color:#888888"><u></u><u></u></span></p><p class="MsoNormal" style="margin-left:24.45pt"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">-Greg</span><span style="color:#888888"><u></u><u></u></span></p>
</div><div><div><p class="MsoNormal" style="margin-left:48.9pt"> <u></u><u></u></p></div><blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0in;margin-bottom:5.0pt">
<p class="MsoNormal" style="margin-bottom:12.0pt;margin-left:48.9pt"><br>Or, perhaps a better question to ask is: are there other ways of reducing the computing burden associated with estimating the Jacobian?<br><br>Thanks,<br>
Greg<u></u><u></u></p></blockquote></div></div><p class="MsoNormal" style="margin-left:48.9pt"> <u></u><u></u></p></div></div></div></div></blockquote></div></div><div><div><p class="MsoNormal"><u></u> <u></u></p></div></div>
</div></div></blockquote></div></div><br></div></div>
</blockquote></div><br></div></div>