# Presentation: 095286

## NOX: An Object-Oriented Nonlinear Solver Package

- 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.

**NOX: An Object-Oriented Nonlinear Solver Package**
- _Roger Pawlowski_, Tamara Kolda, Russell Hooper,
- and John Shadid
- Sandia National Laboratories
- Albuquerque, NM
- Trilinos Workshop
- Copper Mountain Conference on Iterative Solvers
- March 30th, 2004

## Background

- NOX is the nonlinear solver package in the Trilinos Framework.
- NOX is being developed to:
- Enable robust and efficient solutions to systems of nonlinear equations.
- Provide a broad array of nonlinear algorithms through a single interface.
- Allow for rapid deployment of new solver technology into ASCI codes.
- Eliminate redundancies in ASCI code development.
- Written in C++: object-oriented design.
- Online documentation: _[http://](file:///doc/html/index.html)__[software.sandia.gov/nox](file:///doc/html/index.html)_

## Nonlinear Solution Algorithms

- Iterative Linear Solvers, Adaptive Forcing Terms

- Globalizations

**Notes:**
Originally, NOX was developed around Globalizations of Newton’s method.  The LDRD funding has allowed us to explore high and low order models with excitiing results.

Tensor has shown to be more robust 

## Example: Newton’s Method for F  (x) = 0

- _Example: Newton’s Method for __F  __(__x__)__ __= 0_

- Choose an initial guess x0
- For k = 0,1,2,...
- Compute Fk = F  (xk)
- Compute Jk where (Jk )ij = F  i(xk)/x  j
- Let dk = -Jk-1 Fk
- (Optional) Let k be a calculated step length
- Set xk+1 = xk + kdk
- Test for Convergence or Failure

- Building Blocks of NOX

## NOX Solvers(Iterate Control)

-   LineSearchBased
- Compute Direction
- Compute Step Length
- Scale direction by step length
- Update solution
- Check Convergence
-   TrustRegionBased (dogleg)
- Computes Newton Direction
- Computes Cauchy Direction
- Adjust trust region radius
- Update solution
- Check Convergence
-   InexactTrustRegionBased (Prerelease)
-   TensorBased (Prerelease)
-   UserDefined

- Solver is determined by passing a parameter list to a handle for the class:
**NOX::Solver::Manager solver(group, **
**                                                  ****StatusTests,             **
**                                                  ****ParameterList);**
**int status = solver.solve();**

- _Derived from NOX::Solver::Generic_
- bool  **reset**(NOX::Abstract::Group& grp,
-                    NOX::StatusTest::Generic& tests,
-                    NOX::Parameter::List& params)
- bool  **reset**(NOX::Abstract::Group& grp,
-                    NOX::StatusTest::Generic& tests)
- NOX::StatusTest::StatusType **getStatus**()
- NOX::StatusTest::StatusType **iterate**()
- NOX::StatusTest::StatusType **solve**()
- const NOX::Abstract::Group&
**getSolutionGroup**() const
- const NOX::Abstract::Group&
**getPreviousSolutionGroup**() const
- int **getNumIterations**() const
- const NOX::Parameter::List&
**getParameterList**() const

## NOX Directions

- Steepest Descent
- Newton
- Requires a linear solve
- Adaptive forcing terms
- Broyden
- Modified Newton with rank-1 updates to the most recently computed Jacobian
- Nonlinear-CG (Prerelease)
- Tensor (Prerelease)

_**User Defined Directions**_
- Derived from NOX::Direction::Generic
- Passed into the solver via parameter list using a direction template ctor.

_**User Defined Merit Function**_
- Derived from NOX::Parameter::MeritFunction
- Passed into the solver via parameter list using the NOX::Parameter::Arbitrary entry

**Direction is determined and constructed in a handle called a “Manager”:**
**NOX::Direction::Manager dir(PrintParams, DirectionParams);**

## NOX Line Searches

- Full Step
- Constant step size.
- Defaults to 1.0.
- Backtrack
- interval halving
- Polynomial Interpolation
- Quadratic and Cubic interpolation
- Requires a “Sufficient Decrease” Condition
- More’-Thuente
- Polynomial Interpolation
- Sufficient Decrease and Curvature Conditions
- Nonlinear-CG – (Prerelease)
- Curvilinear (Prerelease)

_**User Defined Line Searches**_
- Derived from NOX::LineSearch::Generic
- Passed into the solver via parameter list using a template constructor.

_**User Defined Merit Function**_
- Derived from NOX::Parameter::MeritFunction
- Passed into the solver via parameter list using the NOX::Parameter::Arbitrary entry

_**User Defined Norms**_
- Derived from NOX::Parameter::UserNorm
- Passed into the solver via parameter list using the NOX::Parameter::Arbitrary entry

**Line Searches are determined and constructed in a handle called a “Manager”:**
**NOX::LineSearch::Manager ls(PrintParams, LineSearchParams);**

## Mix-n-Match Solver Algorithms

**Solver**
**Line Search Based**
**Trust Region Based**
**Tensor Based**
**Direction**
**Newton**
**Broyden**
**Steepest Descent**
**Tensor**
**User-Defined**
**Line Search / Damping**
**Full Step**
**Backtrack**
**Polynomial/Quadratic**
**More’-Thuente**
**Curvilinear**
**User-Defined**

**NOX Documentation: **_[Related Pages](file:///doc/html/index.html)_

## Stopping Criteria (StatusTests)

*Highly Flexible Design:  Users build a convergence test hierarchy and registers it with the solver (via solver constructor or reset method).*
- Norm F: {Inf, One, Two}  {absolute, relative}
- Norm Update X: {Inf, One, Two}
- Norm Weighted Root Mean Square (WRMS):
- Max Iterations: Failure test if solver reaches max # iters
- FiniteValue: Failure test that checks for NaN and Inf on
- Stagnation: Failure test that triggers if the convergence rate fails a tolerance check for n consecutive iterations.
- Combination: {AND, OR}
- Users Designed: Derive from NOX::StatusTest::Generic

## Building a Status Test

- Fail if value of          becomes Nan or Inf

- Fail if we reach maximum iterations

- Converge if both:

## Status Tests Continued

_**User Defined are Derived from NOX::StatusTest::Generic**_
- NOX::StatusTest::StatusType **checkStatus**(const NOX::Solver::Generic &problem)
- NOX::StatusTest::StatusType
**checkStatusEfficiently**(const NOX::Solver::Generic &problem,
-                                      NOX::StatusTest::CheckType checkType)
- NOX::StatusTest::StatusType **getStatus**() const
- ostream& **print**(ostream &stream, int indent=0) const

**-- Status Test Results --******...........OR Combination -> ****  **...........AND Combination -> ****    **...........F-Norm = 5.907e-01 < 1.000e-08****                 (Length-Scaled Two-Norm, Absolute Tolerance)****    **...........WRMS-Norm = 4.794e+01 < 1****                 (Min Step Size:  1.000e+00 >= 1)****                 (Max Lin Solv Tol:  1.314e-15 < 0.5)****  **...........Finite Number Check (Two-Norm F) = Finite****  **...........Number of Iterations = 2 < 200**

**-- Final Status Test Results --****Converged....OR Combination -> ****  Converged....AND Combination -> ****    Converged....F-Norm = 3.567e-13 < 1.000e-08****                 (Length-Scaled Two-Norm, Absolute Tolerance)****    Converged....WRMS-Norm = 1.724e-03 < 1****                 (Min Step Size:  1.000e+00 >= 1)****                 (Max Lin Solv Tol:  4.951e-14 < 0.5)****  ??...........Finite Number Check (Two-Norm F) = Unknown**
**  ****??...........Number of Iterations = -1 < 200**

## NOX Interface

**Solver****Layer**

- Don’t need to directly access the vector or matrix entries, only manipulate the objects.
- NOX uses an abstract interface to manipulate linear algebra objects.
- Isolate the Solver layer from the linear algebra implementations used by the application.
- This approach means that NOX does NOT rely on any specific linear algebra format.
- Allows the apps to tailor the linear algebra to their own needs!
- Serial or Parallel
- Any Storage format: User Defined,** **LAPACK, PETSc, Epetra

## NOX::Abstract::Vector

- Initialization
- x = y
- x = |y|
- xi = 1/yi for i = 1 to n
- xi =  for i = 1 to n
- Length of Vector
- Scaling
- x =  x
- xi = xiyi for i = 1 to n
- Update
- x =  a +  x,
- x =  a +  b +  x

- Norm
-  k x k1,  k x k2 ,  k x k1
-  k x kw (weighted norm)
- Dot
- x ¢ y
- Clone (create a copy)
- y = x

- The solver is not allowed nor does it need explicit access to the vector – just the ability to manipulate it.

## NOX::Abstract::Group

-  x = Iterate
- Initialize
- Update
- Access
-  F = F  (x)
- Compute
- Access
-  J = Jacobian of F at x
- Compute
- Apply / Apply Transpose
- Apply Inverse
- Apply Preconditioning
-  n = Newton Vector
- Compute n = -J-1F to specified tolerance
- Access

-  g = Gradient of kF  (xk)k2
- g = JTF
- Access
- Clone

- The linear solver and application interface are combined into the *Group*. Vectors x, F, n, g are accessed as NOX::Abstract::Vector’s.
- Matrix J is never directly accessed!

## Code Demonstration

- _[Example Implementation](file:///simpleExample.C)_

## NOX Framework

**Solver****Layer**

## Linear Algebra Support Features

- NOX’s support libraries define a concrete implementation of the Abstract Vector and Group.
- We only require the user to implement a minimal interface derived from NOX::<Package>::Interface.

**bool ****computeF****(const Epetra_Vector &x, Epetra_Vector &f, FillType flag=F)**
**bool ****computeJacobian****(const Epetra_Vector &x, Epetra_Operator &Jac)**
** **
**bool ****computePrecMatrix****(const Epetra_Vector &x, Epetra_RowMatrix &M)**
** **
**bool ****computePreconditioner****(const Epetra_Vector &x, Epetra_Operator &M)**

**Group(NOX::Parameter::List& printingParams, NOX::Parameter::List& linearSolverParams, NOX::Epetra::Interface& i, NOX::Epetra::Vector& x, Epetra_Operator& J)**
**Group(NOX::Parameter::List& printingParams, NOX::Parameter::List& linearSolverParams, NOX::Epetra::Interface& i, NOX::Epetra::Vector& x, Epetra_Operator& J, Epetra_Operator& M)**

## The Epetra “Goodies”

- Matrix-Free Newton-Krylov Operator
- Derived from Epetra_Operator
- Can be used to estimate Jacobian action on a vector
- NOX::Epetra::MatrixFree
- Finite Difference Jacobian
- Derived from an Epetra_RowMatrix
- Can be used as a preconditioner matrix
- NOX::Epetra::FiniteDifference
- Graph Colored Finite Difference Jacobian
- Derived from NOX::Epetra::FiniteDifference
- Fast Jacobian fills – need connectivity/coloring graph
-  (NOX::Epetra::FiniteDifferenceColoring)
- Full interface to AztecOO using NOX parameter list
- Preconditioners: internal AztecOO, Ifpack, User defined
- Scaling object

## NOX Specific Configure Options

- Compiling NOX library in Trilinos:
- 	 --enable-nox
- Compiling prerelease code:
-     --enable-prerelease
- Using nox built-in linear algebra support:
- 	LAPACK: --enable-nox-lapack
-                  --enable-nox-lapack-examples
- 	Epetra: --enable-nox-epetra
- 		   --enable-nox-epetra-examples
- 	PETSc: --enable-nox-petsc
- 		   --enable-nox-petsc-examples

- Compiling the test suite:
- --enable-tests
- --enable-nox-tests
- Compiling LOCA library in Trilinos/NOX:
- 	 --enable-loca
- Specifying an install directory:
- 	--prefix=/usr/local

**> configure --enable-nox –enable-nox-epetra –prefix=/usr/local**
**> make**
**> make install**
**> make dox**

## Sandia Applications

- Primary NOX Team: Tammy Kolda, Roger Pawlowski, Russ Hooper

## Summary

- Key Features
- Object-oriented C++ library
- Large number of cutting-edge algorithms
- Can use any linear algebra implementation
- Easy interface
- User Flexibility:  Add solvers, directions, line searches, convergence tests
- NOX Support libraries
- Fast integration – reduced interface
- parallel iterative solvers (AztecOO, PETSc)
- preconditioners (Ifpack, ML, Aztec, PETSc)
- Matrix-Free Newton-Krylov
- Matrix Estimation: Finite Difference/Coloring

## NOX Contributors (Ideas, Code, and Testing)

_**Sandia**_
- Tammy Kolda *
- Roger Pawlowski *
- Russ Hooper *
- Brett Bader*
- John Shadid
- Todd Coffey *
- Andy Salinger (LOCA) *
- Eric Phipps (LOCA) *
- Bill Spotz * (PyNOX)
- Mike Heroux (Trilinos)
- Scott Hutchinson (Xyce)
- Rob Hoekstra (Xyce)
- Eric Keiter (Xyce)
- Alan Williams (SIERRA)
- Tom Smith (Premo)
- Alfred Lorber (Premo)
- Tom Brunner (Alegra)

_**Academics**_
- Homer Walker, WPI
- Joseph Simonis, WPI
- Tim Kelley, NCSU
- Matthew Lasater, NCSU
- Bobby Schnabel, UCB
- Richard Byrd, UCB
- Ryan McKenzie, Kentucky
- Craig Douglas, Kentucky

- * NOX Developer

_**NOX Information**_
**Tammy Kolda:   tgkolda@sandia.gov**
**Roger Pawlowski:  rppawlo@sandia.gov**
**Download:  http://software.sandia.gov/nox**
**Trilinos: http://software.sandia.gov/trilinos**