INTRO(3LAS)

NAME

intro -- introduction to LASPack (Package for Linear Algebra with Sparse Matrices)

DESCRIPTION

LASPack is a package for solving large sparse systems of linear equations like those which arise from discretization of partial differential equations.

Main features:

• The primary aim of LASPack is the implementation of efficient iterative methods for the solution of systems of linear equations. All routines and data structures are optimized for effective usage of resources especially with regard to large sparse matrices. The package can be accessed from an application through a straightforward interface defined in the form of procedure calls.
• Beside the obligatory Jacobi, successive over-relaxation, Chebyshev, and conjugate gradient solvers, LASPack contains selected state-of-the-art algorithms (cf. Barrett et al. [1], McCormick[5]) which are commonly used for large sparse systems:
  • CG-like methods for non-symmetric systems: CGN, GMRES, BiCG, QMR, CGS, and BiCGStab,
  • multilevel methods such as multigrid and conjugate gradient method preconditioned by multigrid and BPX preconditioners.
  All above solvers are applicable not only to the positive definite or non-symmetric matrices, but are also adopted for singular systems (e.g. arising from discretization of Neumann boundary value problems).
• The implementation is based on an object-oriented approach (although C as programming language have been used). Vectors and matrices are defined as new data types in connection with the corresponding supporting routines. The basic operations are implemented so that they allow the programming of linear algebra algorithms in a natural way.
• LASPack is extensible in a simple manner. An access to the internal representation of vectors and matrices is not necessary and is, as required of the object-oriented programming, avoided. This allows an improvement of algorithms or a modification of data structures with no adjustment of application programs using the package.
• LASPack is written in ANSI C and is thus largely portable.

The structure of LASPack is depicted in the following figure:

The library consists of several modules at which some of them may be grouped together forming larger units.

The modules VECTOR, MATRIX, and QMATRIX as well as OPERATS, and FACTOR are the main component of the library. The basic objects of linear algebra, vectors and matrices, are here implemented as data types. Their definition consists not only of data structures, but also of the corresponding management routines, e.g. for allocation and release of variables of the above types, or storage and querying of vector components and matrix elements. For matrix storage, the compressed row format and the compressed column format can be used, respectively. Two different types of matrices are implemented in LASPack . The type Matrix is a data type for general rectangular sparse matrices. Variables of such kind are in LASPack intended especially for description of restriction and prolongation operators within multigrid algorithms. The type QMatrix is designed for quadratic sparse matrices of systems of linear equations. With regard to type Matrix, some additional properties are available for this data type such as symmetry, invertability etc. These are also taken into account for storage and in numerical algorithms.

The basic operations of linear algebra are implemented in the module OPERATS. It contains procedures for e.g. assignment and addition of vectors, multiplication of vectors by scalars and matrices, or generation of transposed, diagonal, and triangular matrices. For complex algebraic expressions, the usage of temporary variables allows to chain these routines up so that numerical algorithms could be transcribed directly in LASPack .

The module FACTOR consists of procedures for incomplete factorization of quadratic matrices.

In top-level modules, several iterative solvers are implemented: the classical iterative, semi-iterative, and conjugate gradient methods, selected procedures for non-symmetric systems (module ITERSOLV), and multilevel solvers (module MLSOLV).

In addition, the most common types of preconditioners are available in the module PRECOND. The module EIGENVAL contains procedures for estimation of extremal eigenvalues which are required e.g. by the Chebyshev method.

Whereas the above modules define basic objects of linear algebra and the corresponding operations concerning them, the remaining modules RTC and ERRHANDL are of global kind.

Convergence of iterative solution is controlled by routines of the module RTC. In order to terminate the solution process, a residual criterion is applied.

Routines in the module ERRHANDL support the error handling. They supervise some exception states which may happen during generation or solving of systems of equations and allow their treatment in the application code.

LASPack consists from a global (object-oriented) point of view of definition of the objects Vector, Matrix, and QMatrix and of a set of more or less complicated operations on them. For the extensibility of the library, the strict hidding of internal representation of these objects as well as the communication between the hierarchically build modules by simple structured interfaces in form of procedure calls are important. This allows to extend or exchange LASPack modules in a simple manner, respectively.

LASPack is written in ANSI C and thus portable to most computer platforms. It was successfully tested on Sun Sparc5 (SunOS 4.1.3, gcc 2.4.5), HP 9000/735 (HP-UX 9.05), IBM RS/6000 550 (AIX 3.2.5), DEC 3000/800 M (OSF/1 3.0), SGI IRIS Indigo (IRIX 5.3), and PC 486 (MS-DOS 6.2, BC 2.0/MSC 6.0; Linux 1.1.54, gcc 2.5.8/libc 4.5.26).

REFERENCES

[1] R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, Ch. Romine, H. van der Vorst: Templates for the Solution of Linear Systems: Building Blocks for Iterative Solvers, SIAM, Philadelphia, 1994. (HTML version is here).

[2] G. Golub, C. van Loan: Matrix Computations, second edition, The Johns Hopkins University Press, Baltimore, 1989.

[3] W. Hackbusch: Iterative Solution of Large Sparse Systems of Equations, Springer-Verlag, Berlin, 1994.

[4] W. Hackbusch: Multi-Grid Methods and Applications, Springer-Verlag, Berlin, 1985.

[5] S. F. McCormick: Multigrid Methods, SIAM, Philadelphia, 1987.

AUTHOR

The library LASPack was developed by Tomas Skalicky.

COPYRIGHT

Copyright (C) 1992-1995 Tomas Skalicky. All rights reserved. ANY USE OF THIS CODE CONSTITUTES ACCEPTANCE
OF THE TERMS OF THE COPYRIGHT NOTICE

See the file laspack/copyrght.h for details.

FILES

• installed:

  /usr/local/include/laspack/*.h ... LASPack header files
  /usr/local/lib/liblaspack.a ... LASPack library

• in the distribution:

  laspack/*.h ... LASPack header files
  laspack/*.c ... LASPack sources
  laspack/examples/* ... some examples and test programs
  laspack/doc/*.ps ... reference manual incl. these manual pages

LIST OF MANUAL PAGES

    eigenval(3LAS)  estimation of extremal eigenvalues
    errhandl(3LAS)  error handling routines
    factor(3LAS)    incomplete factorization of quadratic matrices
    itersolv(3LAS)  classical iterative, semi-iterative, CG, and
                    CG-like solvers
    matrix(3LAS)    type Matrix for general rectangular sparse 
                    matrices
    mlsolv(3LAS)    multilevel solvers
    operats(3LAS)   basic operations of linear algebra
    precond(3LAS)   pre-defined preconditioners
    qmatrix(3LAS)   type QMatrix for quadratic sparse matrices
    rtc(3LAS)       residual termination control of iterative 
                    solvers
    vector(3LAS)    type Vector