Logo OS Reviews

Reviewing Freedom.



Linear Algebra on Speed

Hendrik Weimer


Print version

Slashdot me! Digg me! Stumble me! del.icio.us

In numerical computing, there are several tasks that are extremely common. Since many problems are linear or can be linearly approximated, linear algebra is an important tool. Well-known examples are solving sets of linear equations and finding eigenvalues and eigenvectors of a matrix. LAPACK is the most frequently used library for these purposes in the scientific community.

LAPACK is a Fortran library. There are interfaces for other languages like C or C++ available, but they are either incomplete or slower than the native Fortran version. However, the latter is not owed to the often heard and rarely founded claim that Fortran offers superior performance for numerical tasks, but merely because other interfaces have been generated by translators like f2c, which are known to not always generate the optimal code. Nevertheless, including LAPACK in a C program is slightly cumbersome but not difficult, and there is enough documentation available.

On the first look, there are a myriad of functions available in LAPACK. Many functions, however, perform the same task, like finding the solution to a set of linear equations. The difference lies in the precision of the computation (single or double), whether the input data is real or complex and the matrix describing the problem has special properties (e.g. a symmetric matrix).

Taking advantage of special properties of a problem is an extremely important aspect in numerical computing. By far, the greatest progress to speed up numerical computations in the last decades has not been made by faster computers (and you have probably heard of Moore's Law) but by finding faster algorithms. To give an example, solving a linear set of equations generally takes <a href="http://en.wikipedia.org/wiki/Big_O_notation">Oa>(n3) steps. However, if you know that the matrix is tridiagonal, the complexity can be reduced to O(n). Or, put less technically, 10 minutes versus 19 years for n = 1000. So it might be a good idea to think about algorithmic improvements before rushing to buy new hardware.

But even without such special purpose algorithms the performance of LAPACK is outstanding. Finding the eigenvectors of a 1500 × 1500 matrix takes about two minutes on a pretty decent machine, a problem which Octave cannot solve within days.

If you have access to a cluster or an other kind of distributed computing environment, you can use the ScaLAPACK variant, that provides the same interface but uses some algorithms specially optimized for parallel computing.

Altogether, LAPACK is a very powerful tool for numerical computations. The availability of optimized algorithms for problems with special properties often allows it to deliver where other packages fail.

License:Freely distributable
Distributions: [?]■ Debian stable■ Debian unstable
■ Fedora■ Mandriva
■ Suse■ Ubuntu


  • Extremely fast algorithms
  • Many optimized algorithms for special input data
  • Only Fortran interface available

Copyright 2006–2008 OS Reviews. This document is available under the terms of the GNU Free Documentation License. See the licensing terms for further details.