For the simulation of many numerical problems the solution of large and sparse linear systems is required. For these problems the linear solver package LINSOL has been designed. Iterative techniques based on generalized conjugate gradient methods and beyond are implemented. Different polyalgorithms that select appropriate solvers from the whole variety of methods and direct solvers - the (Incomplete) Gauss algorithm for unsymmetric matrices and the (Incomplete) Cholesky algorithm for symmetric matrices - are available.

Highlights of LINSOL are

• robustness
  • by many iterative methods for different classes of matrices
  • by an adaptive method selection
  • by (incomplete) LU and L^TL preconditioning respectively
• portability
  • Fortran90
  • P_MPI - a small, common subset of the well-known message passing interfaces
• flexibility
  • by the implementation of a Unix/Linux interface
  • by the implementation of a Fortran90 interface
  • by the support of  8 storage patterns
• efficient implementation
  • for workstations by an cache optimization
  • for vector computers
  • for parallel computers

Read chapter "In a nutshell" to get a brief 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.

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.

Installation of LINSOL

Please read “How to install LINSOL”, before starting the installation process.

Please read “User’s Overview of LINSOL”, before the first use of LINSOL.

User Interfaces of LINSOL

Please read “How to use the Unix/Linux interface of LINSOL” for the useage of LINSOL with a given matrix (and right hand side) without implementation effort.

The matrix can be read in two formats - the well-known Harwell-Boeing (H/B) file format and the LINSOL file format that is optimally suited to the available storage patterns of the program package LINSOL. Please read “The LINSOL file format” to get to know the LINSOL file format.

The format of the file storing the right hand sides (rhs) and the initial guesses and the format of the file storing the solutions is described in “The file format of the rhs, initial guesses and the solutions”.

Please read “The matrix structure of LINSOL” and “How to use LINSOL in user applications” to embed the program package LINSOL into your application.

Papers related to LINSOL from members of the former research group for supercomputers

The theoretical background of the program package LINSOL is addressed in

Rüdiger Weiss, Hartmut Häfner and Willi Schönauer
LINSOL (LINear SOLver) - Description and User's Guide for the Parallelized Version (DRAFT Version 0.96)
Internal Report 61-95 1995 (524 KiloBytes (KB))

The basic concepts of the program package LINSOL are addressed in

H. Häfner, W. Schönauer, R. Weiss
The Program Package LINSOL - Basic Concepts and Realization (62 KB)
Applied Numerical Mathematics, Vol. 30, No. 2-3, 1999, pp. 213-224.

H. Häfner, W. Schönauer, R. Weiss
The portable and parallel linear solver package LINSOL (97 KB)
Proceedings of the 4th European SGI/Cray MPP Workshop, IPP R/46, Oct. 1998, Max-Planck-Institut für Plasmaphysik, Garching bei München, Germany, pp. 242-251.

W. Schönauer, H. Häfner, R. Weiss
LINSOL, a Parallel Iterative Linear Solver Package of Generalized CG-type for Sparse Matrices (131 KB)
Proceedings of the 8th SIAM Conference on Parallel Processing for Scientific Computing, SIAM, Philadelphia 1997, CD-ROM (ISBN 0-89817-395-1), 8 pages.

H. Häfner, W. Schönauer
Portable Parallelization of the Iterative Linear Solver Package LINSOL (58 KB)
in E.H. D’Hollander, G.R. Joubert, F.J. Peters, D. Trystram (Eds.), Parallel Computing: State-of-the-Art and Perspectives, Elsevier, Amsterdam 1996, pp. 625-628.

Different bandwidth optimization algorithms that are integrated in LINSOL are addressed in

D. Zundel
Implementation and comparison of three bandwidth optimizing algorithms on a distributed memory parallel computer (441 KB)
Diploma thesis, Internal report 75-01.

D. Zundel and W. Schönauer
A Fast "Parallelized" Single Pass Bandwidth Optimizer for Sparse matrices (208 KB)
To appear in: Proceedings of the International Conference on Numerical Algorithms, Marrakesh, Morocco, October 1-5, 2001.

Theoretical and practical aspects of the embedding of the (I)LU preconditioner into the program package LINSOL are addressed in

H. Häfner, W. Schönauer
Embedding of the (I)LU preconditioner into the program package LINSOL (32 KB)
The online paper is a revised version compared to the published version.
Proc. 18th PARS Workshop, Munich, PARS Mitteilungen Nr. 18, Nov. 2001, Gesellschaft für Informatik, Bonn, pp. 77-86.

H. Häfner, W. Schönauer, R. Weiss
The integration of different variants od the (I)LU algorithm in the LINSOL program package (137 KB)
Applied Numerical Mathematics 41 (2002), pp. 39-59.

W. Schönauer, H. Häfner, R. Weiss
Numerical experiments to optimize the (I)LU preconditioning in the iterative linear solver package LINSOL (103 KB)
Applied Numerical Mathematics 41 (2002), pp. 23-37.

Hartmut Häfner, Willi Schönauer, Rüdiger Weiss
Parallelization and Integration of the LU and ILU Algorithm in the LINSOL Program Package (60 KB)
in V. Malyshkin (Ed.), PaCT, Springer Lecture Notes in Computer Science 1662, Berlin 1999, pp. 417-427.

Practical papers on iterative linear solvers and their parallelization are addressed in

R. Weiss, C. Roll, H. Häfner, L. Gross, M. Schmauder, W. Schönauer
Parallelisierung von ODIN-Software für iterative Gleichungslöser
in A. Schreiner, E. Schnepf (Herausgeber), Drittes ODIN-Symposium, Rechenzentrum Universität Karlsruhe, 1994, Seite 117-128.

H. Häfner, W. Schönauer
Kommunikation auf verschiedenen Parallelrechnern, Auswirkung auf die Programmierung (82 KB)
in A. Schreiner, E. Schnepf (Herausgeber), Drittes ODIN-Symposium, Rechenzentrum Universität Karlsruhe, 1994, Seite 195-206.

Theoretical papers on iterative linear solvers are addressed in

C. Koschinski
Properties of Approximate Inverses and Adaptive Control Concepts for Preconditioning (897 KB)
Doctoral thesis, Internal Report 74-99, 1999.

R. Weiss
How to Improve Iterative Solvers: Parallelization and Preconditioning
1999.

R. Weiss, I. Podgajezkaya, H. Häfner, W. Schönauer
Iterative Sovers for Linear Equations, from the Past to the Future
1999.

R. Weiss
Where Have We Been and Where Do We Go to
1999.

R. Weiss
Duality between Solvers for Ordinary Equations and Linear Systems
1998.

R. Weiss, H. Häfner, W. Schönauer
Overview on Solves for Linear Equations
in RIMS Symposium, Kyoto University, Japan, Vol. 98, No. 115, 1998, pp. 213 - 224.

W. Schönauer
Experiments with Search Directions for a Generalized CG Method
Proceedings 15th IMACS World Congress 1997 on Scientific Computation, Modelling and Applied Mathematics, IMACS, New Brunswick 1997, Vol. II, pp. 515-520 (all volumes in one CD-ROM available). Extended version in Applied Numerical Mathematics, Vol. 30, No. 2-3, 1999, pp. 241-256.

R. Weiss
Transformations of and Relations between Iterative Linear Solvers (24 KB)
Internal Report, 1995.

T. Wälde
Genetisch evolutionäre Algorithmen zur Lösung linearer Gleichungssysteme (in German, English abstract)
Diploma thesis, Internal Report 64-96, 1996.

M. Rozloznik, R. Weiss
On the Stable Implementation of the Generalized Minimal Error Method
Internal Report 56-95, 1995.

M. Zimmermann
Projektionsmethoden zur Präkonditionierung von verallgemeinerten CG-Verfahren (in German, English abstract)
Diploma thesis, Internal Report 55-95, 1995.

R. Weiss
A Theoretical Overview of Krylov Subspace Methods (154 KB)
Applied Numerical Mathematics, 1995.

B. Wagner
Kurze Rekursionen bei präkonditionierten CKS-Verfahren (249 KB, in German)
Internal Report 54-95, 1995.

R. Weiss
Relations between Smoothing and QMR (59 KB)
Internal Report 53-94, 1994.

R. Weiss
Orthogonalization Methods (156 KB)
Internal Report 52-94, 1994.

R. Weiss
Minimization Properties and Short Recurrences for Krylov Subspace Methods (75 KB)
Electronic Transactions on Numerical Analysis, 1994.

W. Schönauer, R. Weiss
An engineering approach to generalized conjugate gradient methods and beyond (291 KB)
in W.F. Ames (Ed.), Proceedings 14th IMACS World Congress on Computation and Applied Mathematics, IMACS, New Brunswick 1994, Vol. 3, pp. 1462-1465. Extended version in Applied Numerical Mathematics 19 (1995), pp. 175-206.

R. Weiss, W. Schönauer
Black box solvers for partial differential equations
in H. Küsters, E. Stein, W. Werner (Eds.), Proc. of the Joint International Conference on Mathematical Methods and Supercomputing in Nuclear Applications, M & C + SNA 1993, Kernforschungszentrum Karlsruhe, 1993, Vol. 2, pp. 29-40.

R. Weiss, W. Schönauer
Preconditioned Generalized Conjugate Gradient Methods: What Do We Have and What Do We Need?
in R. Vichnevetsky, D. Knight, G. Richter (Eds.), Advances in Computer Methods for Partial Differential Equations -VII, IMACS, New Brunswick 1992, pp. 806-812.

R. Weiss, W. Schönauer
Accelerating Generalized Conjugate Gradient Methods by Smoothing
in R. Beauwens and P. de Groen (Eds.), Iterative Methods in Linear Algebra, North-Holland, Amsterdam 1992, pp. 283-292.

W. Schönauer, R. Weiss, P. Sternecker
Polyalgorithms with automatic method selection for the iterative solution of linear equations and eigenproblems
in P.W. Gaffney, E.N. Houstis (Eds.), Programming Environments for High-Level Scientific Problem Solving, North-Holland, Amsterdam 1992, pp. 57-67.

P. Sternecker, L. Gross, W. Schönauer
A polyalgorithm for the solution of large symmetric general eigenproblems
in R. Beauwens and P. de Groen (Eds.), Iterative Methods in Linear Algebra, North-Holland, Amsterdam 1992, pp. 423-432.

R. Weiss, W. Schönauer
Solution of partial differential equations by means of data reduction (DARE)
in Multigrid Methods Special Topics and Applications II, edited by W. Hackbusch, U. Trottenberg, GMD-Studien Nr. 189, GMD, St. Augustin, 1991, pp. 361-372.

R. Weiss, W. Schönauer
Solvers for partial differential equations on vector computers
in J. Halin, Treffen des ASIM-Arbeitskreises “Simulationssoftware und -hardware”, Zürich, ASIM-Mitteilungen Heft Nr. 19, pp. 162-169.

R. Weiss, W. Schönauer
Data reduction (DARE) preconditioning for generalized conjugate gradient methods
in O. Axelsson, L.Yu. Kolotilina (Eds.), Preconditioned Conjugate Gradient Methods, Lecture Notes in Mathematics 1457, Springer, Berlin, 1990,                pp. 137-153.

R. Weiss, H. Häfner, W. Schönauer
Tuning the matrix-vector-multiplication in diagonal form
in D.J. Evans et al. (Eds.), Parallel Computing ‘89, Amsterdam 1990, pp. 93-98. W. Schönauer, R. Weiss, M. Schlichte
The basic ideas of the data reduction (DARE) method for the solution of large linear systems on vector computers
ZAMM 69 (1989), pp. T184-T185.

W. Schönauer, M. Schlichte, R. Weiss
Numerical experiments with data reduction (DARE) methods for the solution of large linear systems on vector computers
Proceedings 12th IMACS World Congress on Scientific Computing, edited by R. Vichnevetsky, P. Borne, J. Vignes, IMACS 1988, Vol. 4, pp. 227-229, and in W.F. Ames et al. (Eds.), Numerical and Applied Mathematics, J.C. Baltzer, Basel 1989, pp. 647-651.

W. Schönauer, R. Weiss
Efficient vectorizable PDE solvers
Journal of Computational and Applied Mathematics 27 (1989) (invited paper),  pp. 279-297. W. Schönauer, M. Schlichte, R. Weiss
Wrong ways and promising ways towards robust and efficient iterative linear solvers
in Advances in Computer Methods for Partial Differential Equations - VI, edited by R. Vichnevetsky and R.S. Stepleman, IMACS 1987, pp. 7-14.

W. Schönauer, H. Müller, E. Schnepf
Pseudo-residual type methods for the iterative solution of large linear systems on vector computers
Parallel Computing 85, edited by M. Feilmeier, J. Joubert, U. Schendel, North-Holland 1986, pp. 193-198.

H. Müller, W. Schönauer, E. Schnepf
Vergleich verschiedener Lösungsverfahren für lineare Gleichungen mit Diagonalenspeicherung auf der CYBER 205
in Mitteilungen Nr. 3, Gesellschaft für Informatik, Parallelalgorithmen und -rechnerstrukturen (PARS), Univ. Erlangen, 1985, pp. 65-74. H. Müller, W. Schönauer, E. Schnepf
Design considerations for the linear solver LINSOL on the CYBER 205
in Supercomputer Applications, edited by A.H.L. Emmen, North-Holland 1985, pp. 39-49.

W. Schönauer, H. Müller, E. Schnepf
Numerical tests with biconjugate gradient type methods
ZAMM 65 (1985), pp. T400-T402.

Willi Schönauer, Karlheinz Raith
A Polyalgorithm with Diagonal Storing for the Solution of Very Large Indefinite Linear Banded Systems on a Vector Computer
in Parallel and Large-Scale Computers: Performance, Architecture, Applications, edited by M. Ruschitzka, IMACS Transactions on Scientific Computing, Vol. II, North-Holland (1983), pp. 213-220.

A book on iterative linear solvers is addressed in

R. Weiss
Parameter-Free Iterative Linear Solvers

Two papers on nonlinear systems are addressed in

R. Weiss
On Solvers for Nonlinear Large Systems (98 KB)
Internal Report 69-97, 1997.

R. Weiss, I. Podgajezkaya
Overview on New Solvers for Nonlinear Systems (135 KB)
Applied Numerical Mathematics, 1999.

LINSOL is released under the terms of the GNU General Public License, which means several things. You can do just about anything you want to with it provided you do not incorporate it or any of its code into an application that is not released under the terms of the GNU General Public License. If you want to embed the software package LINSOL or parts of it into a software package to be distributed under other terms than the GNU General Public License, please contact me for an "User-Oriented Software License Agreement" of your own.

Download area

   Download file LINSOL1.0.tar.gz by clicking on the icon!!!

Important note

LINSOL has been installed on the following systems:
a. IBM SP with the compiler XL Fortran Version 7 (OS: AIX 4.3)
b. VPP 5000 with the compiler Fortran90/VP (OS: UXP/V)
c. Hitachi SR8000-F1 with the Fortran90 compiler (OS: HI-UX)
d. InstitutsCluster with Intel Compiler Suite in version 10.1 (Linux-Distribution: Suse SLES 10 SP 2)
e. Parallel system HP XC3000 with with Intel Compiler Suite in version 11.1 (Linux-Distribution: RedHat EL 5 Update 3)

This means that the installation process with the above mentioned compilers should run successfully. With other compilers (on other machines) I can’t guarantee that the installation process runs successfully. As far as my experience goes only minor errors should emerge so that it should be possible for an experienced user to install LINSOL on arbitrary machines. If you get into trouble with the installation process you can contact me per email, but I can’t guarantee a time slot for an answer of your request.

If you’ll find an implementation error within the program package LINSOL, please send me an error description per email. I’ll patch the implementation error as soon as possible and make the revised implementation available in the download area as patch. I can’t guarantee a time slot for the release of a patch. If you patch an implementation error for yourself, please send me even so an error description per email with the patched files as attachment.   

Contact

Hartmut Häfner