## Contents
1 Definition |

LU-decomposition of a rectangular *M*x*N* 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*.

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

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:

- It makes effective use of CPU cache without explicitly specifying its size. With each iteration matrices become smaller until they fits completely in cache. Such algorithms are called 'cache oblivious'.
- Recursive algorithm makes extensive use of ALGLIB BLAS - mostly of the Level 3 BLAS, the most optimized part of ALGLIB package. The matrices being multiplied are usually square (which is more suited for optimization than a low rank updates generated by LAPACK routines).

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.

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

*This article is intended for personal use only.*

ALGLIB Project offers you two editions of ALGLIB:

delivered for free

offers full set of numerical functionality

single-threaded, no low-level optimizations

non-commercial license (GPL or Personal/Academic)

flexible pricing

offers full set of numerical functionality

high performance (multithreading, SIMD, Intel MKL)

commercial license with support plan

Links to download sections for Free and Commercial editions can be found below:

ALGLIB for C++

C++ library.Delivered with sources.

Monolithic design.

Extreme portability.

ALGLIB for Delphi

Delphi wrapper around generic C core.Delivered as precompiled binary.

Compatible with FreePascal.

ALGLIB for C#

Generic C# library.Delivered with sources.

VB.NET and IronPython wrappers.

Extreme portability.

ALGLIB® - numerical analysis library, 1999-2017.

ALGLIB is a registered trademark of the ALGLIB Project.

Policies for this site: privacy policy, trademark policy.

ALGLIB is a registered trademark of the ALGLIB Project.

Policies for this site: privacy policy, trademark policy.