Home

Numerical linear algebra is a fundamental component of scientific and engineering computing. Though a wide range of solutions are obtained using numerical linear algebra, the most common are for systems of linear equations, least squares, eigenvalues, and singular value decomposition. A Fortran 77 library of standard routines for these solutions, Linear Algebra PACKage, was initially released in 1992 and has been in continual development since. The majority of the routines in the LAPACK library are expressed in terms of the Basic Linear Algebra Subroutines. An effort to update the BLAS library was started in November of 1995 with the first meeting of the BLAS Technical Forum. This effort culminated with the release of the Basic Linear Agebra Subprograms Technical (BLAST) Forum Standard. The objective of the linear algebra in Common Lisp is to generate linear algebra routines in native ANSI Common Lisp leveraging the knowledge captured in the BLAST Forum Standard.

Motivation

A numerical linear algebra library with a standard application programming interface (API) facilitates development of numerical software through code reuse and portability. Furthermore, a standard API enables the development of high performance libraries customized for a specific platform. The adoption by the scientific and engineering community of the LAPACK and BLAS libraries demonstrated the value of these attributes. A native Common Lisp numerical linear algebra library would facilitate the development of scientific and engineering software in Common Lisp.

Lisp has the reputation of lacking sufficient floating point performance for use in scientific and engineering applications. There is no technical basis for this reputation. To the contrary, examples of Lisp implementations geared towards numerical computations are provided in Steele and Gabriel. An early critique of Common Lisp does note several issues that impact numeric performance. Some of these issues have been addressed by compilers such as SBCL and by advances in hardware. While the objective of this project is development of a native CL linear algebra library, the library API could be used as an abstraction layer for an FFI to an external high performance numerical library. Then, code written to the interface would use the best available implementation.

Design and Implementation

The first release of this library is focused on correctness, completeness and interface design. Performance is not a consideration in the initial design. Performance will be addressed in future releases. Mixed argument operations are not explicitly handled, the standard behavior of Common Lisp is used.

The correctness is established by implementing algorithms that are documented to be correct. The algoritms are implemented from the BLAS, BLAST, LAPACK, DEMMEL, LAPACK working notes and other references. The correctness of the implementation is then verified through the unit testing. Performance issues will be addressed when the interface is frozen and the unit testing is in place to verify the correctness of the algorithms.

Open Topics

• Banded matrices
• Sparse matrices
• Tensor objects and routines
• Type specific routines
• Exception handling(underflow, overflow, etc.)
• IEEE 754 hardware exception handling
• SMP capabilities
• Distributed capabilities, possibly MPI.

Performance improvements

• uni-processor performance.
• Vectorization.
• SMP performance.
• Distributed performance, possibly MPI.
• Native code generation.

A tensor object needs to be designed and integrated into the library. This may require a modification of the interface.

Minimal error checking is performed in the current implementation. When the interface is established, an error condition system will be implemented that improves the error reporting for the user.

Exception handling is generally not implemented. The default exception handling should rely on Common Lisp exception facilities. The ability to utilize IEEE~754 hardware exception handling should be provided as well.