# Presentation: 470456

##  A Current Overview of the Trilinos Project

**Jonathan Hu**
**Tenth Copper Mountain Conference on Iterative Methods**
**Monday, April 7****th****, 2008**

- Sandia is a multiprogram laboratory operated by Sandia Corporation, a Lockheed Martin Company,for the United States Department of Energy’s National Nuclear Security Administration under contract DE-AC04-94AL85000.

## This Evening’s Talks

- Kevin Long (7:55pm)
- "Building parallel multi-physics simulations with Sundance"
- Ross Bartlett (cancelled)
- "Stratimikos: Unified Access to Trilinos Linear Solver and Preconditioner Capabilities"
- Heidi Thornquist (8:20pm)
- "Belos: A Framework for Next-generation Iterative Linear Solvers"
- Vicki Howle (8:45pm)
- "Physics-based preconditioners in Meros"
- Chris Siefert (9:10pm)
- "Recent Algorithmic (and Practical) Developments in ML"

## Outline of Talk

- Background / Motivation / Evolution.
- (Some) capabilities in Trilinos
- Core
- Discretization/Optimization
- Solvers
- Concluding remarks.

## Trilinos Development Team

**Trilinos Development Team**

**Chris Baker **
- Developer of Anasazi, RBGen
**Ross Bartlett **
- Lead Developer of Thyra and Stratimikos
- Developer of Rythmos
**Pavel Bochev**
- Project Lead and Developer of Intrepid
**Paul Boggs **
- Developer of Thyra
**Eric Boman**
- Lead Developer of Isorropia
- Developer of Zoltan
**Todd Coffey**
- Lead Developer of Rythmos
**David Day**
- Developer of Komplex and Intrepid
**Karen Devine**
- Lead Developer of Zoltan
**Clark Dohrmann**
- Developer of CLAPS
**Michael Gee **
- Developer of ML, NOX
**Bob Heaphy **
- Lead Developer of Trilinos SQA
**Mike Heroux **
- Trilinos Project Leader
- Lead Developer of Epetra, AztecOO,
- Kokkos, Komplex, IFPACK, Thyra, Tpetra
- Developer of Amesos, Belos, EpetraExt, Jpetra

**Ulrich Hetmaniuk**
- Developer of Anasazi** **
**Robert Hoekstra **
- Lead Developer of EpetraExt
- Developer of Epetra, Thyra, Tpetra
**Russell Hooper**
- Developer of NOX
**Vicki Howle **
- Lead Developer of Meros
- Developer of Belos and Thyra
**Jonathan Hu **
- Developer of ML
**Sarah Knepper**
- Developer of Komplex
**Tammy Kolda **
- Lead Developer of NOX** **
**Joe Kotulski**
- Lead Developer of Pliris
**Rich Lehoucq **
- Developer of Anasazi and Belos
**Kevin Long **
- Lead Developer of Thyra,
- Developer of Teuchos
**Roger Pawlowski **
- Lead Developer of NOX

**Eric Phipps **
- Developer of LOCA, NOX, and Sacado
**Denis Ridzal**
- Lead Developer of Aristos and Intrepid
**Marzio Sala**
- Lead Developer of Didasko and IFPACK
- Developer of ML, Amesos
**Andrew Salinger **
- Lead Developer of LOCA
**Paul Sexton **
- Developer of Epetra and Tpetra
**Bill Spotz**
- Lead Developer of PyTrilinos
- Developer of Epetra, New_Package
**Ken Stanley **
- Lead Developer of Amesos and New_Package
**Heidi Thornquist **
- Lead Developer of Anasazi, Belos, RBGen, and Teuchos
**Ray Tuminaro **
- Lead Developer of ML  and Meros
**Jim Willenbring **
- Developer of Epetra and New_Package.
- Trilinos library manager** **
**Alan Williams **
- Lead Developer of Isorropia
- Developer of Epetra, EpetraExt, AztecOO, Tpetra

## Sandia Physics Simulation Codes

**Sandia Physics Simulation Codes**

- Element-based
- Finite element, finite volume, finite difference, network, etc...
- Large-scale
- Billions of unknowns
- Parallel
- MPI-based SPMD
- Distributed memory
- C++
- Object oriented
- Some coupling to legacy Fortran libraries

- Fluids

- Combustion

- Structures

- Circuits

- Plasmas

- MEMS

**Notes:**
Sandia simulates lots of different kinds of physics
Sandia’s physics simulation codes are mostly FE or FV discretized PDEs, some MD, circuit, etc...,  but all element-based

We can differentiate these codes with AD by exploiting this element-based structure

## Evolving Trilinos Solution

**Evolving Trilinos Solution**

- Beyond a “solvers” framework
- Natural expansion of capabilities to satisfy application and research needs

- Discretization methods, AD, Mortar methods, ...

## Trilinos Capabilities

|  | Objective | Package(s) |
| --- | --- | --- |
| Discretizations | Meshing & Spatial Discretizations | phdMesh, Intrepid, Sundance |
|  | Time Integration | Rythmos |
| Optimization | Optimization (SAND) | MOOCHO, Aristos |
| Methods | Automatic Differentiation | Sacado |
|  | Mortar Methods | Moertel |
| Core | Linear algebra objects | Epetra, Jpetra, Tpetra |
|  | Abstract interfaces | Thyra, Stratimikos, RTOp |
|  | Load Balancing | Zoltan, Isorropia |
|  | “Skins” | PyTrilinos, WebTrilinos, Star-P, ForTrilinos |
|  | C++ utilities, (some) I/O | Teuchos, EpetraExt, Kokkos, Triutils |
| Preconditioners | Multigrid methods | ML |
|  | Domain decomposition methods | CLAPS, IFPACK |
|  | ILU-type methods | AztecOO, IFPACK |
|  | Block preconditioners | Meros |
| Solvers | Iterative (Krylov) linear solvers | AztecOO, Belos, Komplex |
|  | Direct sparse linear solvers | Amesos |
|  | Direct dense linear solvers | Epetra, Pliris |
|  | Nonlinear system solvers | NOX, LOCA |
|  | Iterative eigenvalue solvers | Anasazi |

**Notes:**
*slide from Mike Heroux’s Trilinos101 presentation from the 2007 TUG

## Trilinos Framework

**Trilinos Framework**

- Trilinos1 provides a coordination of efforts:
- Leverages Sandia’s research in solvers, discretizations, optimization, graph algorithms
- Fundamental atomic unit is a _*package*_ (e.g., AztecOO, Zoltan)
- Includes core set of vector, graph and matrix classes.
- Provides common abstract solver API.
- Provides ready-made package infrastructure to incorporate new packages:
- Source code management (cvs, bonsai).
- Build tools (autotools).
- Automated regression testing (queue directories within repository).
- Communication tools (mailman mail lists).
- Specifies requirements and suggested practices for package SQA.
- In general allows us to categorize efforts:
- Efforts best done at the Trilinos level (useful to most or all packages).
- Efforts best done at a package level (peculiar or important to a package).
**Allows package developers to focus only on things that are unique to ****their package.**

- 1. Trilinos loose translation: “A string of pearls”

## Trilinos Package Concept

**Trilinos Package Concept**

- Library of common math algorithms developed by small team of experts
- Package interoperability
- Minimal _explicit_ dependencies
- Enabled via **configure**
- Accepts user data in Epetra or Thyra format
- Accepts runtime options via Teuchos parameter lists
- Uses Epetra for privata data
- Can use/can be used by Thyra abstract solver interfaces
- Python interfaces (PyTrilinos)
- Package autonomy
- Can be built independently of Trilinos.
- Has own self-contained CVS structure.
- Has own Bugzilla product and mail lists.
- Free to decide own algorithms, coding style, release contents, testing process, etc.
- Trilinos is not “monolithic”:
- You don’t need all of Trilinos to get things done.
- Any collection of packages can be combined and distributed.
- Current public release contains only 26 of the 30+ Trilinos packages.

- Optional, but as package matures, more of these tend to be satisfied

**Notes:**
Trilinos top layer source line count is less than 2% of total Trilinos line count

JJH: TODO animate to reduce text clutter

Do we need an explicit definition of package?

   package – autonomous library of common algorithms

## Whirlwind Tour of Packages Core        Discretizations & Methods       Solvers

**Whirlwind Tour of Packages**** ****Core        ****Discretizations & Methods       Solvers**

## Petra: Common Linear Algebra Foundation

**Petra: Common Linear Algebra Foundation**

- Provides distributed linear algebra objects (operator, matrix, vector)
- Three implementations
- Epetra – current production version.
- Real, double precision
- Stable core subset of C++ (circa 2000).
- C and Fortran interfaces
- Tpetra – templated scalar & ordinal fields, STL
- Jpetra – Java, portable to any JVM, interfaces to Java versions of MPI, BLAS, LAPACK

**Developers: Mike Heroux, Rob Hoekstra, Alan Williams, Paul Sexton**

## Portable utility package of commonly useful tools:

ParameterList class: key/value pair database, recursive capabilities.
LAPACK, BLAS wrappers (templated on ordinal and scalar type).
Dense matrix and vector classes (compatible with BLAS/LAPACK).
FLOP counters, timers.
Ordinal, Scalar Traits support: Definition of ‘zero’, ‘one’, etc.
Reference counted pointers / arrays, and more...
Takes advantage of advanced features of C++:
Templates
Standard Template Library (STL)
Teuchos::ParameterList:
Allows easy control of solver parameters.
XML format input/output.

- Portable utility package of commonly useful tools:
- ParameterList class: key/value pair database, recursive capabilities.
- LAPACK, BLAS wrappers (templated on ordinal and scalar type).
- Dense matrix and vector classes (compatible with BLAS/LAPACK).
- FLOP counters, timers.
- Ordinal, Scalar Traits support: Definition of ‘zero’, ‘one’, etc.
- Reference counted pointers / arrays, and more...
- Takes advantage of advanced features of C++:
- Templates
- Standard Template Library (STL)
- Teuchos::ParameterList:
- Allows easy control of solver parameters.
- XML format input/output.

**Developers: Roscoe Barlett, Kevin Long, Heidi Thornquist, Mike Heroux, **
**                      ****Paul Sexton, Kris Kampshoff, Chris Baker**

**Teuchos**

**Notes:**
Teuchos is being designed as an optional utility package that takes advantage of some of the more advanced features of C++, including templates and the STL.
Planned features for Teuchos include: a parameter list of arbitrary types, a memory management package, and templated interfaces to the BLAS, LAPACK and a dense matrix class.
My talk will focus on the templated interface to the BLAS. First, I’ll give you a brief background on the BLAS and C++ templates.

## Thyra

**Thyra**

- High-performance, abstract interfaces for linear algebra
- Offers flexibility through abstractions to algorithm developers
- Linear solvers (Direct, Iterative, Preconditioners)
- Abstraction of basic vector/matrix operations (dot, axpy, mv).
- Can use any concrete linear algebra library (Epetra, PETSc, BLAS).
- Nonlinear solvers (Newton, etc.)
- Abstraction of linear solve (solve *Ax=b*).
- Can use any concrete linear solver library:
- AztecOO, Belos, ML, PETSc, LAPACK
- Transient/DAE solvers (implicit)
- Abstraction of nonlinear solve.
- ... and so on.

**Developers:  Roscoe Bartlett, Kevin Long**

**Notes:**
Many different kinds of numerical problems and algorithms for solving those problems are used in scientific computing

Just some of the categories of problems and algorithms are:

## Zoltan

- Data Services for Dynamic Applications
- Dynamic load balancing
- Graph coloring
- Data migration
- Matrix ordering
- Partitioners:
- Geometric (coordinate-based) methods:
- Recursive Coordinate Bisection (Berger, Bokhari)
- Recursive Inertial Bisection (Taylor, Nour-Omid)
- Space Filling Curves (Peano, Hilbert)
- Refinement-tree Partitioning (Mitchell)
- Hypergraph and graph (connectivity-based) methods:
- Hypergraph Repartitioning PaToH (Catalyurek)
- Zoltan Hypergraph Partitioning
- ParMETIS  (U. Minnesota)
- Jostle (U. Greenwich)

**Developers: Karen Devine, Eric Boman, Robert Heaphy**

## Whirlwind Tour of Packages Core        Discretizations & Methods       Solvers

**Whirlwind Tour of Packages**** Core        ****Discretizations & Methods****       Solvers**

## Intrepid

***Interoperable Tools for Rapid Development of Compatible Discretizations***

**Intrepid**

- Intrepid offers an **innovative software design** for compatible discretizations:
-  allows access to FEM, FV and FD methods using a common API
-  supports hybrid discretizations (FEM, FV and FD) on unstructured grids
-  supports a variety of cell shapes:
-  standard shapes (e.g. tets, hexes): high-order finite element methods
-  arbitrary (polyhedral) shapes: low-order mimetic finite difference methods
-  enables optimization, error estimation, V&V, and UQ using fast invasive techniques (direct support for cell-based derivative computations or via automatic differentiation)

**Developers:  Pavel Bochev and Denis Ridzal**

**Notes:**
Reduce text at the top
Remove the red line from slide

## Sacado:  Automatic Differentiation

**Sacado:  Automatic Differentiation**

-   Efficient OO based AD tools optimized for element-level computations
-   Applies AD at “element”-level computation
- “Element” means finite element, finite volume, network device,...
-   Template application’s element-computation code
- Developers only need to maintain one templated code base
-   Provides three forms of AD
- Forward Mode:
- Propagate derivatives of intermediate variables w.r.t. independent variables forward
- Directional derivatives, tangent vectors, square Jacobians,                when **m ****≥ n**.
- Reverse Mode:
- Propagate derivatives of dependent variables w.r.t. intermediate variables backwards
- Gradients, Jacobian-transpose products (adjoints),                 when **n > m**.
- Taylor polynomial mode:
- Basic modes combined for higher derivatives.

**Developers:  Eric Phipps, David Gay**

**Notes:**
That takes me to the Sandia AD project called Sacado, which means roughly “I have derived” in Spanish.
This structure is the many Sandia application codes are element-based where the global computation is a linear combination of small element-level compuations
Element can mean an element in a finite element code, a cell in a finite volume code, a device in a network simulation, etc...
We can use AD to compute element-level derivatives that are manually summed into global derivative.
These element computations are well suited for AD since they involve many fewer independent and dependent variables, I.e., up to a few hundred as opposed to millions for the global computation, and also don’t involve any parallel communication, typically.
Because of simplicity of element-level computation, we can use simple but fast OO AD tools
We’ve been using this package Tfad for forward mode, but are rewriting it since it is no longer a supported library
We’re using a package called Rad developed by David Gay for reverse mode, which is a less general but much more efficient implementation of reverse-mode AD than other packages like ADOL-C
To apply these tools, you have to change the types in the code from floats/doubles to the AD types for Tfad and Rad
We can make that process more efficient by templating the application code using C++ templates
By instantiating the templates classes on floats/doubles, you get the original computation and by instantiating them on the AD types you get the AD computation
Means developers only need to develop and maintain one templated code base
Makes it easy to add new AD types since you only need to add new instantiations
We’ve been developing these ideas in Charon, a large-scale finite element semiconductor device and reacting fluid flow simulation code that you’ve heard about before
We’ve templated both the finite-element residual computation in Charon and the electric current calculation
Having AD just in Charon is allowing us to directly impact important projects such as QASPR
I just presented this work at an AD workshop at ICCS a week ago, which made me realize just how different this approach is than what people are typically doing in the AD community
This is a much more lower-level, intrusive approach designed to be used by code developers who are experts on the structure of their codes instead of a black-box, all or nothing approach for people who may not know anything about the internals of the code

Difference is the approach:  
  By applying AD at element-level , eliminate all of the difficulties of applying AD to a large-scale code (cross-country accumulation, MPI, etc...)
  By templating app, we can use simple, highly specialized tools that are fast (ADOL-C tries to do everything with one type)

## phdMesh

- Highly portable & compact
- _p_arallel _h_eterogeneous _d_ynamic unstructured mesh library
- parallel geometric proximity search
- dynamic load balancing
- Geometric proximity search is a performance constraining kernel for contact detection and multiphysics loose-coupling.
- Dynamic mesh modification is a performance constraining capability for adaptive applications.

- Exploits hybrid parallelization – single algorithm for distributed (MPI) + local (threads) + serial proximity search.
- Provides a *superset* of a much larger Sandia mesh subsystem’s capabilities with an API and implementation 1/10 of the size.
- Research effort for advanced applications concepts:
- scaling studies
- performance interaction between load balancing and geometric search
- explore hybrid distributed/local parallelization of other application kernels in anticipation of manycore architectures.

**Notes:**
phdMesh not only provides a first-of-a-kind explicit dynamics micro-application, but will also provide Trilinos with a fully-functional state-of-the-art mesh library in Trilinos 9.0.  

Furthermore, the algorithms developed in phdMesh are being incorporated into existing Sandia applications directly.

## Whirlwind Tour of Packages Core        Discretizations & Methods       Solvers

**Whirlwind Tour of Packages**** Core        Discretizations & Methods       ****Solvers**

## AztecOO

**AztecOO**

- Krylov subspace solvers: CG, GMRES, Bi-CGSTAB,...
- Preconditioners: Incomplete factorizations, SOR, polynomial
- Based on Aztec library (written in C):
- Extracted from MPSalsa reacting flow code.
- Installed in dozens of Sandia apps.
- 1900+ external licenses.
- AztecOO improves on Aztec by:
- Using Epetra objects for defining matrix and RHS.
- Providing more preconditioners/scalings.
- Using C++ class design to enable more sophisticated use.
- AztecOO interfaces allow:
- Continued use of Aztec for functionality.
- Introduction of new solver capabilities outside of Aztec.

**Developers:  Mike Heroux, Alan Williams, Ray Tuminaro**

## IFPACK: Algebraic Preconditioners

**IFPACK: Algebraic Preconditioners**

- Overlapping Schwarz preconditioners with incomplete factorizations, block relaxations, block direct solves.
- Accepts user matrix via abstract Epetra matrix interfaces
- Simple perturbation stabilizations, condition estimation
- Separates graph construction from factorization
- Interface to sparse direct solvers (KLU, UMFPACK, SuperLU, MUMPS, ScaLAPACK)
- Single, clear, consistent interface. Common look-and-feel for all classes
- Separation from specific solver details
- Serial and distributed solvers; Amesos handles data redistribution
- Native solvers:  KLU and Paraklete

**Developers:  Marzio Sala, Mike Heroux, Heidi Thornquist**

**Amesos**

**Developers: Heidi Thornquist Ken Stanley, Marzio Sala, Tim Davis**

**Notes:**
JJH: TODO animate to make less cluttered

## Anasazi

**Anasazi**

- Next-generation eigensolver library, written in templated C++.
- Provide a generic framework for developing iterative algorithms for solving large-scale eigenproblems.
- Algorithm implementation is accomplished through the use of traits classes and abstract base classes:
**Operator-vector products: ****	****Anasazi::MultiVecTraits****,  ****Anasazi::OperatorTraits**
**Orthogonalization:****	****Anasazi::OrthoManager, Anasazi::MatOrthoManager**
**Status tests:** 		**Anasazi::StatusTest, Anasazi::StatusTestResNorm**
**Iteration kernels:****	****Anasazi::Eigensolver**
**Eigensolver managers:** 	**Anasazi::SolverManager**
**Eigenproblem:** 	**Anasazi::Eigenproblem**
**Sort managers:** 	**Anasazi::SortManager**
- Currently has solver managers for three eigensolvers:
- Block Krylov-Schur
- Block Davidson
- LOBPCG
- Can solve:
- standard and generalized eigenproblems
- Hermitian and non-Hermitian eigenproblems
- real or complex-valued eigenproblems

**Developers:  Heidi Thornquist, Mike Heroux, Chris Baker, **
**                       ****Rich Lehoucq, Ulrich Hetmaniuk**

## NOX: Nonlinear Solvers

**NOX: Nonlinear Solvers**

- Suite of nonlinear solution methods
- Newton-type methods.
- Uses abstract vector and “group” interfaces:
- Flexible selection and tuning of various direction & line search strategies
- Epetra/AztecOO/ML, LAPACK, PETSc implementations of abstract vector/group interfaces.
- Designed to be easily integrated into existing applications.

**Developers:  Roger Pawlowski, Russ Hooper, Eric Phipps **

- Library of continuation algorithms
- Zero order, first order, & arc length continuation
- multi-parameter (via Henderson's MF Library)
- Turning point, pitchfork bifurcation, Hopf bifurcation
- Phase transition continuation
- Eigenvalue approximation (via ARPACK or Anasazi)

**LOCA**

**Developers: Andy Salinger, Eric Phipps**

## MOOCHO & Aristos

**MOOCHO & Aristos**

- MOOCHO: Multifunctional Object-Oriented arCHitecture for Optimization
- Large-scale invasive simultaneous analysis and design (SAND) using reduced space SQP methods.
- Aristos: Optimization of large-scale design spaces
- Invasive optimization approach based on full-space SQP methods.
- Efficiently manages inexactness in the inner linear system solves.

**Developer: Denis Ridzal**

**Developer: Roscoe Bartlett**

## Full “Vertical” Solver Coverage

**Full “Vertical” Solver Coverage**

- _Trilinos Packages_

**Notes:**
Many different kinds of numerical problems and algorithms for solving those problems are used in scientific computing

Just some of the categories of problems and algorithms are:

## Trilinos Availability / Information

**Trilinos Availability / Information**

- Trilinos and related packages are available via LGPL.
- Current release (8.0) is “click release”.  Unlimited availability.
- 1800+ Downloads since 3/05 (not including internal Sandia users).
- 750 registered users:
- 57% university, 11% industry, 20% gov’t.
- 35% European, 35% US, 10% Asian.
- Trilinos Release 8: September 2007.
- Trilinos Release 9: Fall, 2008
- Trilinos Awards:
- 2004 R&D 100 Award.
- SC2004 HPC Software Challenge Award.
- Sandia Team Employee Recognition Award.
- Lockheed-Martin Nova Award Nominee.
- Annual Trilinos User Group Meeting @ SNL
- talks available for download
- For more info, visit http://trilinos.sandia.gov