Trilinos Linear and Eigen Solver Capabilities

 

Introduction
New in Trilinos 9.0: Interoperability with PETSc 
Iterative linear solvers
Direct solvers
Preconditioners
Eigen-solvers
Reduced basis generation
Future Plans

Introduction


Trilinos provides a wide-variety of solution methods for linear and eigen systems.  The purpose of this page is to give an overview of the capabilities in the areas of iterative and direct solvers, preconditioners, high-level interfaces, and eigen-solvers.  Unless otherwise noted, all packages have been publicly released.

New in Trilinos 9.0: Interoperability with PETSc


PETSc application developers can now create and apply virtually any Trilinos linear solver or preconditioner within their application code.   This is now possible via the Epetra_PETScAIJMatrix() class, which is a lightweight wrapper for the PETSc aij matrix type.  This interface gives access to virtually all solvers described on this page.  In particular, a PETSc application has full access to the algebraic multigrid methods in ML and the advanced Krylov recycling techniques in Belos.

Iterative linear solvers

 

AztecOO: Preconditioners and Krylov subspace methods

Point-of-contact: Mike Heroux
http://trilinos.sandia.gov/packages/aztecoo
 
AztecOO includes a number of Krylov iterative methods such as conjugate gradient (CG), generalized minimum residual (GMRES) and stabilized biconjugate gradient (BiCGSTAB) to solve systems of equations.  AztecOO may use a variety of internally implemented preconditioners, such as SOR, polynomial, domain decomposition, and incomplete factorization preconditioning, as well as preconditioners provided by other Trilinos packages.  AztecOO also fully contains the C-language Aztec linear solver package, so any application that is using Aztec can use the AztecOO library in place of Aztec.  Note that only bug fixes are being applied to AztecOO.   Active algorithm development is taking place in Belos.

 

Belos: Classical and block Krylov subspace methods

Points-of-contact: Heidi Thornquist and Mike Parks
http://trilinos.sandia.gov/packages/belos
 
Belos provides next-generation iterative linear solvers and a powerful linear solver developer framework. This framework includes the following abstract interfaces and implementations:

        

Komplex: Complex-valued system solver

Points-of-contact: Mike Heroux and David Day
http://trilinos.sandia.gov/packages/komplex

KOMPLEX is an add-on module to AZTEC that allows users to solve complex-valued linear systems.  KOMPLEX solves a complex-valued linear system Ax=b by solving an equivalent real-valued system of twice the dimension.

Stratimikos: High level linear solver interface

Point-of-contact: Roscoe Bartlett
http://trilinos.sandia.gov/packages/stratimikos


Stratimikos contains a unified set of Thyra-based wrappers to linear solver and preconditioner capabilities in Trilinos.  Stratimikos is also a place where unified testing of linear solvers and preconditioners can be performed. Currently, Stratimikos essentially consists of the single class Stratimikos::DefaultLinearSolverBuilder, which provides uniform access to linear solver capabilities in Trilinos.  The underlying operator can be viewed as either an Epetra_CrsMatrix object or as an Epetra_RowMatrix object. This class builds linear solvers using the Thyra linear solver and preconditioner factory adapters (e.g. for AztecOO, Belos, Amesos, Ifpack, and ML).  The linear solver and preconditioner factories are returned as Thyra::LinearOpWithSolveFactoryBase and Thyra::PreconditionerFactoryBase objects respectively.  Given these objects, you can solve individual linear systems (see examples).


The class Stratimikos::DefaultLinearSolverBuilder is parameter-list driven. An example parameter list in XML form that selects AztecOO and Ifpack is shown below:

<ParameterList>
  <Parameter name="Linear Solver Type" type="string" value="AztecOO"/>
  <ParameterList name="Linear Solver Types">
    <ParameterList name="AztecOO">
      <ParameterList name="Forward Solve">
        <ParameterList name="AztecOO Settings">
          <Parameter name="Aztec Solver" type="string" value="GMRES"/>
          <Parameter name="Convergence Test" type="string" value="r0"/>
          <Parameter name="Size of Krylov Subspace" type="int" value="300"/>
        </ParameterList>
        <Parameter name="Max Iterations" type="int" value="400"/>
        <Parameter name="Tolerance" type="double" value="1e-13"/>
      </ParameterList>
      <Parameter name="Output Every RHS" type="bool" value="1"/>
    </ParameterList>
  </ParameterList>
  <Parameter name="Preconditioner Type" type="string" value="Ifpack"/>
  <ParameterList name="Preconditioner Types">
    <ParameterList name="Ifpack">
      <Parameter name="Prec Type" type="string" value="ILU"/>
      <Parameter name="Overlap" type="int" value="1"/>
      <ParameterList name="Ifpack Settings">
        <Parameter name="fact: level-of-fill" type="int" value="2"/>
      </ParameterList>
    </ParameterList>
  </ParameterList>
</ParameterList>

The parameter "Linear Solver Type" selects the linear solver type (currently supported are "Amesos", "AztecOO", and "Belos"). The parameter "Preconditioner Type" selects the preconditioner type (currently supported are "None", "ML", and "Ifpack").

Many other example XML input files (e.g. *.xml) can be found in the directory stratimikos/example. The full listing of supported parameters can be found in the documentation for Stratimikos::DefaultLinearSolverBuilder.

The example simple_stratimikos_example.cpp shows how to wrap Epetra objects and then use Stratimikos::DefaultLinearSolverBuilder to solve a linear system.  The example MixedOrderPhysicsBasedPreconditioner.cpp shows the use of Stratimikos in a more sophisticated context.

See how all of the examples and tests are run by looking at stratimikos/test/definition.

Direct linear solvers


Amesos: direct sparse linear solver interface

Point-of-contact: Heidi Thornquist
http://trilinos.sandia.gov/packages/amesos

Amesos is a set of C++ interfaces to serial and parallel sparse direct solvers. Amesos contains two nice sparse solvers: KLU and Paraklete. KLU is serial, while Paraklete (distributed with Trilinos 7.0 or higher) is a parallel solver. Amesos also offers an interface to LAPACK, and several other well-know solvers available on the web.

The main idea of Amesos is to give a high-level view of direct solvers, as composed by four main phases:


1)       specification of parameters
2)       initialization of the solver, using matrix sparsity only
3)       computation of the factors
4)       solution of the linear system

Amesos insulates the user from all the low-level details typical of direct solvers, like the matrix format, data distribution for the matrix, the solution and the right-hand side, parameter settings, and so on. Amesos is not based on any matrix format; instead, an matrix interface (specified by using the Epetra_RowMatrix class) is adopted. This facilitates the usage of Amesos classes in any projects whose matrix can be wrapped as an Epetra_RowMatrix.

Pliris: direct dense linear solver

Point-of-contact: Joe Kotulski
http://trilinos.sandia.gov/packages/pliris
 
Pliris is an object-oriented interface to a LU solver for dense matrices on parallel platforms. These matrices are double precision real matrices distributed on a parallel machine.

The matrix is torus-wrap mapped onto the processors(transparent to the user) and uses partial pivoting during the factorization of the matrix.  Each processor contains a portion of the matrix and the right hand sides determined by a distribution function to optimally load balance the computation and communication during the factorization of the matrix. The general prescription is that no processor can have no more(or less) than one row or column of the matrix than any other processor.  Since the input matrix is not torus-wrapped permutation of the results is performed to "unwrap the results" which is transparent to the user.

Preconditioners

 

Ifpack: Point preconditioning, incomplete factorizations, and classical domain decomposition

Point-of-contact: Mike Heroux
http://trilinos.sandia.gov/packages/ifpack
 
IFPACK provides a suite of object-oriented algebraic preconditioners. IFPACK constructors expect an Epetra_RowMatrix object for construction.   IFPACK objects interact well with other Trilinos classes. In particular, IFPACK can be used as a preconditioner for AztecOO and smoother in ML.

IFPACK contains one-level domain decomposition preconditioners of overlapping type. Each ``subdomain'' is defined by the set of rows assigned to a given processors. Several options are available for the local solution, ranging from simple relaxation schemes, to incomplete factorizations, to direct solvers (through the Amesos package).

ML: smoothed aggregation algebraic multigrid

Points-of-contact: Ray Tuminaro and Jonathan Hu
http://trilinos.sandia.gov/packages/ml
 
ML contains a variety of parallel multigrid schemes for preconditioning or solving large sparse linear systems of equations arising primarily from elliptic PDE discretizations.  The main methods in ML are
Within each of these methods there are several different algorithms to guide the type of coarsening and the inter-grid transfers (including the ability to drop weak coupling within the operator during inter-transfer construction).  Additionally, ML can use Zoltan to rebalance coarse grid operators for better parallel performance.
 
ML provides a variety of smoothers:  SOR, polynomial, Ifpack domain decomposition and incomplete factorizations, and Aztec methods.  Coarse-grid solvers include the afore-mentioned smoothers, as well as any direct method available through Amesos.

ML can also be used as a framework to generate new multigrid methods. Using ML's internal aggregation routines and Galerkin products, it is possible to focus on new types of inter-grid transfer operators without having to address the cumbersome aspects of generating an entirely new parallel algebraic multigrid code. We have used this flexibility to produce special multilevel methods using coarse grid finite element functions to serve as inter-grid transfers


Claps: classical and BDDC domain decomposition methods

Point-of-contact: Clark Dohrmann
http://trilinos.sandia.gov/packages/claps
Release status: Sandia only
 
The Claps package is a collection of domain decomposition preconditioners and solvers. Currently, there are two preconditioners in the package. The first one is based on classical overlapping Schwarz with a partition of unity coarse space, while the second one is based on a primal iterative sub-structuring approach. The latter one is often referred to as BDDC in the literature. An approach for accommodating linear constraint equations is also included.

The Claps package is currently in transition.  We plan on replacing the partition of unity coarse space for overlapping Schwarz with one based on energy-minimizing discrete harmonic extensions. In order to reduce the memory and computational expenses of direct solvers for the local and coarse problems, options will be put in place to replace them with inexact ones based on multilevel preconditioners or incomplete factorizations.

Meros: Segregated preconditioners for incompressible fluid flow

Point-of-contact: Victoria Howle (victoria.howle AT ttu DOT edu)
http://trilinos.sandia.gov/packages/meros
 
Meros provides scalable block preconditioning for problems that couple simultaneous solution variables such as Navier-Stokes problems.  The initial focus of Meros is on preconditioners for the incompressible Navier-Stokes equations in two- or three-dimensions.
 
Linearization and discretization of the incompressible Navier-Stokes equations by finite elements, finite differences or finite volumes leads to a two-by-two block linear system of equations.  These block systems must be solved at each step of a nonlinear (Picard or Newton) iteration, or at each time step.
 
Block preconditioners are useful for a number of reasons:
   
Meros includes the following classes of methods:
 

Eigen-solvers

 

Anasazi: parallel eigen-solvers

Points-of-contact: Heidi Thornquist and Chris Baker
http://trilinos.sandia.gov/packages/anasazi

Anasazi is an extensible and interoperable framework for large-scale eigenvalue algorithms. The motivation for this framework is to provide a generic interface to a collection of algorithms for solving large-scale eigenvalue problems. Anasazi is interoperable because both the matrix and vectors (defining the eigenspace) are considered to be opaque objects---only knowledge of the matrix and vectors via elementary operations is necessary. An implementation of Anasazi is accomplished via the use of interfaces. Current interfaces available include Epetra and so any libraries that understand Epetra matrices and vectors (such as AztecOO) may also be used in conjunction with Anasazi.

One of the goals of Anasazi is to allow the user the flexibility to specify the data representation for the matrix and vectors and so leverage any existing software investment. The algorithms that are currently available through Anasazi are block Krylov-Schur, block Davidson, and locally-optimal block preconditioned conjugate gradient (LOBPCG) method.

Reduced order bases


RBGen: reduced order basis generation

Point-of-contact: Heidi Thornquist
Release status: Sandia only

The RBGen package provides a data and system analysis toolkit, enabling the parallel computation of reduced-order bases for large-scale applications such as model-order reduction and data mining.

Future Plans

  1. Refactor of ML
  2. New templated incomplete factorization package
  3. New domain decomposition package
  4. Additional direct factorization techniques
  5. Refactor of Ifpack