# Presentation: 301552

## David Keyes, project lead

**David Keyes, project lead**
**Dept. of Mathematics & Statistics**
**Old Dominion University**

## Who we are...

**Who we are...**

**... ****the ****PETSc ****and**** TAO**** people**

**... ****the ****hypre**** and ****PVODE**** people**

**... ****the ****SuperLU ****and ****PARPACK**** people**

**... ****as well as the builders of other widely used packages ...**

## Plus some university collaborators

**Plus some university collaborators**

**Our DOE lab collaborations predate SciDAC by many years.**

## You may know our “Templates”

**www.siam.org**

**www.netlib.org**

**... ****but what we are doing now goes “in between” and far beyond!**

## Scope for TOPS

**Design and implementation of “solvers”**
**Time integrators**
**Nonlinear solvers**
**Optimizers**
**Linear solvers**
**Eigensolvers**
**Software integration**
**Performance optimization**

**(w/ sens. anal.)**

**(w/ sens. anal.)**

## Motivation for TOPS

**Not just algorithms, but vertically integrated software suites**
**Portable, scalable, extensible, tunable implementations**
**Motivated by representative apps, intended for many others**
**Starring ****hypre**** and ****PETSc****, among other existing packages**
**Driven by three applications SciDAC groups**
**LBNL-led “21st Century Accelerator” designs**
**ORNL-led core collapse supernovae simulations**
**PPPL-led magnetic fusion energy simulations**
**Coordinated with other ISIC SciDAC groups**

**Many DOE mission-critical systems are modeled by PDEs**
**Finite-dimensional models for infinite-dimensional PDEs must be large for accuracy**
**Qualitative insight is not enough (Hamming notwithstanding)**
**Simulations must resolve policy controversies, in some cases**
**Algorithms are as important as hardware in supporting simulation**
**Easily demonstrated for PDEs in the period 1945–2000 **
**Continuous problems provide exploitable hierarchy of approximation models, creating hope for “optimal” algorithms**
**Software lags both hardware and algorithms**

## Salient Application Properties

**Multirate**
**requiring fully or semi-implicit in time solvers**
**Multiscale**
**requiring finest mesh spacing much smaller than domain diameter**
**Multicomponent**
**requiring physics-informed preconditioners, transfer operators, and smoothers**

***PEP-II cavity model, c/o Advanced Computing for 21st Century Accelerator Science & Technology SciDAC group***

## Keyword: “Optimal”

**Convergence rate nearly independent of discretization parameters**
**Multilevel schemes for linear and nonlinear problems**
**Newton-like schemes for quadratic convergence of nonlinear problems**

**Convergence rate as independent as possible of physical parameters**
**Continuation schemes**
**Asymptotics-induced, operator-split preconditioning**

***Parallel multigrid on steel/rubber composite, c/o M. Adams, Berkeley-Sandia***

## It’s 2002; do you know what your solver is up to?

**Have you updated your solver in the past five years?**
**Is your solver running at 1-10% of machine peak?**
**Do you spend more time in your solver than in your physics?**
**Is your discretization or model fidelity limited by the solver?**
**Is your time stepping limited by stability?**
**Are you running loops *****around***** your analysis code? **
**Do you care how sensitive to parameters your results are?**

**If the answer to any of these questions is “yes”, please tell us at the poster session!**

## What we believe

**Many of us came to work on solvers through interests in applications**
**What we believe about ...**
**applications**
**users**
**solvers**
**legacy codes**
**software**
**      ... ****will impact how comfortable you are collaborating   with us**
**So please give us your comments on the next five slides!**

## What we believe about apps

**Solution of a system of PDEs is rarely a goal in itself **
**PDEs are solved to derive various outputs from specified inputs**
**Actual goal is characterization of a response surface or a design or control strategy**
**Together with analysis, sensitivities and stability are often desired**
**Software tools for PDE solution should also support related follow-on desires**

**No general purpose PDE solver can anticipate all needs**
**Why we have *****national laboratories*****, not *****numerical libraries *****for PDEs today**
**A PDE solver improves with user interaction**
**Pace of algorithmic development is very rapid**
**Extensibility is important**

## What we believe about users

**Solvers are used by people of varying numerical backgrounds**
**Some expect MATLAB-like defaults**
**Others want to control everything, e.g., even varying the type of smoother and number of smoothings on different levels of a multigrid algorithm**
**Multilayered software design is important**

**Users’ demand for resolution is virtually insatiable**
**Relieving resolution requirements with modeling (e.g., turbulence closures, homogenization) only defers the demand for resolution to the next level**
**Validating such models requires high resolution**
**Processor scalability and algorithmic scalability (optimality) are critical **

## What we believe about legacy code

**Porting to a scalable framework does not mean starting from scratch**
**High-value meshing and physics routines in original languages can be substantially preserved**
**Partitioning, reordering and mapping onto distributed data structures (that we may provide) adds code but little runtime**
**Distributions should include code samples exemplifying “separation of concerns”**

**Legacy solvers may be limiting resolution, accuracy, and generality of modeling overall**
**Replacing the solver may “solve” several other issues**
**However, pieces of the legacy solver may have value as part of a preconditioner**
**Solver toolkits should include “shells” for callbacks to high value legacy routines**

## What we believe about solvers

**Solvers are employed as part of a larger code**
**Solver library is not only library to be linked**
**Solvers may be called in multiple, nested places**
**Solvers typically make callbacks**
**Solvers should be swappable**
**Solver threads must not interfere with other component threads, including other active instances of themselves**

**Solvers are employed in many ways over the life cycle of an applications code**
**During development and upgrading, robustness (of the solver) and verbose diagnostics are important**
**During production, solvers are streamlined for performance  **
**Tunability is important**

## What we believe about software

**A continuous operator may appear in a discrete code in many different instances**
**Optimal algorithms tend to be hierarchical and nested iterative**
**Processor-scalable algorithms tend to be domain-decomposed and concurrent iterative**
**Majority of progress towards desired highly resolved, high fidelity result occurs through cost-effective low resolution, low fidelity parallel efficient stages**
**Operator abstractions and recurrence are important**

**Hardware changes many times over the life cycle of a software package**
**Processors, memory, and networks evolve annually**
**Machines are replaced every 3-5 years at major DOE centers**
**Codes persist for decades **
**Portability is critical **

## Why is TOPS needed?

**What is wrong?**
**Many widely used libraries are “behind the times” algorithmically **
**Logically innermost (solver) kernels are often the most computationally complex — should be designed from the inside out by experts and present the right “handles” to users**
**Today’s components do not “talk to” each other very well**
**Mixing and matching procedures too often requires mapping data between different storage structures (taxes memory and memory bandwidth)**

**What exists already?**
**Adaptive time integrators for stiff systems: variable-step BDF methods**
**Nonlinear implicit solvers: Newton-like methods, FAS multilevel methods**
**Optimizers (with constraints): quasi-Newton RSQP methods**
**Linear solvers: subspace projection methods (multigrid, Schwarz, classical smoothers), Krylov methods (CG, GMRES), sparse direct methods**
**Eigensolvers: matrix reduction techniques followed by tridiagonal eigensolvers, Arnoldi solvers**

## Nonlinear Solvers

**What’s ready?**
**KINSOL**** (LLNL) and ****PETSc ****(ANL)**
**Preconditioned Newton-Krylov (NK) methods with MPI-based objects**
**Asymptotically nearly quadratically convergent and mesh independent**
**Matrix-free implementations (FD and AD access to Jacobian elements)**
**Thousands of direct downloads (****PETSc****) and active worldwide “friendly user” base**
**Interfaced with ****hypre**** preconditioners (****KINSOL****)**
**Sensitivity analysis extensions (****KINSOL****)**
**1999 Bell Prize for unstructured implicit CFD computation at 0.227 Tflop/s on a legacy F77 NASA code**

**What’s next?**
**Semi-automated continuation schemes (e.g., pseudo-transience)**
**Additive-Schwarz Preconditioned Inexact Newton (ASPIN)**
**Full Approximation Scheme (FAS) multigrid**
**Polyalgorithmic combinations of ASPIN, FAS, and NK-MG, together with new linear solvers/preconditioners**
**Automated Jacobian calculations with parallel colorings**
**New grid transfer and nonlinear coarse grid operators**
**Guidance of trade-offs for cheap/expensive residual function calls**
**Further forward and adjoint sensitivities**

## Optimizers

**What’s ready?**
**TAO**** (ANL) and ****VELTISTO**** (CMU)**
**Bound-constrained and equality-constrained optimization**
**Achieve optimum in number of PDE solves independent of number of control variables**
**TAO**** released 2000, ****VELTISTO**** 2001**
**Both built on top of ****PETSc**
**Applied to problems with thousands of controls and millions of constraints on hundreds of processors**
**Used for design, control, parameter identification**
**Used in nonlinear elasticity, Navier-Stokes, acoustics**
**State-of-art Lagrange-Newton-Krylov-Schur algorithmics**

**What’s next?**
**Extensions to inequality constraints (beyond simple bound constraints)**
**Extensions to time-dependent PDEs, especially for inverse problems**
**Multilevel globalization strategies**
**Toleration strategies for approximate Jacobians and Hessians**
**“****Hardening” of promising control strategies to deal with negative curvature of Hessian**
**Pipelining of PDE solutions into sensitivity analysis**

## Linear Solvers

**What’s ready?**
**PETSc**** (ANL), ****hypre**** (LLNL), ****SuperLU ****(UCB), ****Oblio**** (ODU)**
**Krylov, multilevel, sparse direct**
**Numerous preconditioners, incl. BNN, SPAI, PILU/PICC**
**Mesh-independent convergence for ever expanding set of problems**
**hypre**** used in several ASCI codes and milestones to date**
**SuperLU**** in ScaLAPACK**
**State-of-art algebraic multigrid (****hypre****) and supernodal (****SuperLU****) efforts**
**Algorithmic replacements *****alone***** yield up to two orders of magnitude in DOE apps, before parallelization**

**What’s next?**
**Hooks for physics-based operator-split preconditionings**
**AMGe, focusing on incorporation of neighbor information and strong cross-variable coupling**
**Spectral AMGe for problems with geometrically oscillatory but algebraically smooth components**
**FOSLS-AMGe for saddle-point problems**
**Hierarchical basis ILU**
**Incomplete factorization adaptations of ****SuperLU**** **
**Convergence-enhancing orders for ILU**
**Stability-enhancing orderings for sparse direct methods for indefinite problems**

## Eigensolvers

**What’s ready?**
**LAPACK and ScaLAPACK symmetric eigensolvers (UCB, UTenn, LBNL)**
**PARPACK for sparse and nonsymmetric problems**
**Reductions to symmetric tridiagonal or Hessenberg form, followed by new “Holy Grail” algorithm**
**Holy Grail optimal (!): *****O(kn)***** work for *****k n*****-dimensional eigenvectors**

**What’s next?**
**Direct and iterative linear solution methods for shift-invert Lanczos for selected eigenpairs in large symmetric eigenproblems**
**Jacobi-Davidson projection methods for selected eigenpairs**
**Multilevel methods for eigenproblems arising from PDE applications**
**Hybrid multilevel/Jacobi-Davidson methods**

## Goals/Success Metrics

**Understand range of algorithmic options and their tradeoffs (e.g., memory versus time)**
**Can try all reasonable options easily without recoding or extensive recompilation**
**Know how their solvers are performing**
**Spend more time in their physics than in their solvers**
**Are intelligently driving solver research, and publishing joint papers with TOPS researchers**
**Can simulate *****truly new physics*****, as solver limits are steadily pushed back**

**TOPS users ****—**

## Expectations TOPS has of Users

**Tell us if you think our assumptions above are incorrect or incomplete**
**Be willing to experiment with novel algorithmic choices – optimality is *****rarely***** achieved beyond model problems without interplay between physics and algorithmics!**
**Adopt flexible, extensible programming styles in which algorithmic and data structures are not hardwired**
**Be willing to let us play with the real code you care about, but be willing, as well to abstract out relevant compact tests**
**Be willing to make concrete requests, to understand that requests must be prioritized, and to work with us in addressing the high priority requests**
**If possible, *****profile, ******profile******, ******profile***** before seeking help**

## TOPS may be for you!

**dkeyes@odu.edu**

**TOPS may be for you!**

**For more information**** ...**