NAG Library Routine Document

F07BDF (DGBTRF)

+− Contents

1 Purpose

2 Specification

3 Description

4 References

5 Parameters

6 Error Indicators and Warnings

7 Accuracy

8 Further Comments

+− 9 Example

9.1 Program Text

9.2 Program Data

9.3 Program Results

1 Purpose

F07BDF (DGBTRF) computes the

L U

factorization of a real

m

n

band matrix.

2 Specification

SUBROUTINE F07BDF (

M, N, KL, KU, AB, LDAB, IPIV, INFO)

INTEGER	M, N, KL, KU, LDAB, IPIV(min(M,N)), INFO
REAL (KIND=nag_wp)	AB(LDAB,*)

The routine may be called by its LAPACK name dgbtrf.

3 Description

F07BDF (DGBTRF) forms the

L U

factorization of a real

m

n

band matrix

A

using partial pivoting, with row interchanges. Usually

m = n

, and then, if

A

has

k_{l}

nonzero subdiagonals and

k_{u}

nonzero superdiagonals, the factorization has the form

A = P L U

, where

P

is a permutation matrix,

L

is a lower triangular matrix with unit diagonal elements and at most

k_{l}

nonzero elements in each column, and

U

is an upper triangular band matrix with

k_{l} + k_{u}

superdiagonals.

Note that

L

is not a band matrix, but the nonzero elements of

L

can be stored in the same space as the subdiagonal elements of

A

U

is a band matrix but with

k_{l}

additional superdiagonals compared with

A

. These additional superdiagonals are created by the row interchanges.

4 References

Golub G H and Van Loan C F (1996) Matrix Computations (3rd Edition) Johns Hopkins University Press, Baltimore

5 Parameters

1: M – INTEGERInput

On entry:

m

, the number of rows of the matrix

A

Constraint:

M \geq 0

2: N – INTEGERInput

On entry:

n

, the number of columns of the matrix

A

Constraint:

N \geq 0

3: KL – INTEGERInput

On entry:

k_{l}

, the number of subdiagonals within the band of the matrix

A

Constraint:

KL \geq 0

4: KU – INTEGERInput

On entry:

k_{u}

, the number of superdiagonals within the band of the matrix

A

Constraint:

KU \geq 0

5: AB(LDAB, $*$ ) – REAL (KIND=nag_wp) arrayInput/Output

Note: the second dimension of the array AB must be at least

\max (1, N)

On entry: the

m

n

matrix

A

The matrix is stored in rows

k_{l} + 1

2 k_{l} + k_{u} + 1

; the first

k_{l}

rows need not be set, more precisely, the element

A_{i j}

must be stored in

AB (k_{l} + k_{u} + 1 + i - j, j) = A_{i j} for ​ \max (1, j - k_{u}) \leq i \leq \min (m, j + k_{l}) .

See Section 8 in F07BAF (DGBSV) for further details.

On exit: if

INFO \geq 0

, AB is overwritten by details of the factorization.

The upper triangular band matrix

U

, with

k_{l} + k_{u}

superdiagonals, is stored in rows

1

k_{l} + k_{u} + 1

of the array, and the multipliers used to form the matrix

L

are stored in rows

k_{l} + k_{u} + 2

2 k_{l} + k_{u} + 1

6: LDAB – INTEGERInput

On entry: the first dimension of the array AB as declared in the (sub)program from which F07BDF (DGBTRF) is called.

Constraint:

LDAB \geq 2 \times KL + KU + 1

7: IPIV( $\min (M, N)$ ) – INTEGER arrayOutput

On exit: the pivot indices that define the permutation matrix. At the

i

th step, if

IPIV (i) > i

then row

i

of the matrix

A

was interchanged with row

IPIV (i)

, for

i = 1, 2, \dots, \min (m, n)

IPIV (i) \leq i

indicates that, at the

i

th step, a row interchange was not required.

8: INFO – INTEGEROutput

On exit:

INFO = 0

unless the routine detects an error (see Section 6).

6 Error Indicators and Warnings

Errors or warnings detected by the routine:

$INFO < 0$: If $INFO = - i$ , the $i$ th parameter had an illegal value. An explanatory message is output, and execution of the program is terminated.

$INFO > 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.

7 Accuracy

The computed factors

L

and

U

are the exact factors of a perturbed matrix

A + E

, where

|E| \leq c (k) ε P |L| |U|,

c (k)

is a modest linear function of

k = k_{l} + k_{u} + 1

, and

ε

is the machine precision. This assumes

k ≪ \min (m, n)

8 Further Comments

The total number of floating point operations varies between approximately

2 n k_{l} (k_{u} + 1)

and

2 n k_{l} (k_{l} + k_{u} + 1)

, depending on the interchanges, assuming

m = n ≫ k_{l}

and

n ≫ k_{u}

A call to F07BDF (DGBTRF) may be followed by calls to the routines:

F07BEF (DGBTRS) to solve $A X = B$ or $A^{T} X = B$ ;
F07BGF (DGBCON) to estimate the condition number of $A$ .

The complex analogue of this routine is F07BRF (ZGBTRF).

9 Example

This example computes the

L U

factorization of the matrix

A

, where

A = (\begin{matrix} - 0.23 & 2.54 & - 3.66 & 0.00 \\ - 6.98 & 2.46 & - 2.73 & - 2.13 \\ 0.00 & 2.56 & 2.46 & 4.07 \\ 0.00 & 0.00 & - 4.78 & - 3.82 \end{matrix}) .

Here

A

is treated as a band matrix with one subdiagonal and two superdiagonals.

NAG Library Routine DocumentF07BDF (DGBTRF)

+− Contents

1 Purpose

2 Specification

3 Description

4 References

5 Parameters

6 Error Indicators and Warnings

7 Accuracy

8 Further Comments

9 Example

9.1 Program Text

9.2 Program Data

9.3 Program Results

NAG Library Routine Document

F07BDF (DGBTRF)