.. _implicit-feti:

********************
FETI Equation Solver
********************

FETI is a domain-decomposition-based parallel iterative linear solver that can be used to compute the action of the global tangent stiffness matrix for the nonlinear CG solver [:footcite:`impsol:ref:farhat1`, :footcite:`impsol:ref:farhat2`]. FETI uses a direct solver on each domain and iteratively solves for Lagrange multiplier fields at the domain boundaries. 

FETI also generates a coarse grid matrix from the global tangent stiffness matrix. The coarse matrix is used to accelerate convergence and distribute the error more evenly across the local mesh domains. The highest eigenvalue :math:`\lambda_1` and lowest eigenvalue :math:`\lambda_N` of the coarse matrix are relatively inexpensive to calculate. These eigenvalues are then used to compute the condition number of the coarse matrix :math:`\kappa= \lambda_1 / \lambda_N`. If :math:`\kappa` is excessively large, then a warning is printed to the log file, indicating that the problem is ill-posed.

Under typical usage, the FETI domains correspond to the portions of the model owned by each processor. If a model is run on a single processor, FETI  behaves as a direct solver. Because large models are typically run using many processors, FETI uses significantly lower total computing resources than a direct solution method of the whole problem would require. The large number of small direct solutions may be performed in parallel.

.. 
  The FETI algorithm is an iterative linear solver algorithm that we use to solve for the direction (K g = r, where r is the residual, K is the tangent stiffness matrix, and g is the gradient direction) used within the adagio nonlinear conjugate gradient (cg) algorithm. FETI is a domain decomposition method that splits the tangent stiffness matrix into a local (on processor) matrix and a coarse matrix that is automatically generated within the algorithm. Since the coarse matrix is constructed from the global system matrix, it has a lot of useful information that can be extracted about the conditioning of the problem. We use a simple power method iteration on the coarse matrix to determine the highest and lowest eigenvalues which are used to compute the condition number of the coarse matrix (= max eigenvalue / min eigenvalue). In a nutshell, this message is a diagnostic tool where we have set (somewhat arbitrarily) a large condition number is > :math:`1\times 10^5`.

Although a few other linear solvers are available for use with the full tangent preconditioner in the CG solver, it is recommended that FETI be used. FETI is actively maintained and tested by the Sierra/SM development team. FETI has been demonstrated as a robust parallel solver has been used successfully on a wide range of production analyses. The command block for the FETI equation solver is as follows:

.. code-block:: sierrainput

   BEGIN FETI EQUATION SOLVER <string>name
     #
     # convergence commands
     MAXIMUM ITERATIONS = <integer>max_iter(500)
     RESIDUAL NORM TOLERANCE = <real>residual_tol(1.0e-3)
     #
     # diagnostic commands, off by default.
     # "solver" turns on print statements from FETI
     # "matrix" prints the element matrices to the log file
     # "stats" prints time and iteration statistics
     # "export_matrices" exports the matrix to a MATLAB file
     # (in serial)
     PARAM-STRING "debugMask" VALUE <string>"solver"|"matrix"
     #
     # Hinge detection (bad decomposition topologies)
     # Use stk_balance to avoid bad decompositions
     PARAM-STRING "detect_bad_topology" VALUE <string>"true"
     #
     # Export cubit journal files with bad topologies for viz
     PARAM-STRING "debug_bad_topology" VALUE <string>"true"
     #
     # memory usage commands
     PARAM-STRING "precision" VALUE <string>"single"|"double"
       ("double")
     #
     # Lumped uses less memory, Dirichlet improves convergence
     PRECONDITIONING METHOD = LUMPED|DIRICHLET(DIRICHLET)
     MAXIMUM ORTHOGONALIZATION = <integer>max_orthog(1000)
     #
     # solver commands
     LOCAL SOLVER  = SKYLINE|SPARSE|ITERATIVE(SPARSE)
     COARSE SOLVER = SKYLINE|SPARSE|ITERATIVE(SPARSE)
     #
     # factorization tolerance for local domain matrix
     PARAM-REAL "local_rbm_tol" value <real>(1e-12)
     #
     # factorization tolerance for global coarse matrix
     PARAM-REAL "global_rbm_tol" value <real>(1e-9)
     #
     # linear residual stagnation tolerance
     PARAM-REAL "stagnation_tol" value <real>(1e-6)
   
   END [FETI EQUATION SOLVER <string>name] 

The command lines used to control FETI all reside in the ``FETI EQUATION SOLVER`` command block, where ``name`` identifies the particular command block. This command block, as with all equation solver command blocks, is  placed in the SIERRA scope and referenced by ``name`` when it is used. Although many command lines are available to control the behavior of FETI, the default settings generally work well for the vast majority of problems. Thus, it is recommended that all default settings be used unless special behavior is desired because of the unique features of a specific model. The command lines in the ``FETI EQUATION SOLVER`` command block are described in :numref:`implicit-feticonv` through :numref:`implicit-fetisolv`.

.. _implicit-feticonv:

Convergence Commands
====================

.. code-block:: sierrainput

     MAXIMUM ITERATIONS = <integer>max_iter(500)
     RESIDUAL NORM TOLERANCE = <real>residual_tol(1.0e-3)

These command lines provide controls on the convergence of the FETI iterative solver and belong in the ``FETI EQUATION SOLVER`` command block.

The ``MAXIMUM ITERATIONS`` command line sets the maximum number of iterations allowed per FETI solve. The default value of the parameter ``max_iter`` is 500. A FETI solve occurs once per CG iteration when  used with the full tangent preconditioner. 

The ``RESIDUAL NORM TOLERANCE`` command line sets the convergence criterion for the FETI solver. The default value of the parameter ``residual_tol`` is 1.0e-3. The relative residual norm is compared against the linear residual :math:`||Ax-b||` divided by the norm of current residual, :math:`||b||` where :math:`b` is the residual force, :math:`A` is the tangent stiffness matrix, and :math:`x` is the linear solution vector. If convergence is not reached before the iteration count exceeds ``max_iter``, FETI will return the current approximate gradient direction to the CG solver and continue iterating. The code will not exit with an error. The default settings for both of these command lines are reasonable for most models and typically should not be modified.

.. _implicit-fetimemory:

Memory Usage Commands
=====================

.. code-block:: sierrainput

   PARAM-STRING "precision" VALUE <string>"single"|"double"
     ("double")
   PRECONDITIONING METHOD = LUMPED|DIRICHLET(DIRICHLET)
   MAXIMUM ORTHOGONALIZATION = <integer>max_orthog(1000)

The command lines listed above can be placed in the ``FETI EQUATION SOLVER`` command block to enable optional memory-saving features of the FETI solver. These features will adversely impact the solver effectiveness to some degree, but they can be useful if the memory requirements of a model exceed the capacity of the machine on which the model is run. Before using these features, it is important to consider that on a distributed memory cluster, spreading the model out over more processors can reduce the memory requirements on each processor. For this reason, it is often better to use more processors rather than use the options described here.

FETI has the option of using either single or double precision for storage of internal variables. The default behavior is to use double precision, and this is typically recommended. To select single precision, the user would specify the command line as follows: ``PARAM-STRING "precision" VALUE "single"``. Using single-precision variables within FETI can reduce the memory requirements by roughly a factor of two. Use of single precision may, however, degrade the performance of the solver, requiring more iterations within FETI or more CG iterations. Using single precision in FETI does not affect the Sierra/SM data structures, which are always double precision, and therefore does not adversely affect solution ultimate accuracy.

The ``PRECONDITIONING METHOD`` command line selects the preconditioning method that is used by FETI. The default option, ``DIRICHLET``, typically results in the best convergence rate. The ``LUMPED`` option uses less memory, but it usually results in more linear iterations. This option should only be used if there are limitations on memory usage.

Like the CG solver, the FETI equation solver stores a set of search directions to ensure that the search direction used in each iteration is orthogonal to previous search directions. The number of search directions stored is controlled with the ``MAXIMUM ORTHOGONALIZATION`` command line. The default value of 1000 for ``max_orthog`` provides optimal convergence for linear solves that take less than 1000 iterations. Setting ``max_orthog`` to a lower number can decrease memory usage however, as with the other options discussed above, may require more iterations for convergence.

.. _implicit-fetisolv:

Solver Commands
===============

.. code-block:: sierrainput

   LOCAL SOLVER  = SKYLINE|SPARSE|ITERATIVE(SPARSE)
   COARSE SOLVER = SKYLINE|SPARSE|ITERATIVE(SPARSE)
   PARAM-REAL "local_rbm_tol" value <real>(1e-12)
   PARAM-REAL "global_rbm_tol" value <real>(1e-9)

These command lines control the type of solver used by FETI for solving the linear system that arises from the coarse grid and for the local solution mesh linear system. The ``LOCAL SOLVER``  command line is used to select the solver for the local subdomains. Similarly, the solver for the coarse grid can be selected with the ``COARSE SOLVER`` command lines. Both of these command lines allow the same three options: ``SPARSE``, ``SKYLINE``, and ``ITERATIVE``, where ``SPARSE`` is the typical default. The coarse solver default is set based on the number of processors being used in the problem. For processor counts less than 3, the ``SKYLINE`` solver is the default coarse grid solver. For processor counts greater than 3 and less than 2000, the ``SPARSE`` solver is the default coarse grid solver. For processor counts greater than 2000, the ``ITERATIVE`` coarse grid solver is the default.

The FETI algorithm uses these direct solvers to factorize the local matrix and coarse grid matrices before iterating on the solution. These factorization algorithms use tolerances to detect singularities in the matrix. The default values for ``local_rbm_tol`` and ``global_rbm_tol`` are recommended in most situations.

- The ``SPARSE`` option uses a sparse matrix storage direct solver. The sparse matrix is factored into an :math:`A=LDL^T` decomposition. FETI takes advantage of equation orderings to reduce matrix fill-in. The default equation ordering is done by calling the METIS sparse matrix ordering algorithm. This solver is recommended for both speed and memory efficiency.

- The ``SKYLINE`` option uses a skyline (profile) matrix storage direct solver. The skyline matrix is factored into an :math:`A=LDL^T` decomposition. This method is robust, detects rigid-body modes effectively, and includes the reverse Cuthill-McKee (RCM) and Sloan equation orderings. This solver uses more memory than does the sparse solver.

- The ``ITERATIVE`` option implements a multiple domain FETI algorithm for the local solver or the coarse solver. The number of domains for the local solver is either computed based on internal heuristics or input by the user. The number of domains for the coarse solver is defaulted to 2 which means that the iterative coarse solver will run on 2 processors. This option is recommended  in special circumstances where memory becomes an issue with the sparse direct solver or the problem is being run on greater than 2000 processors.

CG with Full Tangent Preconditioner and FETI Input Example
==========================================================

The following example defines a FETI solver for use in a CG preconditioner. The linear solver ``my_feti`` references a FETI solver with a non-default parameter set. This example  sets the preconditioning method to the lumped method to reduce memory usage.

.. code-block:: sierrainput

   ...
       Begin solver
         Begin cg
           target relative residual = 1.0e-09
           Maximum Iterations       = 100
           begin full tangent preconditioner
             linear solver = my_feti
           end
         end
       end
     end adagio region adagio
   end adagio procedure Agio_Procedure
   
   begin feti equation solver my_feti
     preconditioning method = lumped
   end

.. _implicit-fetiprint:

Printing Stiffness Matrix
=========================

The following example shows how to print the element stiffness matrices of your model. This option will produce a large amount of output, so it is not advised for large meshes or runs with a high numbers of time steps.

.. code-block:: sierrainput

   BEGIN FETI EQUATION SOLVER feti
     #
     # diagnostic commands, off by default.
     # "matrix" prints the element matrices to the log file
     PARAM-STRING "debugMask" VALUE "matrix"
   
     # This line sets the number of decimal precision 
     # for the stiffness matrix output:
     param-int "print_precision" value 15
   END

When using this command, you will need to run your problem in serial (1 processor) with a full tangent preconditioner. Remember to specify this ``FETI`` solver using the ``LINEAR SOLVER`` option in the ``FULL TANGENT PRECONDITIONER`` command block. The individual element matrices will be printed to the log file in a format that is readable by Matlab.

.. raw::
  html

  <hr>

.. footbibliography::
