DGETRF
Univ. of Tennessee, Univ. of California Berkeley and NAG Ltd..
May 2008
May 2008
Purpose
DGETRF computes an LU factorization of a general M-by-N matrix A
using partial pivoting with row interchanges.
The factorization has the form
A = P * L * U
where P is a permutation matrix, L is lower triangular with unit
diagonal elements (lower trapezoidal if m > n), and U is upper
triangular (upper trapezoidal if m < n).
This code implements an iterative version of Sivan Toledo's recursive
LU algorithm[1]. For square matrices, this iterative versions should
be within a factor of two of the optimum number of memory transfers.
The pattern is as follows, with the large blocks of U being updated
in one call to DTRSM, and the dotted lines denoting sections that
have had all pending permutations applied:
1 2 3 4 5 6 7 8
+-+-+---+-------+------
| |1| | |
|.+-+ 2 | |
| | | | |
|.|.+-+-+ 4 |
| | | |1| |
| | |.+-+ |
| | | | | |
|.|.|.|.+-+-+---+ 8
| | | | | |1| |
| | | | |.+-+ 2 |
| | | | | | | |
| | | | |.|.+-+-+
| | | | | | | |1|
| | | | | | |.+-+
| | | | | | | | |
|.|.|.|.|.|.|.|.+-----
| | | | | | | | |
The 1-2-1-4-1-2-1-8-... pattern is the position of the last 1 bit in
the binary expansion of the current column. Each Schur update is
applied as soon as the necessary portion of U is available.
[1] Toledo, S. 1997. Locality of Reference in LU Decomposition with
Partial Pivoting. SIAM J. Matrix Anal. Appl. 18, 4 (Oct. 1997),
1065-1081. http://dx.doi.org/10.1137/S0895479896297744
using partial pivoting with row interchanges.
The factorization has the form
A = P * L * U
where P is a permutation matrix, L is lower triangular with unit
diagonal elements (lower trapezoidal if m > n), and U is upper
triangular (upper trapezoidal if m < n).
This code implements an iterative version of Sivan Toledo's recursive
LU algorithm[1]. For square matrices, this iterative versions should
be within a factor of two of the optimum number of memory transfers.
The pattern is as follows, with the large blocks of U being updated
in one call to DTRSM, and the dotted lines denoting sections that
have had all pending permutations applied:
1 2 3 4 5 6 7 8
+-+-+---+-------+------
| |1| | |
|.+-+ 2 | |
| | | | |
|.|.+-+-+ 4 |
| | | |1| |
| | |.+-+ |
| | | | | |
|.|.|.|.+-+-+---+ 8
| | | | | |1| |
| | | | |.+-+ 2 |
| | | | | | | |
| | | | |.|.+-+-+
| | | | | | | |1|
| | | | | | |.+-+
| | | | | | | | |
|.|.|.|.|.|.|.|.+-----
| | | | | | | | |
The 1-2-1-4-1-2-1-8-... pattern is the position of the last 1 bit in
the binary expansion of the current column. Each Schur update is
applied as soon as the necessary portion of U is available.
[1] Toledo, S. 1997. Locality of Reference in LU Decomposition with
Partial Pivoting. SIAM J. Matrix Anal. Appl. 18, 4 (Oct. 1997),
1065-1081. http://dx.doi.org/10.1137/S0895479896297744
Arguments
| M |
(input) INTEGER
The number of rows of the matrix A. M >= 0.
|
| N |
(input) INTEGER
The number of columns of the matrix A. N >= 0.
|
| A |
(input/output) DOUBLE PRECISION array, dimension (LDA,N)
On entry, the M-by-N matrix to be factored.
On exit, the factors L and U from the factorization A = P*L*U; the unit diagonal elements of L are not stored. |
| LDA |
(input) INTEGER
The leading dimension of the array A. LDA >= max(1,M).
|
| IPIV |
(output) INTEGER array, dimension (min(M,N))
The pivot indices; for 1 <= i <= min(M,N), row i of the
matrix was interchanged with row IPIV(i). |
| INFO |
(output) INTEGER
= 0: successful exit
< 0: if INFO = -i, the i-th argument had an illegal value > 0: if INFO = i, U(i,i) is exactly zero. The factorization has been completed, but the factor U is exactly singular, and division by zero will occur if it is used to solve a system of equations. |