# Presentation: 250328

## AmesosSparse Direct Solver Package

**Ken Stanley, Rob Hoekstra, Marzio Sala, Tim Davis, Mike Heroux **
**Trilinos Users Group**
**Albuquerque **
**3 Nov 2004**

**Notes:**
 The goal of Amesos, is to make AX = B as easy as it sounds, at least for sparse direct solvers.  

## What’s new in Amesos

**Release - in Trilinos 4.0**
**Solvers - Klu, Mumps, SuperLU**
**Interface - Base Solver and Factory Method**
**Epetra_RowMatrix support**
**Future – Distributed Memory Solver**

**Notes:**
 The goal of Amesos, is to make AX = B as easy as it sounds, at least for sparse direct solvers.  

## Amesos Interface to sparse direct solvers

**Common clean interface **
**Pick a solver!**
**Any solver on any (Epetra) matrix**
**Trilinos package **
**Autotooled configuration & build**
**Nightly testing**
**Bug Tracking**

**Notes:**
The goal of Amesos, is to make AX = B as easy as it sounds, at least for sparse direct solvers.

## 
Epetra_LinearProblem Problem( A, x, b);
Amesos Afact;
Amesos_BaseSolver* Solver = Afact.Create( “Klu”, Problem ) ; 

Solver->SymbolicFactorization(  ) ;   
Solver->NumericFactorization(  ) ;   
Solver->Solve(  ) ; 

**Epetra_LinearProblem Problem( A, x, b);**
**Amesos Afact;**
**Amesos_BaseSolver* Solver = Afact.Create( “Klu”, Problem ) ; **
**Solver->SymbolicFactorization(  ) ;   **
**Solver->NumericFactorization(  ) ;   **
**Solver->Solve(  ) ; **

**Calling Amesos**

**Notes:**
The best User’s Manual is the one that you never have to open.  

## Amesos Solvers

**Klu:  Built-in.  Serial unsymmetric  [Davis] **
**SuperLU:  Serial unsymmetric [Li et al.]**
**UMFPACK:  Serial unsymmetric [Davis]**
**SuperLUdist:  Parallel unsymmetric [Li et al.]**
**MUMPS:  Parallel unsymmetric [Amestoy et al.]**
**DSCPACK:  Parallel Symmetric [Ragavan]**

**Notes:**
The goal of Amesos, is to make AX = B as easy as it sounds, at least for sparse direct solvers.

## Amesos User Guide:
http://software.sandia.gov/trilinos/packages/amesos
Build Amesos
CONFIGURE:
./configure –enable-amesos
BUILD:
make 
TEST:
cd amesos/test
source AmesosKlu.exe

_**[http://software.](ttp://software.sandia.gov/trilinos/packages/amesos)**__**[sandia](ttp://software.sandia.gov/trilinos/packages/amesos)**__**[.](ttp://software.sandia.gov/trilinos/packages/amesos)**__**[gov](ttp://software.sandia.gov/trilinos/packages/amesos)**__**[/](ttp://software.sandia.gov/trilinos/packages/amesos)**__**[trilinos](ttp://software.sandia.gov/trilinos/packages/amesos)**__**[/packages/](ttp://software.sandia.gov/trilinos/packages/amesos)**__**[amesos](ttp://software.sandia.gov/trilinos/packages/amesos)**_
**Build Amesos**
**CONFIGURE:**
**./configure –enable-amesos**
**BUILD:**
**make **
**TEST:**
**cd amesos/test**
**source AmesosKlu.exe**

**Getting started: ****Building Amesos**

## 
Epetra_LinearProblem Problem( A, x, b);
Amesos Afact;
Amesos_BaseSolver* Solver = Afact.Create( “Klu”, Problem ) ; 

Solver->SymbolicFactorization(  ) ;   
For () { 
    // Changes to the data, but not the non-zero pattern
    Solver->NumericFactorization(  ) ;   
    Solver->Solve(  ) ; 
}

**Epetra_LinearProblem Problem( A, x, b);**
**Amesos Afact;**
**Amesos_BaseSolver* Solver = Afact.Create( “Klu”, Problem ) ; **
**Solver->SymbolicFactorization(  ) ;   **
**For () { **
**    ****// Changes to the data, but not the non-zero pattern**
**    ****Solver->NumericFactorization(  ) ;   **
**    ****Solver->Solve(  ) ; **
**}**

**Calling Amesos****Same Structure Different Data**

## 
Epetra_LinearProblem Problem( A, x, b);
Amesos Afact;
Amesos_BaseSolver* Solver = Afact.Create( “Klu”, Problem ) ; 

Solver->SymbolicFactorization(  ) ;   
Solver->NumericFactorization(  ) ;  
For ( ) {  
   //  Changes to b
  Solver->Solve(  ) ; 
}

**Epetra_LinearProblem Problem( A, x, b);**
**Amesos Afact;**
**Amesos_BaseSolver* Solver = Afact.Create( “Klu”, Problem ) ; **
**Solver->SymbolicFactorization(  ) ;   **
**Solver->NumericFactorization(  ) ;  **
**For ( ) {  **
**   ****//  Changes to b**
**  ****Solver->Solve(  ) ; **
**}**

**Calling Amesos****Multiple Solves, Changing RHS**

## 
Epetra_Multivector x, b; 
Epetra_LinearProblem Problem( A, x, b);
Amesos Afact;
Amesos_BaseSolver* Solver = Afact.Create( “Klu”, Problem ) ; 

Solver->SymbolicFactorization(  ) ;   
Solver->NumericFactorization(  ) ;   
Solver->Solve(  ) ; 

**Epetra_Multivector x, b; **
**Epetra_LinearProblem Problem( A, x, b);**
**Amesos Afact;**
**Amesos_BaseSolver* Solver = Afact.Create( “Klu”, Problem ) ; **
**Solver->SymbolicFactorization(  ) ;   **
**Solver->NumericFactorization(  ) ;   **
**Solver->Solve(  ) ; **

**Calling Amesos****Blocked Right Hand Sides**

**Notes:**
The best User’s Manual is the one that you never have to open.  

## 
Epetra_LinearProblem Problem( A, x, b);
Amesos Afact;
Amesos_BaseSolver* Solver = Afact.Create( “Klu”, Problem ) ; 
ParamList.SetParam( “Refactorize”, true );
Solver->SetParameters( ParamList );

Solver->SymbolicFactorization(  ) ;   
For () { 
    // Small changes to the data, Same non-zero pattern
    Solver->NumericFactorization(  ) ; 
    Solver->Solve(  ) ; 
}

**Epetra_LinearProblem Problem( A, x, b);**
**Amesos Afact;**
**Amesos_BaseSolver* Solver = Afact.Create( “Klu”, Problem ) ; **
**ParamList.SetParam( “Refactorize”, true );**
**Solver->SetParameters( ParamList );**
**Solver->SymbolicFactorization(  ) ;   **
**For () { **
**    ****// Small ****changes to the data, Same non-zero pattern**
**    ****Solver->NumericFactorization(  ) ; **
**    ****Solver->Solve(  ) ; **
**}**

**Calling Amesos****Pivotless Re-factorization**

## Amesos Switching solvers

**Afact.Create( “Klu”, Problem ) ; **
**-> ****Afact.Create( “****SuperLUdist****”, Problem ) ;**
**Amesos redistributes data (serial to parallel, etc.)**
**Heuristics consistent across solvers**
**Parameter List **
**Allows individual control over each solver **
**Amesos fills in capabilities**
**Transpose **
**Blocked right hand sides **

**Notes:**
The goal of Amesos, is to make AX = B as easy as it sounds, at least for sparse direct solvers.

##  Amesos User Guide: http://software.sandia.gov/trilinos/packages/amesos

Download source from the authors’ website
Modify make.inc 
“make” 
 Check output of example run

Future Work 
Work with authors to Autotool their libraries

**Download source from the authors’ website**
**Modify make.inc **
**“****make” **
** ****Check output of example run**
**Future Work **
**Work with authors to Autotool their libraries**

**Amesos ****Adding third party libraries**

## Amesos User Guide:
http://software.sandia.gov/trilinos/packages/amesos
Build Amesos
CONFIGURE: (e.g. DSCPACK )
./configure –enable-amesos –enable-amesos-dscpack –with-libs=“-L/dir –ldscpack” -with-incdirs=-I/dir/SRC
BUILD:
make 
TEST:
cd amesos/test
source AmesosDscpack.exe

_**[http://software.](ttp://software.sandia.gov/trilinos/packages/amesos)**__**[sandia](ttp://software.sandia.gov/trilinos/packages/amesos)**__**[.](ttp://software.sandia.gov/trilinos/packages/amesos)**__**[gov](ttp://software.sandia.gov/trilinos/packages/amesos)**__**[/](ttp://software.sandia.gov/trilinos/packages/amesos)**__**[trilinos](ttp://software.sandia.gov/trilinos/packages/amesos)**__**[/packages/](ttp://software.sandia.gov/trilinos/packages/amesos)**__**[amesos](ttp://software.sandia.gov/trilinos/packages/amesos)**_
**Build Amesos**
**CONFIGURE: (e.g. DSCPACK )**
**./configure –enable-amesos –enable-amesos-dscpack –with-libs=“-L/dir –ldscpack” -with-incdirs=-I/dir/SRC**
**BUILD:**
**make **
**TEST:**
**cd amesos/test**
**source AmesosDscpack.exe**

**Building Amesos****with additional third party libraries**

## Amesos Future Work

**Additional third party libraries **
**Allow any ordering to be used by any package**
**Extended precision iterative refinement**
**Enhance nightly testing**
**Performance**
**Memory leaks**
**Check code coverage**
**Work with authors to autotool their libraries**

**Notes:**
The goal of Amesos, is to make AX = B as easy as it sounds, at least for sparse direct solvers.

## Amesos [Davis, Stanley, Heroux]Distributed memory solver goals:

**Built into Amesos in 2005**
**Simple design**
**Full partial pivoting**
**Allowing restrictions may improve performance**
**Leverage existing technology**
**Epetra support**
**Amesos serial solvers**
**Partitioners**
**Static Pivoting**

## AmesosDistributed memory solver overview

**Reduction to Block Triangular form**
**Partition each block**
**Use “enhanced” Amesos serial solver for local partition factorization**
**Restricted Pivoting**
**Partial Factorization**
**Add Schur Complements to root node**
**Use any Amesos solver on the root node**

## No Pivot Case

- Factor
- Leaves

- Compute
- Schur Complements

- Update
- Root Node

- Factor Root

## Static pivoting [Li; Demmel]
Local pivoting  

Delayed pivoting

Singly bordered 
     form [J. Scott]
     augmented matrix

**Local pivoting  **
**Delayed pivoting**
**Singly bordered **
**     ****form [J. Scott]**
**     ****augmented matrix**

** ****Pivoting Strategies**

**Notes:**
The goal of Amesos, is to make AX = B as easy as it sounds, at least for sparse direct solvers.

## Static and Local Pivoting

**Static pivoting [Li; Demmel]**
**Reorder and scale rows and columns to promote diagonal dominance**
**Imperfect but works well in practice**
**Can reduce need for pivoting even if it doesn’t eliminate it**
**Local pivoting  **
**Requires no additional communication**

**Notes:**
The goal of Amesos, is to make AX = B as easy as it sounds, at least for sparse direct solvers.

## Delayed pivoting 

**Delay columns **
**   ****which do not allow**
**   ****an acceptable pivot choice**
** ****Allow root node         to grow**
**Threshold pivoting reduces communication**
** ****Requires:**
**A serial solver which supports**
**   ****delayed pivoting**
**Mutable root node size**

**Notes:**
The goal of Amesos, is to make AX = B as easy as it sounds, at least for sparse direct solvers.

## Augment matrix, adding 
     columns [-I;I] to split
           and        onto separate
     rows
Allows full partial pivoting
If       and        are not used 
     as pivots, matrix can be
     collapsed to original size 

**     ****columns ****[-I;I] ****to split**
**           ****and        onto separate**
**     ****rows**
**Allows full partial pivoting**
**If       and        are not used **
**     ****as pivots, matrix can be**
**     ****collapsed to original size **

**Singly bordered form**

**Notes:**
The goal of Amesos, is to make AX = B as easy as it sounds, at least for sparse direct solvers.

## Amesos Interface to sparse direct solvers

**Simple interface **
**SuperLU, KLU, MUMPS, UMFPACK, DSCPACK, SuperLUdist**
**Built-in serial solver **
**Future:**
**Built-in distributed memory solver**
**More third party solvers**
**Extended precision iterative refinement**

**Notes:**
The goal of Amesos, is to make AX = B as easy as it sounds, at least for sparse direct solvers.