• LINSOL

  • Für die Simulation vieler numerischer Probleme ist die Lösung großer Linearsysteme erforderlich. Für diese Probleme wurde LINSOL entwickelt.

  • Lizenztyp:

Overview

LINSOL solves huge symmetric and non-symmetric linear systems. LINSOL is adapted to the application of sparse matrices, but can be efficiently applied to full matrices, too. The basic solution algorithms are iterative generalized Conjugate Gradient (CG) methods; implemented methods are PRES20, BCG, Bi-CGSTAB, Bi-CGSTAB2, CGS, BICO, QMR, CGNE, CGNR (ATPRES), GMERR(5) and GMERR(20) for non-symmetric matrices and GMERRS and the classical CG-algorithm for symmetric matrices. The linear system can be normalized by eight different variants. The methods PRES20, BICO and Bi-CGSTAB2 can be precondtioned by the (Incomplete) Gauss algorithm and the classical CG-algorithm by the (Incomplete) Cholesky algorithm. 

 

Important features of the program package LINSOL are

  • robustness,
  • portability,
  • flexibility,
  • efficient implementation for workstations, vector computers and parallel computers.

 

 Robustness is reached by two features of the program package. The first one is an adaptive method selection called polyalgorithm. It chooses the optimal algorithm from many iterative methods and automatically switches to a better converging method, if the convergence deteriorates. The second one is the integration of the Gauss algorithm for non-symmetric matrices and the Cholesky algorithm for symmetric matrices into the according iterative algorithms; it can be used as convergence accelerator or as emergency exit, if the iterative methods converge slowly or all methods fail to converge. Both preconditioners are optimized for sparse matrices and can be controlled by three threshold parameters. According to the choice of the parameters all graduations between the complete decomposition leading to the solution in one iteration step and a weak approximation of the complete decomposition are possible.

Portability of the code on parallel computers is obtained by using the message passing paradigm; beyond that, LINSOL only uses a small, common subset of all known message passing interfaces; thus it is possible to exchange message passing libraries used by LINSOL by linking the program package with another available message passing library.

Flexibility is obtained first by the integration of two interfaces into LINSOL (see also first figure). Using the Unix/Linux interface the user only has to define parameters in a file controlling the program flow of LINSOL. The matrix can be stored in Harwell/Boeing- or LINSOL-format that is optimally adapted to the storage patterns implemented in LINSOL. The Fortran90 interface allows the integration of LINSOL into an application program.

Flexibility  with respect to the integration of the program package into an application is obtained by the support of many common storage patterns for sparse matrices. In all, 8 storage patterns are defined and can be used; the most important are: diagonal, row, column - always full and packed. It is allowed to compose the matrix of the linear system of any of the 8 storage patterns. For example it is possible to store the main diagonal of the matrix in the storage pattern main diagonal and to store all other elements in the storage pattern packed row so that a sparse nxn-matrix mostly consists of n+1 data types (1 data type of the storage pattern main diagonal and n data types of the storage pattern packed row).

Efficient implementation of LINSOL for workstations, vector computers and parallel machines:  efficient vectorization leads to a high optimization rate on vector computers; on cache-based systems as e.g. workstations a cache optimization can be switched on; the most important feature on parallel computers is the scalability with respect to the time requirements and to the memory requirements.
Further optimizations affect the use of the direct solver; thus a bandwidth optimizer minimizing the fill in of the sparse preconditioning matrix during the factorization can be switched on before the (incomplete) decomposition starts; if the matrix is not symmetric and consists of rows with only one nonzero entry, a pre-forward elimination can additionally be switched on shifting entries of the matrix by the use of known solution components to the right hand side and subsequently removing the shifted entries from the matrix.

Car body of Renault Scenic with metallic reflections computed by radiosity method with LINSOL as integrated solver of the linear systems.