Commits

committed 7b08aa8

Broke down ICL14 talk into slides

• Participants
• Parent commits 4cdc2f5
• Branches master

File ICL14.tex

• Ignore whitespace

\title[NPC]{Nonlinear Preconditioning in PETSc}
\author[M.~Knepley]{Matthew~Knepley {\bf$\in$} PETSc Team}
-\date[FoaLab]{FoaLab Seminar\\Oxford University \quad March 21, 2014}
+\date[SUNY '14]{Seminar\\Dept. of Mechanical and Aerospace Engineering, SUNY Buffalo\\Buffalo, NY \qquad April 23, 2014}
% - Use the \inst command if there are several affiliations
\institute[UC]{
Computation Institute\\

\section{Algorithmics}
%
-\begin{frame}{Abstract System}\Large
-
-Out prototypical nonlinear equation is:
-
-  \F(\vx) = \vb
-
-\begin{overprint}
-\onslide<1>
-and we define the residual as
-
-  \vr(\vx) = \F(\vx) - \vb
-
-\onslide<2>
-and we define the (linear) residual as
-
-  \vr(\vx) = A \vx - \vb
-
-\end{overprint}
-\end{frame}
-%
-\begin{frame}{Linear Left Preconditioning}\Large
-
-\begin{overprint}
-\onslide<1>
-The modified equation becomes
-
-  P^{-1} \left( A \vx - \vb \right) = 0
-
-\onslide<2>
-The modified defect correction equation becomes
-
-  P^{-1} \left( A \vx_i - \vb \right) = \vx_{i+1} - \vx_i
-
-\end{overprint}
-\end{frame}
-%
-
-Unlike the linear case, we must define
-\begin{itemize}
-  \item the solution $\vx$
-  \item[] AND
-  \item the residual $\vr$
-\end{itemize}
-in both the inner and outer solvers.
-\end{frame}
-%
-
-The linear iteration
-\begin{overprint}
-\onslide<1>
-
-  \vx_{i+1} = \vx_i - (\alpha P^{-1} + \beta Q^{-1}) (A \vx_i - \vb)
-
-\onslide<2->
-
-  \vx_{i+1} = \vx_i - (\alpha P^{-1} + \beta Q^{-1}) \vr_i
-
-\end{overprint}
-
-\bigskip
-becomes the nonlinear iteration
-\visible<3>{
-
-  \vx_{i+1} = \vx_i + \alpha (\N(\F,\vx_i,\vb) - \vx_i) + \beta (\M(\F,\vx_i,\vb) - \vx_i)
-
-}
-\end{frame}
-%
-\begin{frame}{Nonlinear Left Preconditioning}\Large
-
-From the additive combination, we have
-
-  P^{-1} \vr \Longrightarrow \vx_i - \N(\F,\vx_i,\vb)
-
-so we define the preconditioning operation as
-
-  \vr_L \equiv \vx - \N(\F,\vx,\vb)
-
-\end{frame}
-%
-\begin{frame}[fragile]{Multiplicative Combination}\Large
-
-The linear iteration
-\begin{overprint}
-\onslide<1>
-\begin{align}
-  \vx_{i+1} = \vx_i - (P^{-1} + Q^{-1} - Q^{-1} A P^{-1}) \vr_i
-\end{align}
-\onslide<2->
-\begin{align}
-  \vx_{i+1/2} &= \vx_i - P^{-1} \vr_i\\
-  \vx_i      &= \vx_{i+1/2} - Q^{-1} \vr_{i+1/2}
-\end{align}
-\end{overprint}
-
-\bigskip
-becomes the nonlinear iteration
-\visible<3>{
-
-  \vx_{i+1} = \M(\F,\,\N(\F,\vx_i,\vb),\,\vb)
-
-}
-
-\end{frame}
-%
-\begin{frame}{Nonlinear Right Preconditioning}\Large
-
-For the linear case, we have
-\begin{align}
-  A P^{-1} \vy &= \vb\\
-           \vx &= P^{-1} \vy
-\end{align}
-so we define the preconditioning operation as
-\begin{align}
-  \vy &= \M(\F(\N(\F,\cdot,\vb)),\,\vx_i,\vb)\\
-  \vx &= \N(\F,\vy,\vb)
-\end{align}
-\end{frame}
-%
-\begin{frame}{Nonlinear Preconditioning}
-\begin{tabular}{l|c|c|l}
-  Type            & Sym      & Statement & Abbreviation \\
-  \hline
-  Additive        & $+$      & $\vx + \alpha(\M(\F,\vx,\vb)-\vx)$                            & $\M + \N$\\
-                  &          & $\phantom{\vx} + \beta(\N(\F,\vx,\vb)-\vx)$                   & \\
-  Multiplicative  & $*$      & $\M(\F,\N(\F,\vx,\vb),\vb)$                                   & $\M * \N$\\
-  Left Prec.      & $\lp$    & $\M(\vx - \N(\F,\vx,\vb),\vx,\vb)$                            & $\M \lp \N$\\
-  Right Prec.     & $\rp$    & $\M(\F(\N(\F,\vx,\vb)),\vx,\vb)$                              & $\M \rp \N$\\
-  Inner Lin. Inv. & $\lin$   & $\vy = \vJ(\vx)^{-1}\vr(\vx) = \krylov(\vJ(\vx),\vy_0,\vb)$    & $\NEWT\lin\krylov$\\
-\end{tabular}
-\end{frame}
-%
-\begin{frame}{Nonlinear Richardson}
-
-\begin{algorithmic}[1]
-  \Procedure{\NRICH}{$\vF, \vx_i, \vb$}
-    \State $\phantom{\vx_{i+1}} \mathllap{\vd} = -\vr(\vx_i)$
-    \State $\vx_{i+1} = \vx_i + \lambda\vd$ \Comment{$\lambda$ determined by line search}
-  \EndProcedure
-  \State \Return $\vx_{i+1}$
-\end{algorithmic}
-\end{frame}
-%
-\begin{frame}{Line Search}
-
-Equivalent to $\NRICH \lp \N$:
-\begin{align*}
-  \NRICH &\lp \N &\\
-  \visible<2->{\NRICH(\vx &- \N(\F,\vx,\vb),\vx,\vb) &\\}
-  \visible<3->{\vx_{i+1} &= \vx_i + \lambda \vr_L &\\}
-  \visible<4->{\vx_{i+1} &= \vx_i + \lambda (\N(\F,\vx_i,\vb) - \vx_i) &}
-\end{align*}
-\end{frame}
-%
-\begin{frame}{PETSc Line Search}
-\begin{itemize}
-  \item[BT] Standard cubic back-tracking
-  \begin{itemize}
-    \item Defaults to full step when Wolfe conditions satisfied
-    \item No more work than necessary
-    \item May stagnate
-    \item Can be badly scaled apart from \NEWT
-  \end{itemize}
-
-  \item[L2] Secant minimization of residual
-  \begin{itemize}
-    \item Optimal damping in the residual direction
-    \item Minimize $||\vr(\vx + \lambda\delta\vx)||_2$
-  \end{itemize}
-
-  \item[CP] Secant minimization of energy
-  \begin{itemize}
-    \item Appropriate when $\F$ is the gradient of an energy function
-    \item Looks for roots of $\delta\vx^T \F(\vx + \lambda\delta\vx)$
-  \end{itemize}
-\end{itemize}
-\end{frame}
-%
-\begin{frame}{Nonlinear GMRES}
-\begin{algorithmic}[1]
-        \Procedure{$\NGMRES$}{$\F, \vx_i \cdots \vx_{i-m+1}, \vb$ }
-        \State $\vd_i = -\vr(\vx_i)$
-        \State $\vx_i^M = \vx_i + \lambda\vd_i$
-        \State $\F_i^M = \vr(\vx_i^M)$
-        \State \textbf{minimize} $\|\vr((1 - \sum^{i-1}_{k=i-m}\alpha_i)\vx_i^M + \displaystyle\sum_{k = i - m}^{i-1}\alpha_k\vx_k)\|_2$ over $\{\alpha_{i - m} \cdots \alpha_{i-1}\}$
-        \State $\vx^A_i = (1 - \sum^{i-1}_{k=i-m}\alpha_i)\vx^M + \displaystyle\sum^{i-1}_{k = i - m}\alpha_k\vx_k$
-        \State $\vx_{i+1} = \vx^A_i \text{ or } \vx^M_i \text{ if } \vx^A_i \text{ is insufficient.}$
-        \EndProcedure
-        \State \Return $\vx_{i+1}$
-\end{algorithmic}
-\pause
-\begin{center}
-  Can emulate Anderson mixing and DIIS
-\end{center}
-\end{frame}
-%
-\begin{frame}{Newton-Krylov}
-\begin{algorithmic}[1]
-  \Procedure{\NK}{$\vF,\vx_i,\vb$}
-  \State $\phantom{\vx_{i+1}}\mathllap{\vd} = \vJ(\vx_i)^{-1} \vr(\vx_i,\vb)$ \Comment{solve by Krylov method}
-  \State $\vx_{i+1} = \vx_i + \lambda \vd$ \Comment{$\lambda$ determined by line search}
-  \EndProcedure
-  \State \Return $\vx_{i+1}$
-\end{algorithmic}
-\end{frame}
-%
-\begin{frame}{Left Preconditioned Newton-Krylov}
-\begin{algorithmic}[1]
-  \Procedure{\NK}{$\vx - \vM(\F,\vx,\vb),\vx_i,0$}
-    \State $\phantom{\vx_{i+1}}\mathllap{\vd} = \frac{\partial(\vx_i - \M(\F,\vx_i,\vb))}{\partial\vx_i}^{-1} (\vx_i - \M(\F,\vx_i,\vb))$
-    \State $\vx_{i+1} = \vx_i + \lambda \vd$
-  \EndProcedure
-  \State \Return $\vx_{i+1}$
-\end{algorithmic}
-\end{frame}
-%
-\begin{frame}{Jacobian Computation}
-\visible<3>{
-\begin{center}\LARGE
-  \red{\bf Impractical!}
-\end{center}
-}
-\begin{equation*}
-  \frac{\partial(\vx - \M(\F,\vx_i,\vb))}{\vx_i} = I - \frac{\partial\M(\F,\vx_i,\vb)}{\partial\vx_i},
-\end{equation*}
-\pause
-Direct differencing would require
-\begin{itemize}
-  \item one inner nonlinear iteration
-\end{itemize}
-per {\bf Krylov} iteration.
-\end{frame}
-%
-\begin{frame}{Jacobian Computation}{Approximation for NASM}
-\begin{align*}
-  \frac{\partial(\vx - \M(\F,\vx,\vb))}{\partial\vx} &= \frac{\partial(\vx - (\vx - \sum_b J_b(\vx_b)^{-1} \F_b(\vx_b)))}{\partial\vx}\\
-   &\approx \sum_b J_b(\vx_{b*})^{-1} J(\vx)
-\end{align*}
-This would require
-\begin{itemize}
-  \item one inner nonlinear iteration
-  \item small number of block solves
-\end{itemize}
-per {\bf outer nonlinear} iteration.
-\end{frame}
-%% Slide on right-prec and the Jac approx, equiv to multiplicative, other approx of Jameson
-%
-\begin{frame}{Right Preconditioned Newton-Krylov}
-\begin{algorithmic}[1]
-  \Procedure{NK}{$\vF(\vM(\vF,\cdot,\vb)),\vy_i,\vb$}
-    \State $\phantom{\vx_{i+1}}\mathllap{\vx_i} = \vM(\vF,\vy_i,\vb)$
-    \State $\phantom{\vx_{i+1}}\mathllap{\vd} = \vJ(\vx)^{-1}\vr(\vx_i)$
-    \State $\vx_{i+1} = \vx_i + \lambda \vd$  \Comment{$\lambda$ determined by line search}
-  \EndProcedure
-  \State \Return $\vx_{i+1}$
-\end{algorithmic}
-\end{frame}
-%
-\begin{frame}{Jacobian Computation}{First-Order Approximation}
-Only the action of the original Jacobian is needed at first order:
-% Suppress b in function calls
-\begin{align*}
-  \vy_{i+1}         &= \vy_i - \lambda\frac{\partial\M(\F,\vy_i)}{\partial\vy_i}^{-1} J(\M(\F,\vy_i))^{-1}\F(\M(\F,\vy_i)) \\
-  \M(\F,\vy_{i+1})  &= \M(\F, \vy_i - \lambda\frac{\partial\M(\F,\vy_i)}{\partial\vy_i}^{-1} J(\M(\F,\vy_i))^{-1} \F(\M(\F,\vy_i))) \\
-                   &\approx \M(\F,\vy_i) \\
-                   & - \lambda\frac{\partial\M(\F,\vy_i)}{\partial\vy_i} \frac{\partial\M(\F,\vy_i)}{\partial\vy_i}^{-1} J(\M(\F,\vy_i))^{-1} \F(\M(\F,\vy_i))) \\
-                   &= \M(\F,\vy_i) - \lambda J(\M(\F,\vy_i))^{-1} \F(\M(\F,\vy_i)) \\
-  \vx_{i+1}         &= \vx_i - \lambda J(\vx_i)^{-1}\F(\vx_i)
-\end{align*}
-\pause
-\begin{center}
-  $\NK \rp \vM$ is equivalent to $\NK * \vM$ at first order
-\end{center}
-\end{frame}
-%
-\begin{frame}{Jacobian Computation}{Direct Approximation}
-\begin{align*}
-  \F(\M(\F,\vy_i,\vb)) &= J(\M(\F,\vy_i,\vb)) \frac{\partial\M(\F,\vy_i,\vb)}{\partial\vy_i} (\vy_{i+1} - \vy_i)\\
-                       &\approx J(\M(\F,\vy_i,\vb)) (\M(\F,\vy_i + \vd, \vb) - \vx_i)
-\end{align*}
-\begin{itemize}
-  \item Solve for $\vd$
-  \item Requires inner nonlinear solve for each Krylov iterate
-  \item Needs FGMRES
-\end{itemize}
-\end{frame}
-%
-\begin{frame}{Full Approximation Scheme (FAS)}{Nonlinear Multigrid}
-\begin{algorithmic}[1]
-  \Procedure{$\FAS$}{$\vF, \vx_i, \vb$}
-    \State $\phantom{\vx_{i+1}}\mathllap{\vx_s} = \M_s(\F, \vx_i, \vb)$
-    \State $\phantom{\vx_{i+1}}\mathllap{\vx_c} = \inject \vx_s$
-    \State $\phantom{\vx_{i+1}}\mathllap{\vb_c} = \F_c(\vx_c) - \restrict[\F(\vx_s) - \vb]$
-    \State $\phantom{\vx_{i+1}}\mathllap{\vx_s} = \vx_s + \interp[\FAS(\vF_c,\vx_c,\vb_c) - \vx_c]$
-    \State $\phantom{\vx_{i+1}}\mathllap{\vx_{i+1}} = \M_s(\F, \vx_s, \vb)$
-  \EndProcedure
-  \State \Return $\vx_{i+1}$
-\end{algorithmic}
-\end{frame}
+\input{slides/SNES/BasicSystem.tex}
+\input{slides/SNES/LeftPrec.tex}
+\input{slides/SNES/LeftNPrec.tex}
+\input{slides/SNES/MultiplicativeNPrec.tex}
+\input{slides/SNES/RightNPrec.tex}
+\input{slides/SNES/NPrecTable.tex}
+%
+\input{slides/SNES/NRICH.tex}
+\input{slides/SNES/NRICH-LP.tex}
+\input{slides/SNES/LineSearchVariants.tex}
+\input{slides/SNES/NGMRES.tex}
+\input{slides/SNES/NK.tex}
+\input{slides/SNES/LP-NK.tex}
+\input{slides/SNES/RP-NK.tex}
+\input{slides/SNES/FAS.tex}
%
\begin{frame}{Other Nonlinear Solvers}\Large
\setlength{\leftmargini}{3em}
\section{Experiments}
%
\subsection{Composition}
-\begin{frame}{Large Deformation Elasticity}
-\begin{center}
-  \includegraphics[width=0.75\textwidth]{figures/solutions/SNESEx16/elasticitydeformation.png}
-\end{center}
-\begin{center}
-  \only<1>{Unstressed and stressed configurations for the elasticity test problem.}
-  \only<2>{Coloration indicates vertical displacement in meters.}
-  \only<3>{P. Wriggers, Nonlinear Finite Element Methods, Springer, 2008.}
-\end{center}
-\end{frame}
-%
-\begin{frame}[fragile]{Large Deformation Elasticity}{Running}
-
-SNES example 16:
-\begin{alltt}
-cd src/snes/examples/tutorials
-make ex16
-./ex16 -da_grid_x 401 -da_grid_y 9 -da_grid_z 9
-  -height 3 -width 3
-  -rad 100 -young 100 -poisson 0.2
-\end{alltt}
-\end{frame}
-%
-\begin{frame}{Plain SNES Convergence}
-\begin{overprint}
-\onslide<1>
-$(\NK\pc\MG)$ and \NCG
-\begin{center}
-  \includegraphics[width=0.7\textwidth]{figures/solutions/SNESEx16/unpreconditioned.pdf}
-\end{center}
-\onslide<2>
-\bigskip
-\begin{tabular}{l|ccccccc}
-Solver & T & N. It & L. It & Func & Jac & PC & NPC \\
-\hline
-$\NCG$ & 53.05 & 4495 & 0 & 8991 & -- & -- & -- \\
-$(\NK\pc\MG)$ & 23.43 & 27 & 1556 & 91 & 27 & 1618 & -- \\
-\end{tabular}
-\end{overprint}
-\end{frame}
-%
-\begin{frame}{Composed SNES Convergence}
-\begin{overprint}
-\onslide<1>
-$\NCG(10)+(\NK\pc\MG)$ and $\NCG(10)*(\NK\pc\MG)$
-\begin{center}
-  \includegraphics[width=0.7\textwidth]{figures/solutions/SNESEx16/composed.pdf}
-\end{center}
-\onslide<2>
-\bigskip
-\begin{tabular}{l|ccccccc}
-Solver & T & N. It & L. It & Func & Jac & PC & NPC \\
-\hline
-$\NCG$ & 53.05 & 4495 & 0 & 8991 & -- & -- & -- \\
-$(\NK\pc\MG)$ & 23.43 & 27 & 1556 & 91 & 27 & 1618 & -- \\
-$\NCG(10)$ & 14.92 & 9 & 459 & 218 & 9 & 479 & -- \\
-$+(\NK\pc\MG)$ &  &  &  &  &  &  &  \\
-$\NCG(10)$ & 16.34 & 11 & 458 & 251 & 11 & 477 & -- \\
-$*(\NK\pc\MG)$ &  &  &  &  &  &  &  \\
-\end{tabular}
-\end{overprint}
-\end{frame}
-%
-\begin{frame}{Peconditioned SNES Convergence}
-\begin{overprint}
-\onslide<1>
-$\NGMRES\rp(\NK\pc\MG)$ and $\NCG\lp(\NK\pc\MG)$
-\begin{center}
-  \includegraphics[width=0.5\textwidth]{figures/solutions/SNESEx16/preconditioned.pdf}
-\end{center}
-\onslide<2>
-\bigskip
-\begin{tabular}{l|ccccccc}
-Solver & T & N. It & L. It & Func & Jac & PC & NPC \\
-\hline
-$\NCG$ & 53.05 & 4495 & 0 & 8991 & -- & -- & -- \\
-$(\NK\pc\MG)$ & 23.43 & 27 & 1556 & 91 & 27 & 1618 & -- \\
-$\NCG(10)$ & 14.92 & 9 & 459 & 218 & 9 & 479 & -- \\
-$+(\NK\pc\MG)$ &  &  &  &  &  &  &  \\
-$\NCG(10)$ & 16.34 & 11 & 458 & 251 & 11 & 477 & -- \\
-$*(\NK\pc\MG)$ &  &  &  &  &  &  &  \\
-$\NGMRES$ & 9.65 & 13 & 523 & 53 & 13 & 548 & 13 \\
-$\rp(\NK\pc\MG)$ &  &  &  &  &  &  &  \\
-$\NCG$ & 9.84 & 13 & 529 & 53 & 13 & 554 & 13 \\
-$\lp(\NK\pc\MG)$ &  &  &  &  &  &  &  \\
-\end{tabular}
-\end{overprint}
-\end{frame}
+\input{slides/SNES/Ex16Equations.tex}
+\input{slides/SNES/SNESEx16.tex}
+\input{slides/SNES/NPCEx16.tex}
%
\subsection{Multilevel}
\input{slides/SNES/Ex19Equations.tex}

• Ignore whitespace
+
+The linear iteration
+\begin{overprint}
+\onslide<1>
+
+  \vx_{i+1} = \vx_i - (\alpha P^{-1} + \beta Q^{-1}) (A \vx_i - \vb)
+
+\onslide<2->
+
+  \vx_{i+1} = \vx_i - (\alpha P^{-1} + \beta Q^{-1}) \vr_i
+
+\end{overprint}
+
+\bigskip
+becomes the nonlinear iteration
+\visible<3>{
+
+  \vx_{i+1} = \vx_i + \alpha (\N(\F,\vx_i,\vb) - \vx_i) + \beta (\M(\F,\vx_i,\vb) - \vx_i)
+
+}
+\end{frame}

File slides/SNES/BasicSystem.tex

• Ignore whitespace
+\begin{frame}{Abstract System}\Large
+
+Out prototypical nonlinear equation is:
+
+  \F(\vx) = \vb
+
+\begin{overprint}
+\onslide<1>
+and we define the residual as
+
+  \vr(\vx) = \F(\vx) - \vb
+
+\onslide<2>
+and we define the (linear) residual as
+
+  \vr(\vx) = A \vx - \vb
+
+\end{overprint}
+\end{frame}

File slides/SNES/Ex16Equations.tex

• Ignore whitespace
+\begin{frame}{SNES ex16}{3D Large Deformation Elasticity}
+
+
+ \int_{\Omega} F \cdot S : \nabla v\,d\Omega + \int_{\Omega} \mathtt{loading}\ \mathbf{e}_y \cdot v\,d\Omega = 0
+
+\medskip
+\begin{itemize}
+  \item[S] Second Piola-Kirchhoff tensor
+  \begin{itemize}
+    \item[] Saint Venant-Kirchhoff model of hyperelasticity
+  \end{itemize}
+  \item[$\Omega$] {\tt -arc} \textit{angle} subsection of a cylindrical shell
+  \begin{itemize}
+    \item[] {\tt -height} \textit{thickness}
+    \item[] {\tt -width} \textit{width}
+  \end{itemize}
+\end{itemize}
+\end{frame}

File slides/SNES/Ex19Equations.tex

• Ignore whitespace
-\begin{frame}{SNES ex19}{Drive Cavity Flow}
+\begin{frame}{SNES ex19}{Driven Cavity Flow}
\begin{center}
\begin{align}
-\Delta\vu    + \nabla\times\Omega &= 0 \\
-\Delta\Omega + \nabla\cdot(\vu\Omega) - \sc{GR} \nabla_x T &= 0 \\
-  -\Delta T     + \sc{PR} \nabla\cdot(\vuT) &= 0
+  -\Delta T     + \sc{PR} \nabla\cdot(\vu T) &= 0
\end{align}
\end{center}
\end{frame}

File slides/SNES/FAS.tex

• Ignore whitespace
+\begin{frame}{Full Approximation Scheme (FAS)}{Nonlinear Multigrid}
+\begin{algorithmic}[1]
+  \Procedure{$\FAS$}{$\vF, \vx_i, \vb$}
+    \State $\phantom{\vx_{i+1}}\mathllap{\vx_s} = \M_s(\F, \vx_i, \vb)$
+    \State $\phantom{\vx_{i+1}}\mathllap{\vx_c} = \inject \vx_s$
+    \State $\phantom{\vx_{i+1}}\mathllap{\vb_c} = \F_c(\vx_c) - \restrict[\F(\vx_s) - \vb]$
+    \State $\phantom{\vx_{i+1}}\mathllap{\vx_s} = \vx_s + \interp[\FAS(\vF_c,\vx_c,\vb_c) - \vx_c]$
+    \State $\phantom{\vx_{i+1}}\mathllap{\vx_{i+1}} = \M_s(\F, \vx_s, \vb)$
+  \EndProcedure
+  \State \Return $\vx_{i+1}$
+\end{algorithmic}
+\end{frame}

File slides/SNES/LP-NK.tex

• Ignore whitespace
+\begin{frame}{Left Preconditioned Newton-Krylov}
+\begin{algorithmic}[1]
+  \Procedure{\NK}{$\vx - \vM(\F,\vx,\vb),\vx_i,0$}
+    \State $\phantom{\vx_{i+1}}\mathllap{\vd} = \frac{\partial(\vx_i - \M(\F,\vx_i,\vb))}{\partial\vx_i}^{-1} (\vx_i - \M(\F,\vx_i,\vb))$
+    \State $\vx_{i+1} = \vx_i + \lambda \vd$
+  \EndProcedure
+  \State \Return $\vx_{i+1}$
+\end{algorithmic}
+\end{frame}
+%
+\begin{frame}{Jacobian Computation}
+\visible<3>{
+\begin{center}\LARGE
+  \red{\bf Impractical!}
+\end{center}
+}
+\begin{equation*}
+  \frac{\partial(\vx - \M(\F,\vx_i,\vb))}{\vx_i} = I - \frac{\partial\M(\F,\vx_i,\vb)}{\partial\vx_i},
+\end{equation*}
+\pause
+Direct differencing would require
+\begin{itemize}
+  \item one inner nonlinear iteration
+\end{itemize}
+per {\bf Krylov} iteration.
+\end{frame}
+%
+\begin{frame}{Jacobian Computation}{Approximation for NASM}
+\begin{align*}
+  \frac{\partial(\vx - \M(\F,\vx,\vb))}{\partial\vx} &= \frac{\partial(\vx - (\vx - \sum_b J_b(\vx_b)^{-1} \F_b(\vx_b)))}{\partial\vx}\\
+   &\approx \sum_b J_b(\vx_{b*})^{-1} J(\vx)
+\end{align*}
+This would require
+\begin{itemize}
+  \item one inner nonlinear iteration
+  \item small number of block solves
+\end{itemize}
+per {\bf outer nonlinear} iteration.
+\end{frame}

File slides/SNES/LeftNPrec.tex

• Ignore whitespace
+\begin{frame}{Nonlinear Left Preconditioning}\Large
+
+From the additive combination, we have
+
+  P^{-1} \vr \Longrightarrow \vx_i - \N(\F,\vx_i,\vb)
+
+so we define the preconditioning operation as
+
+  \vr_L \equiv \vx - \N(\F,\vx,\vb)
+
+\end{frame}

File slides/SNES/LeftPrec.tex

• Ignore whitespace
+\begin{frame}{Linear Left Preconditioning}\Large
+
+\begin{overprint}
+\onslide<1>
+The modified equation becomes
+
+  P^{-1} \left( A \vx - \vb \right) = 0
+
+\onslide<2>
+The modified defect correction equation becomes
+
+  P^{-1} \left( A \vx_i - \vb \right) = \vx_{i+1} - \vx_i
+
+\end{overprint}
+\end{frame}

File slides/SNES/LineSearchVariants.tex

• Ignore whitespace
+\begin{frame}{PETSc Line Search}
+\begin{itemize}
+  \item[BT] Standard cubic back-tracking
+  \begin{itemize}
+    \item Defaults to full step when Wolfe conditions satisfied
+    \item No more work than necessary
+    \item May stagnate
+    \item Can be badly scaled apart from \NEWT
+  \end{itemize}
+
+  \item[L2] Secant minimization of residual
+  \begin{itemize}
+    \item Optimal damping in the residual direction
+    \item Minimize $||\vr(\vx + \lambda\delta\vx)||_2$
+  \end{itemize}
+
+  \item[CP] Secant minimization of energy
+  \begin{itemize}
+    \item Appropriate when $\F$ is the gradient of an energy function
+    \item Looks for roots of $\delta\vx^T \F(\vx + \lambda\delta\vx)$
+  \end{itemize}
+\end{itemize}
+\end{frame}

File slides/SNES/MultiplicativeNPrec.tex

• Ignore whitespace
+\begin{frame}[fragile]{Multiplicative Combination}\Large
+
+The linear iteration
+\begin{overprint}
+\onslide<1>
+\begin{align}
+  \vx_{i+1} = \vx_i - (P^{-1} + Q^{-1} - Q^{-1} A P^{-1}) \vr_i
+\end{align}
+\onslide<2->
+\begin{align}
+  \vx_{i+1/2} &= \vx_i - P^{-1} \vr_i\\
+  \vx_i      &= \vx_{i+1/2} - Q^{-1} \vr_{i+1/2}
+\end{align}
+\end{overprint}
+
+\bigskip
+becomes the nonlinear iteration
+\visible<3>{
+
+  \vx_{i+1} = \M(\F,\,\N(\F,\vx_i,\vb),\,\vb)
+
+}
+
+\end{frame}

File slides/SNES/NGMRES.tex

• Ignore whitespace
+\begin{frame}{Nonlinear GMRES}
+\begin{algorithmic}[1]
+        \Procedure{$\NGMRES$}{$\F, \vx_i \cdots \vx_{i-m+1}, \vb$ }
+        \State $\vd_i = -\vr(\vx_i)$
+        \State $\vx_i^M = \vx_i + \lambda\vd_i$
+        \State $\F_i^M = \vr(\vx_i^M)$
+        \State \textbf{minimize} $\|\vr((1 - \sum^{i-1}_{k=i-m}\alpha_i)\vx_i^M + \displaystyle\sum_{k = i - m}^{i-1}\alpha_k\vx_k)\|_2$ over $\{\alpha_{i - m} \cdots \alpha_{i-1}\}$
+        \State $\vx^A_i = (1 - \sum^{i-1}_{k=i-m}\alpha_i)\vx^M + \displaystyle\sum^{i-1}_{k = i - m}\alpha_k\vx_k$
+        \State $\vx_{i+1} = \vx^A_i \text{ or } \vx^M_i \text{ if } \vx^A_i \text{ is insufficient.}$
+        \EndProcedure
+        \State \Return $\vx_{i+1}$
+\end{algorithmic}
+\pause
+\begin{center}
+  Can emulate Anderson mixing and DIIS
+\end{center}
+\end{frame}

File slides/SNES/NK.tex

• Ignore whitespace
+\begin{frame}{Newton-Krylov}
+\begin{algorithmic}[1]
+  \Procedure{\NK}{$\vF,\vx_i,\vb$}
+  \State $\phantom{\vx_{i+1}}\mathllap{\vd} = \vJ(\vx_i)^{-1} \vr(\vx_i,\vb)$ \Comment{solve by Krylov method}
+  \State $\vx_{i+1} = \vx_i + \lambda \vd$ \Comment{$\lambda$ determined by line search}
+  \EndProcedure
+  \State \Return $\vx_{i+1}$
+\end{algorithmic}
+\end{frame}

File slides/SNES/NPCEx16.tex

• Ignore whitespace
+\begin{frame}{Composed SNES Convergence}
+\begin{overprint}
+\onslide<1>
+$\NCG(10)+(\NK\pc\MG)$ and $\NCG(10)*(\NK\pc\MG)$
+\begin{center}
+  \includegraphics[width=0.7\textwidth]{figures/solutions/SNESEx16/composed.pdf}
+\end{center}
+\onslide<2>
+\bigskip
+\begin{tabular}{l|ccccccc}
+Solver & T & N. It & L. It & Func & Jac & PC & NPC \\
+\hline
+$\NCG$ & 53.05 & 4495 & 0 & 8991 & -- & -- & -- \\
+$(\NK\pc\MG)$ & 23.43 & 27 & 1556 & 91 & 27 & 1618 & -- \\
+$\NCG(10)$ & 14.92 & 9 & 459 & 218 & 9 & 479 & -- \\
+$+(\NK\pc\MG)$ &  &  &  &  &  &  &  \\
+$\NCG(10)$ & 16.34 & 11 & 458 & 251 & 11 & 477 & -- \\
+$*(\NK\pc\MG)$ &  &  &  &  &  &  &  \\
+\end{tabular}
+\end{overprint}
+\end{frame}
+%
+\begin{frame}{Peconditioned SNES Convergence}
+\begin{overprint}
+\onslide<1>
+$\NGMRES\rp(\NK\pc\MG)$ and $\NCG\lp(\NK\pc\MG)$
+\begin{center}
+  \includegraphics[width=0.5\textwidth]{figures/solutions/SNESEx16/preconditioned.pdf}
+\end{center}
+\onslide<2>
+\bigskip
+\begin{tabular}{l|ccccccc}
+Solver & T & N. It & L. It & Func & Jac & PC & NPC \\
+\hline
+$\NCG$ & 53.05 & 4495 & 0 & 8991 & -- & -- & -- \\
+$(\NK\pc\MG)$ & 23.43 & 27 & 1556 & 91 & 27 & 1618 & -- \\
+$\NCG(10)$ & 14.92 & 9 & 459 & 218 & 9 & 479 & -- \\
+$+(\NK\pc\MG)$ &  &  &  &  &  &  &  \\
+$\NCG(10)$ & 16.34 & 11 & 458 & 251 & 11 & 477 & -- \\
+$*(\NK\pc\MG)$ &  &  &  &  &  &  &  \\
+$\NGMRES$ & 9.65 & 13 & 523 & 53 & 13 & 548 & 13 \\
+$\rp(\NK\pc\MG)$ &  &  &  &  &  &  &  \\
+$\NCG$ & 9.84 & 13 & 529 & 53 & 13 & 554 & 13 \\
+$\lp(\NK\pc\MG)$ &  &  &  &  &  &  &  \\
+\end{tabular}
+\end{overprint}
+\end{frame}

• Ignore whitespace
+
+Unlike the linear case, we must define
+\begin{itemize}
+  \item the solution $\vx$
+  \item[] AND
+  \item the residual $\vr$
+\end{itemize}
+in both the inner and outer solvers.
+\end{frame}

File slides/SNES/NPrecTable.tex

• Ignore whitespace
+\begin{frame}{Nonlinear Preconditioning}
+\begin{tabular}{l|c|c|l}
+  Type            & Sym      & Statement & Abbreviation \\
+  \hline
+  Additive        & $+$      & $\vx + \alpha(\M(\F,\vx,\vb)-\vx)$                            & $\M + \N$\\
+                  &          & $\phantom{\vx} + \beta(\N(\F,\vx,\vb)-\vx)$                   & \\
+  Multiplicative  & $*$      & $\M(\F,\N(\F,\vx,\vb),\vb)$                                   & $\M * \N$\\
+  Left Prec.      & $\lp$    & $\M(\vx - \N(\F,\vx,\vb),\vx,\vb)$                            & $\M \lp \N$\\
+  Right Prec.     & $\rp$    & $\M(\F(\N(\F,\vx,\vb)),\vx,\vb)$                              & $\M \rp \N$\\
+  Inner Lin. Inv. & $\lin$   & $\vy = \vJ(\vx)^{-1}\vr(\vx) = \krylov(\vJ(\vx),\vy_0,\vb)$    & $\NEWT\lin\krylov$\\
+\end{tabular}
+\end{frame}

File slides/SNES/NRICH-LP.tex

• Ignore whitespace
+\begin{frame}{Line Search}
+
+Equivalent to $\NRICH \lp \N$:
+\begin{align*}
+  \NRICH &\lp \N &\\
+  \visible<2->{\NRICH(\vx &- \N(\F,\vx,\vb),\vx,\vb) &\\}
+  \visible<3->{\vx_{i+1} &= \vx_i - \lambda \vr_L &\\}
+  \visible<4->{\vx_{i+1} &= \vx_i + \lambda (\N(\F,\vx_i,\vb) - \vx_i) &}
+\end{align*}
+\end{frame}

File slides/SNES/NRICH.tex

• Ignore whitespace
+\begin{frame}{Nonlinear Richardson}
+
+\begin{algorithmic}[1]
+  \Procedure{\NRICH}{$\vF, \vx_i, \vb$}
+    \State $\phantom{\vx_{i+1}} \mathllap{\vd} = -\vr(\vx_i)$
+    \State $\vx_{i+1} = \vx_i + \lambda\vd$ \Comment{$\lambda$ determined by line search}
+  \EndProcedure
+  \State \Return $\vx_{i+1}$
+\end{algorithmic}
+\end{frame}

File slides/SNES/RP-NK.tex

• Ignore whitespace
+\begin{frame}{Right Preconditioned Newton-Krylov}
+\begin{algorithmic}[1]
+  \Procedure{NK}{$\vF(\vM(\vF,\cdot,\vb)),\vy_i,\vb$}
+    \State $\phantom{\vx_{i+1}}\mathllap{\vx_i} = \vM(\vF,\vy_i,\vb)$
+    \State $\phantom{\vx_{i+1}}\mathllap{\vd} = \vJ(\vx)^{-1}\vr(\vx_i)$
+    \State $\vx_{i+1} = \vx_i + \lambda \vd$  \Comment{$\lambda$ determined by line search}
+  \EndProcedure
+  \State \Return $\vx_{i+1}$
+\end{algorithmic}
+\end{frame}
+%
+\begin{frame}{Jacobian Computation}{First-Order Approximation}
+Only the action of the original Jacobian is needed at first order:
+% Suppress b in function calls
+\begin{align*}
+  \vy_{i+1}         &= \vy_i - \lambda\frac{\partial\M(\F,\vy_i)}{\partial\vy_i}^{-1} J(\M(\F,\vy_i))^{-1}\F(\M(\F,\vy_i)) \\
+  \M(\F,\vy_{i+1})  &= \M(\F, \vy_i - \lambda\frac{\partial\M(\F,\vy_i)}{\partial\vy_i}^{-1} J(\M(\F,\vy_i))^{-1} \F(\M(\F,\vy_i))) \\
+                   &\approx \M(\F,\vy_i) \\
+                   & - \lambda\frac{\partial\M(\F,\vy_i)}{\partial\vy_i} \frac{\partial\M(\F,\vy_i)}{\partial\vy_i}^{-1} J(\M(\F,\vy_i))^{-1} \F(\M(\F,\vy_i))) \\
+                   &= \M(\F,\vy_i) - \lambda J(\M(\F,\vy_i))^{-1} \F(\M(\F,\vy_i)) \\
+  \vx_{i+1}         &= \vx_i - \lambda J(\vx_i)^{-1}\F(\vx_i)
+\end{align*}
+\pause
+\begin{center}
+  $\NK \rp \vM$ is equivalent to $\NK * \vM$ at first order
+\end{center}
+\end{frame}
+%
+\begin{frame}{Jacobian Computation}{Direct Approximation}
+\begin{align*}
+  \F(\M(\F,\vy_i,\vb)) &= J(\M(\F,\vy_i,\vb)) \frac{\partial\M(\F,\vy_i,\vb)}{\partial\vy_i} (\vy_{i+1} - \vy_i)\\
+                       &\approx J(\M(\F,\vy_i,\vb)) (\M(\F,\vy_i + \vd, \vb) - \vx_i)
+\end{align*}
+\begin{itemize}
+  \item Solve for $\vd$
+  \item Requires inner nonlinear solve for each Krylov iterate
+  \item Needs FGMRES
+\end{itemize}
+\end{frame}

File slides/SNES/RightNPrec.tex

• Ignore whitespace
+\begin{frame}{Nonlinear Right Preconditioning}\Large
+
+For the linear case, we have
+\begin{align}
+  A P^{-1} \vy &= \vb\\
+           \vx &= P^{-1} \vy
+\end{align}
+so we define the preconditioning operation as
+\begin{align}
+  \vy &= \M(\F(\N(\F,\cdot,\vb)),\,\vx_i,\vb)\\
+  \vx &= \N(\F,\vy,\vb)
+\end{align}
+\end{frame}

File slides/SNES/SNESEx16.tex

• Ignore whitespace
+\begin{frame}{Large Deformation Elasticity}
+\begin{center}
+  \includegraphics[width=0.75\textwidth]{figures/solutions/SNESEx16/elasticitydeformation.png}
+\end{center}
+\begin{center}
+  \only<1>{Unstressed and stressed configurations for the elasticity test problem.}
+  \only<2>{Coloration indicates vertical displacement in meters.}
+  \only<3>{P. Wriggers, Nonlinear Finite Element Methods, Springer, 2008.}
+\end{center}
+\end{frame}
+%
+\begin{frame}[fragile]{Large Deformation Elasticity}{Running}
+
+SNES example 16:
+\begin{alltt}
+cd src/snes/examples/tutorials
+make ex16
+./ex16 -da_grid_x 401 -da_grid_y 9 -da_grid_z 9
+  -height 3 -width 3
+  -rad 100 -young 100 -poisson 0.2
+\end{alltt}
+\end{frame}
+%
+\begin{frame}{Plain SNES Convergence}
+\begin{overprint}
+\onslide<1>
+$(\NK\pc\MG)$ and \NCG
+\begin{center}
+  \includegraphics[width=0.7\textwidth]{figures/solutions/SNESEx16/unpreconditioned.pdf}
+\end{center}
+\onslide<2>
+\bigskip
+\begin{tabular}{l|ccccccc}
+Solver & T & N. It & L. It & Func & Jac & PC & NPC \\
+\hline
+$\NCG$ & 53.05 & 4495 & 0 & 8991 & -- & -- & -- \\
+$(\NK\pc\MG)$ & 23.43 & 27 & 1556 & 91 & 27 & 1618 & -- \\
+\end{tabular}
+\end{overprint}
+\end{frame}