Solution of systems of linear equations
Solution of systems of linear equations
Keywords Internet,Linear systems, Software
Welcome to Internews of Engineering Computations. One of the most common problems of numerical methods is the solution of systems of equations. This can be done using a wide variety of well-known algorithms tailored to perform well for the problems at hand and the hardware available. For good performance of the solver it is important to correctly classify what kind of system of equations is to be solved. The type of equations depends on the problem and the numerical method used to solve the problem. For instance, the boundary element method produces different systems of equations than the finite element method when solving the same physical problem. The solution procedure can be direct or iterative, sequential or parallel. The system of equations can be linear, non-linear, positive definite, indefinite,symmetric, unsymmetric, real or complex; to name just a few. Another aspect is the programming language used to implement the solver: Fortran 77, Fortran 90,C, C++, Java, Ada, Basic, etc. Naturally, there are commercial libraries available to perform this task, most notably by NAG (http://www.nag.co.uk), by Visual Numerics (http://www.vni.com) and by Harwell (http://www.dci.clrc.ac.uk/ Activity.asp?HSL). In this edition of Internews, however, we concentrate on solvers for the solution of linear systems of equations that are freely available for research purposes in source code form on the Internet.
Webwatch looks at a site that casts some light onto the confusing variety of file formats/types.
Site #1: GAMS: Guide to Available Mathematical Software
The GAMS site can be visited at http://gams.nist.gov GAMS is "a cross-index and virtual repository of mathematical and statistical software components of use in computational science and engineering". The home page looks quite bare by modern Internet standards. However, since the home page is not cluttered it is straightforward to make out the important links and follow them. The mathematical software cross index can be searched by problem type, package name,module name or text in module abstracts. When following the problem type link,the visitor can search the archive, browse it or follow a decisions tree.
The decision tree is very useful in guiding people to the correct software packages when the problem type is known. For instance, following linear algebra, solution of systems of linear equations,real symmetric matrices, sparse (most systems of linear equations result in sparse matrices when using the finite element method) one arrives at the subclass D2b4 "solution of systems of linear equations, including matrix inverses, and LU and related factorizations (real symmetric sparse matrices)". At this stage GAMS displays a list of modules for this class of problems,including links to where to find more details about them and to download areas. Examples include Lapack (http://www.netlib.org/linalg/lapack) or Itpack (http://www.netlib.org/itpack). Some of the links point to commercial software. However, most of them guide the visitor to free software available for downloading. Here is where the real searching starts. It takes some time to work through all the referenced software packages and find the most appropriate module with respect to programming language,solution algorithm, interface, etc.
The link More Math and Statistics at NIST on the home page of GAMS takes the visitor to a list of services,organizations and projects. Among others, it links to transactions on mathematical software, The Matrix Market, JavaNumerics, Lecture Series,Mathematical and Computational Science Division, F90GL and Sparse BLAS.
Site #2: Mathematical Software
This site is maintained by A. Neumaier at http://solon.cma.univie.ac.at/~neum/software.htmlThe page contains links to a variety of software categories pointing, for instance, to direct linear solvers and iterative linear solvers.
The direct solver category includes links to general software (e.g. Serial Strassen Code, Sparse Matrix Computations, etc.), mesh partitioning software (Metis, Chaco, etc.) and sparse direct solvers (FSPAK, UMFPACK, SuperLU, PLAPACK and PSPASES; to name just a few).
The iterative solvers section points for instance to Aztec, P_Sparslib, GMRES, etc. It also links to Lecture Notes on Iterative Methods.
This page is simple in its design,but it contains a plentiful set of good links to software for the solution of linear, sparse systems of equations.
Site #3: GPSNew
NASA (http://www.nasa.gov) has developed the general-purpose solver (GPS; not to be confused with GPS the global positioning system) which can be found at http://transit.larc.nasa.gov/csb-www/GPS.htmlThe home page is a simple document in the style of a readme file with some links to figures, performance tables and contacts. GPS originated from the sparse equation solver VSS for structural analysis. GPS is a direct, sparse matrix solver for complex structural systems resulting in sparse or dense, positive definite or indefinite matrices. For large scale systems it has "out-of-core"facilities. The matrices are stored in NASA format (http://transit.larc.nasa.gov/csb-www/Matrix.html).User Feedback at the bottom of the home page links to success stories of the software.
The equation solver link on GPS's home page takes the visitor to the benchmarking page, which contains 21 "real"NASA benchmarks ranging from small problems (576 equations) to large problems(551,705 equations). The benchmark also contains links to a Java version of the VSS solver.
GPS seems to run on any platform;Cray, workstations and PCs. The PC version is called Winsolve (http://transit.larc.nasa.gov/csb-www/latest.html). This version is optimised for the Intel processor architecture and requires Windows 95 or NT. Versions optimised for other hardware platforms are also available.
The major drawback of GPS is its limited availability. Users have to complete a letter of request and a usage agreement. The letter of request limits the free distribution of the GPS software to the USA.
Site #4: Aztech_main
Sandia National Laboratories (http://www.cs.sandia.gov) are the developers of the Aztec solver (http://www.cs.sandia.gov/CRF/aztec1.html). Aztec is a "massively parallel iterative solver library for solving sparse linear systems". Their home page is well organised and colourful.
The first two links from the home page guide the visitor to release notes and download Aztec 2.0. When following the download link, the potential user is requested to fill in an online Aztec license agreement. Once completed, the user is e-mailed with a user-ID and a password, which makes it possible to log into the download area.
Aztec is not self-contained since it relies on domain decomposition software (for example CHACO at http://www.cs.sandia.gov/CRF/chac.html but most probably METIS at http://www-users.cs.umn.edu/~karypis/metis/main.html will work with it as well) and MPI for message passing.
Other links on the home page point to description, recent accomplishments, impact, related programs and publications. The publications link leads to the Aztech's user guide.
Webwatch
The age of computers brought not only a number of different hardware "interpretations" of computers(supercomputers, workstations, PCs, palmtops, etc.) but it also created an immense variety on the software side; operating systems as well as file formats. While variety can be spice in one's life, for people working with computers it can turn into a nightmare. The large number of different, incompatible file formats can be confusing and time-consuming when trying to work with such files. The Website Wotsit's Format: the programmer's file formats and data formats resources (http://www.wotsit.org) contains a comprehensive list of links to documents about file types and their formats. The site is very well organised. There is a list of links pointing to categories of file types ranging from graphics files over font files and game files to hardware formats and game programming. For instance, when following the link to text files/documents (http:// www.wotsit.org)the visitor can browse a list of document file types and follow links that contain detailed information about these formats. On the home page of this site there are also possibilities to join a chat forum, follow links for programming,register for e-mail updates, go to requests, submit more information and send feedback to Wotsit. Additionally, there is a search facility. This site is not only for users who want to quickly read up on a file type but also for programmers who wish to implement a new interface.
The Internet Editor of Engineering Computations
The Internet Editor of Engineering Computations, Johann Sienz, can be contacted via e-mail: J.Sienz@swansea.ac.uk or fax +44 1792 295676.
