ARSC2010.tex

%\documentclass[handout]{beamer}
\documentclass{beamer}

\mode<presentation>
{
%\usetheme{Singapore}
%\usetheme{Warsaw}
\usetheme{Malmoe}
\useinnertheme{circles}
\useoutertheme{infolines}
% \useinnertheme{rounded}

\setbeamercovered{transparent}
}

\usepackage[english]{babel}
\usepackage[latin1]{inputenc}
\usepackage{bm,textpos,alltt,listings,multirow,ulem,minted}

% font definitions, try \usepackage{ae} instead of the following
% three lines if you don't like this look
\usepackage{mathptmx}
\usepackage[scaled=.90]{helvet}
\usepackage{courier}
\usepackage[T1]{fontenc}
\usepackage{tikz}
\usetikzlibrary[shapes.arrows,arrows,shapes.misc]

% \usepackage{pgfpages}
% \pgfpagesuselayout{4 on 1}[letterpaper,landscape,border shrink=5mm]

\newcommand{\II}{\mathcal{I}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\E}{\mathcal{E}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\I}{\mathcal{I}}
\newcommand{\N}{\mathcal{N}}
\newcommand{\PP}{\mathcal{P}}
\newcommand{\bigO}{\mathcal{O}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\kb}{\tt}
\newcommand{\blue}{\textcolor{blue}}
\newcommand{\green}{\textcolor{green!70!black}}
\newcommand{\red}{\textcolor{red}}
\newcommand{\brown}{\textcolor{brown}}
\newcommand{\cyan}{\textcolor{cyan}}
\newcommand{\magenta}{\textcolor{magenta}}
\newcommand{\yellow}{\textcolor{yellow}}
\newcommand{\mini}{\mathop{\rm minimize}}
\newcommand{\st}{\mbox{subject to }}
\newcommand{\lap}[1]{\Delta #1}
\newcommand{\grad}[1]{\nabla #1}
\renewcommand{\div}[1]{\nabla \cdot #1}
\def\code#1{{\tt #1}}
\def\shell#1{{\tt \$ #1}}
\newcommand\mtab{\hspace{\stretch{1}}}
\newcommand\ud{\,\mathrm{d}}
\newcommand\bslash{{$\backslash$}}
\newcommand\half{{\frac 1 2}}
\newcommand{\abs}[1]{\left\lvert #1 \right\rvert}
\newcommand{\bigabs}[1]{\big\lvert #1 \big\rvert}
\newcommand{\norm}[1]{\left\lVert #1 \right\rVert}
\newcommand\oneitem[1]{\begin{itemize} \item #1 \end{itemize}}
\newcommand\pp{{\mathfrak p}}

\def\mintc\mint{c}

\def\Rbasic{1}
\def\Rsnesmf{2}
\def\Rsnesmflambda{3}
\def\Rsnesmfp{4}
\def\Rcolor{5}
\def\Rassemblebratu{6}
\def\Rassemblepicard{7}
\def\Rmyprealloc{8}
\def\Rnewtoncrash{9}
\def\Rnewtonbug{10}
\def\Rnewtonfix{11}

\title[PETSc]{The Portable Extensible Toolkit for Scientific computing}

\author{Jed Brown}


% - Use the \inst command only if there are several affiliations.
% - Keep it simple, no one is interested in your street address.
\institute[ETH Z\"urich]
{

}

\date{ARSC 2010-08-03}


% This is only inserted into the PDF information catalog. Can be left
% out.
\subject{Talks}



% If you have a file called "university-logo-filename.xxx", where xxx
% is a graphic format that can be processed by latex or pdflatex,
% resp., then you can add a logo as follows:

% \pgfdeclareimage[height=0.5cm]{university-logo}{university-logo-filename}
% \logo{\pgfuseimage{university-logo}}



% Delete this, if you do not want the table of contents to pop up at
% the beginning of each subsection:
% \AtBeginSubsection[]
% {
% \begin{frame}<beamer>
% \frametitle{Outline}
% \tableofcontents[currentsection,currentsubsection]
% \end{frame}
% }
\AtBeginPart{\frame{\partpage}}

% If you wish to uncover everything in a step-wise fashion, uncomment
% the following command:

%\beamerdefaultoverlayspecification{<+->}

\begin{document}
\lstset{language=C}

\begin{frame}
\titlepage
\end{frame}

\input{slides/PETSc/Requests.tex}

\part{Usage and Algorithms}
\begin{frame}
\frametitle{Day 1 Outline}
\tableofcontents
\end{frame}

\section{Introduction}
\input{slides/PETSc/Timeline.tex}
\input{slides/PETSc/About.tex}
\input{slides/PETSc/RoleOfPETSc.tex}
\input{slides/PETSc/Installation.tex}

\section{Programming model}
\input{slides/PETSc/PETScPyramid.tex}
\input{slides/SNES/FlowControl.tex}
\input{slides/MPICollective.tex}
\input{slides/PETSc/OptionsDatabase.tex}

\section{Algorithms}
\input{slides/pbratu.tex}
% \input{thi}
% \input{slides/SNES/DrivenCavity.tex}
% \input{DrivenCavityRun.tex}

% \begin{frame}{Summary}
% \vskip0pt plus.5fill
% \begin{block}{Today}
% \begin{itemize}
%   \item Build, run, and modify examples
%   \item Familiar with debugging capability
%   \item Understand some general properties of the algorithms
%   \item Check Jacobians, diagnose failure to converge
%   \item Get help from the options database and manual pages
% \end{itemize}
% \end{block}

% \begin{block}{Tomorrow}
%   \begin{itemize}
%   \item Performance bottlenecks
%   \item Optimizing memory access patterns
%   \item Parallel scalability
%   \item Integration with your existing projects/lower-level interfaces
%   \item Tricks for hard problems/extending PETSc
%   \end{itemize}
% \end{block}
% \end{frame}

% \input{FieldSplit}
% \input{Q1Q1Stokes}
% \section{Performance}
% \input{bandwidth}

\part{Performance, scalability, and hard problems}
\begin{frame}
\frametitle{Day 2 Outline}
\tableofcontents
% You might wish to add the option [pausesections]
\end{frame}

\section{Algorithms (continued from yesterday)}
\subsection{Hydrostatic Ice}
\input{slides/ToyHydrostaticIce.tex}
\subsection{Driven cavity}
\input{slides/SNES/DrivenCavity.tex}
\input{slides/DrivenCavityRun.tex}

\section{Application Integration}
\input{slides/PETSc/Integration/ApplicationIntegration.tex}
\input{slides/ApplicationIntegration.tex}
\input{slides/PETSc/Integration/Stages.tex}
\input{slides/PETSc/Integration/Initialization.tex}
\input{slides/PETSc/MatrixMemoryPreallocation.tex}
\input{slides/PETSc/Integration/LinearSolvers.tex}
\input{slides/PETSc/Integration/NonlinearSolvers.tex}

\section{Performance and Scalability}
%\input{WhyWeNeedAPerformanceModel.tex}
\input{slides/JFNKBottlenecks.tex}
\subsection{Memory hierarchy}
\input{slides/CPUArchitecture.tex}
\input{slides/HardwareCapability.tex}
\input{slides/OlikerSpMVOptimization.tex}
\input{slides/SpMVPerformanceModel.tex}
\input{slides/StreamTriad-XT5-BGP.tex}
\input{slides/OptimizingSpMV.tex}
\input{slides/OptimizingSpMVUnassembled.tex}
%\subsection{Matrix formats}
%\input{MatrixPreallocation}
%\frame{}
%\subsubsection{Preallocation}
%\frame{}
\subsection{Profiling}
\input{slides/PETSc/Integration/Profiling.tex}
\input{slides/ReadingLogSummary.tex}
\input{slides/CommunicationCosts.tex}
\input{slides/ScalabilityDefinition.tex}
\input{slides/MultigridAdvice.tex}

\section{Hard problems}
\input{slides/FieldSplit.tex}
\input{slides/CoupledMultiphysics.tex}
\input{slides/Anisotropy.tex}
\input{slides/SIPreconditioning.tex}

\begin{frame}{References}
  \begin{itemize}
  \item Knoll and Keyes, \emph{Jacobian-free Newton-Krylov methods: a survey of approaches and applications}, JCP, 2004.
  \item Elman et. al., \emph{A taxonomy and comparison of parallel block multi-level preconditioners for the incompressible Navier-Stokes equations}, JCP, 2008.
  \item Wan, Chan, and Smith, \emph{An energy-minimizing interpolation for robust multigrid methods}, SIAM J. Sci. Comp, 2000.
  \item Gropp, Kaushik, Keyes, Smith, \emph{Performance Modeling and Tuning of an Unstructured Mesh CFD Application}, Supercomputing, 2000.
  \end{itemize}
\end{frame}

\part{\texttt{petsc4py}, boundary conditions, and optimization}
\begin{frame}
\frametitle{Day 3 Outline}
\tableofcontents
% You might wish to add the option [pausesections]
\end{frame}

\section{petsc4py}
\input{slides/petsc4py/WhatIsPython.tex}
\input{slides/petsc4py/mpi4py.tex}
\input{slides/petsc4py/Intro.tex}

\section{Implementing boundary conditions}
\begin{frame}{Dirichlet conditions}
  \begin{itemize}
  \item Partition discrete ansatz space as
    \[ V = V_I \times V_\Gamma \]
  \item Define affine projections from $V \to V$
    \begin{itemize}
    \item[$R_I$] impose inhomogeneous Dirichlet values
    \item[$R_0$] impose homogeneous Dirichlet values
    \item[$R_\Gamma$] preserve boundary values (annihilate interior)
    \end{itemize}
  \item Discrete residual
    \begin{gather*}
      F(x) = R_0 f(R_I x) + R_\Gamma (x - R_I 0)
    \end{gather*}
    where $f$ is ``interior'' physics (ignoring Dirichlet boundary conditions)
  \item Jacobian preserves symmetry and completely decouples Dirichlet
    values from the rest of the system
  \end{itemize}
\end{frame}

\begin{frame}{Scaling boundary conditions}
  \begin{itemize}
  \item Only important for geometric multigrid (because fields are fully decoupled otherwise)
  \item Subspaces in geometric multigrid should be nested
  \item Want diagonal entry for boundary to be same size as diagonal entry for adjacent nodes
  \item Scale by ``local viscosity'' or an analogue
    \[ 6 \eta (\Delta x \Delta y \Delta z)\left(1/\Delta x^2 + 1/\Delta y^2 + 1/\Delta z^2\right) \]
  \end{itemize}
\end{frame}

\def\uu{\bm u}
\def\LL{\mathcal L}
\def\di{\partial}
\section{Optimization}
\begin{frame}{PDE-constrained optimization}
  \begin{block}{Minimization statement}
    Minimize $f(\bm x)$ subject to $\bm c(\bm x) = 0$ where $\bm x =
    (\bm d,\uu)^T$ is the vector of design and state variables.
  \end{block}
  \begin{block}{Lagrangian}
    \begin{equation*}
      \LL(\bm x,\bm \lambda) = f(\bm x) + \bm \lambda^T \bm c(\bm x)
    \end{equation*}
  \end{block}
  \begin{block}{First order optimality conditions}
    \begin{equation*}
      \begin{pmatrix}
        \LL_x \\
        \LL_\lambda
      \end{pmatrix}
      (\bm x,\bm \lambda) =
      \begin{pmatrix}
        \bm g (\bm x) + A(\bm x)^T \bm \lambda \\
        \bm c(\bm x)
      \end{pmatrix}
      = 0
    \end{equation*}
    where $\bm g = \frac{\di f}{\di \bm x}$ and $A = (A_d \ \ A_u) = \frac{\di \bm c}{\di \bm x}$.
  \end{block}
\end{frame}

\begin{frame}[shrink=5]{A full space method: LNKS}
  \begin{block}{The Hessian}
    \begin{equation*}
      \begin{pmatrix}
        W_{ss} & A_s^T & W_{sd} \\
        A_s & 0 & A_d \\
        W_{ds} & A_d^T & W_{dd}
      \end{pmatrix}
    \end{equation*}
  \end{block}
  \begin{block}{Block factorization}
    \begin{align*}
      \begin{bmatrix}
        & 1 & \\
        1 & & \\
        & & 1
      \end{bmatrix}
      \begin{bmatrix}
        1 & & \\
        W_{ss} A_s^{-1} & 1 & \\
        W_{ds} A_s^{-1} & A_d^T A_s^{-T} & 1
      \end{bmatrix}
      \begin{bmatrix}
        A_s & & \\
        & A_s^T & \\
        & & S \\
      \end{bmatrix}
      \begin{bmatrix}
        1 & & A_d \\
        & 1 & R \\
        & & 1
      \end{bmatrix}
    \end{align*}
    where
    \[ R = W_{ud} - W_{uu}A_u^{-T}A_d , \]
    \[ S = A_d^T A_s^{-T} W_{ss} A_s^{-1} A_d - A_d^T A_s^{-T} W_{sd} - W_{ds} A_s^{-1} A_d + W_{dd} \]
    and $\tilde{S}$ is a BFGS update used to precondition solves with $S$.%\cite{biros2005pln1,biros2005pln2}
  \end{block}
\end{frame}

% \input{FieldSplit}
% \input{Q1Q1Stokes}
% \section{Performance}

\end{document}