Main       Free Edition       Commercial Edition       FAQ       Forum       About Us

LU decomposition

Contents

    1 Definition
    2 Applications
    3 ALGLIB implementation
    4 Subroutines
    5 Manual entries

Definition

LU-decomposition of a rectangular MxN matrix A is a representation of A as a product of permutation matrix P, lower unitriangular matrix L and upper triangular matrix U: A = PLU.

Applications

Main applications of LU decomposition are solving linear equations systems, matrix inversion, and other tasks.

ALGLIB implementation

ALGLIB package implements recursive version of LU decomposition. Algorithm splits matrix into two approximately equal parts, decomposes first part, updates second one and builds its decomposition. Recursion is stopped when matrix size becomes small enough to fit in the smallest L1 cache of the modern CPUs. At this point, non-recursive version is called. This approach has the following advantages:

These features allows to achieve the maximum performance possible with your compiler/language. However, different compilers and different programming languages have different limitations. As for linear algebra algorithms, C++ version of ALGLIB is the most efficient implementation. Implementations in other languages have significantly lower performance.

Subroutines

LU decomposition is calculated by rmatrixlu and cmatrixlu subroutines. Permutatuion matrix P is stored in separate array, L and U replace A. For example, for 4x3 matrix we will get:

A11 A12 A13   =>    U11 U12 U13
A21 A22 A23   =>    L21 U22 U23
A31 A32 A33   =>    L31 L32 U33
A41 A42 A43   =>    L41 L42 L43

Manual entries

C++ trfac subpackage   
C# trfac subpackage   

This article is intended for personal use only.

Download ALGLIB

C#

C# source.

Downloads page

 

C++

C++ source.

Downloads page

 

C++, multiple precision arithmetic

C++ source. MPFR/GMP is used.

GMP source is available from gmplib.org. MPFR source is available from www.mpfr.org.

Downloads page

 

FreePascal

FreePascal version.

Downloads page

 

Delphi

Delphi version.

Downloads page

 

VB.NET

VB.NET version.

Downloads page

 

VBA

VBA version.

Downloads page

 

Python

Python version (CPython and IronPython are supported).

Downloads page

 

 

ALGLIB® - numerical analysis library, 1999-2014.
ALGLIB is a registered trademark of the ALGLIB Project.