F08NHF (DGEBAL) : NAG Library, Mark 24

Note: before using this routine, please read the Users' Note for your implementation to check the interpretation of bold italicised terms and other implementation-dependent details.

F08NHF (DGEBAL) balances a real general matrix in order to improve the accuracy of computed eigenvalues and/or eigenvectors.

The routine may be called by its LAPACK name dgebal.

F08NHF (DGEBAL) balances a real general matrix

A

. The term ‘balancing’ covers two steps, each of which involves a similarity transformation of

A

. The routine can perform either or both of these steps.

The routine first attempts to permute $A$ to block upper triangular form by a similarity transformation:
$P A P^{T} = A^{'} = (\begin{matrix} A_{11}^{'} & A_{12}^{'} & A_{13}^{'} \\ 0 & A_{22}^{'} & A_{23}^{'} \\ 0 & 0 & A_{33}^{'} \end{matrix})$
where $P$ is a permutation matrix, and $A_{11}^{'}$ and $A_{33}^{'}$ are upper triangular. Then the diagonal elements of $A_{11}^{'}$ and $A_{33}^{'}$ are eigenvalues of $A$ . The rest of the eigenvalues of $A$ are the eigenvalues of the central diagonal block $A_{22}^{'}$ , in rows and columns $i_{lo}$ to $i_{hi}$ . Subsequent operations to compute the eigenvalues of $A$ (or its Schur factorization) need only be applied to these rows and columns; this can save a significant amount of work if $i_{lo} > 1$ and $i_{hi} < n$ . If no suitable permutation exists (as is often the case), the routine sets $i_{lo} = 1$ and $i_{hi} = n$ , and $A_{22}^{'}$ is the whole of $A$ .

The routine applies a diagonal similarity transformation to

A^{'}

, to make the rows and columns of

A_{22}^{'}

as close in norm as possible:

A^{''} = D A^{'} D^{- 1} = (\begin{matrix} I & 0 & 0 \\ 0 & D_{22} & 0 \\ 0 & 0 & I \end{matrix}) (\begin{matrix} A_{11}^{'} & A_{12}^{'} & A_{13}^{'} \\ 0 & A_{22}^{'} & A_{23}^{'} \\ 0 & 0 & A_{33}^{'} \end{matrix}) (\begin{matrix} I & 0 & 0 \\ 0 & D_{22}^{- 1} & 0 \\ 0 & 0 & I \end{matrix}) .

This scaling can reduce the norm of the matrix (i.e.,

‖A_{22}^{''}‖ < ‖A_{22}^{'}‖

) and hence reduce the effect of rounding errors on the accuracy of computed eigenvalues and eigenvectors.

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

On entry: indicates whether

A

is to be permuted and/or scaled (or neither).

$JOB ='N'$: $A$ is neither permuted nor scaled (but values are assigned to ILO, IHI and SCALE).
$JOB ='P'$: $A$ is permuted but not scaled.
$JOB ='S'$: $A$ is scaled but not permuted.
$JOB ='B'$: $A$ is both permuted and scaled.

Constraint:

JOB ='N'

'P'

'S'

'B'

On entry:

n

, the order of the matrix

A

Constraint:

N \geq 0

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

\max (1, N)

On entry: the

n

n

matrix

A

On exit: A is overwritten by the balanced matrix. If

JOB ='N'

, A is not referenced.

On entry: the first dimension of the array A as declared in the (sub)program from which F08NHF (DGEBAL) is called.

Constraint:

LDA \geq \max (1, N)

On exit: the values

i_{lo}

and

i_{hi}

such that on exit

A (i, j)

is zero if

i > j

and

1 \leq j < i_{lo}

i_{hi} < i \leq n

JOB ='N'

'S'

i_{lo} = 1

and

i_{hi} = n

On exit: details of the permutations and scaling factors applied to

A

. More precisely, if

p_{j}

is the index of the row and column interchanged with row and column

j

and

d_{j}

is the scaling factor used to balance row and column

j

then

SCALE (j) = \{\begin{cases} p_{j}, & j = 1, 2, \dots, i_{lo} - 1 \\ d_{j}, & j = i_{lo}, i_{lo} + 1, \dots, i_{hi} and \\ p_{j}, & j = i_{hi} + 1, i_{hi} + 2, \dots, n . \end{cases}

The order in which the interchanges are made is

n

i_{hi} + 1

then

1

i_{lo} - 1

On exit:

INFO = 0

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

Errors or warnings detected by the routine:

INFO = - i

, argument

i

had an illegal value. An explanatory message is output, and execution of the program is terminated.

The errors are negligible.

If the matrix

A

is balanced by F08NHF (DGEBAL), then any eigenvectors computed subsequently are eigenvectors of the matrix

A^{''}

(see Section 3) and hence F08NJF (DGEBAK) must then be called to transform them back to eigenvectors of

A

If the Schur vectors of

A

are required, then this routine must not be called with

JOB ='S'

'B'

, because then the balancing transformation is not orthogonal. If this routine is called with

JOB ='P'

, then any Schur vectors computed subsequently are Schur vectors of the matrix

A^{''}

, and F08NJF (DGEBAK) must be called (with

SIDE ='R'

) to transform them back to Schur vectors of

A

The total number of floating point operations is approximately proportional to

n^{2}

The complex analogue of this routine is F08NVF (ZGEBAL).

This example computes all the eigenvalues and right eigenvectors of the matrix

A

, where

A = (\begin{array}{r} 5.14 & 0.91 & 0.00 & - 32.80 \\ 0.91 & 0.20 & 0.00 & 34.50 \\ 1.90 & 0.80 & - 0.40 & - 3.00 \\ - 0.33 & 0.35 & 0.00 & 0.66 \end{array}) .

The program first calls F08NHF (DGEBAL) to balance the matrix; it then computes the Schur factorization of the balanced matrix, by reduction to Hessenberg form and the

Q R

algorithm. Then it calls F08QKF (DTREVC) to compute the right eigenvectors of the balanced matrix, and finally calls F08NJF (DGEBAK) to transform the eigenvectors back to eigenvectors of the original matrix

A

NAG Library Routine Document

F08NHF (DGEBAL)

+− 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 DocumentF08NHF (DGEBAL)

+− 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

F08NHF (DGEBAL)