F08 Chapter Contents
F08 Chapter Introduction
NAG Library Manual

# NAG Library Routine DocumentF08NHF (DGEBAL)

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.

## 1  Purpose

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

## 2  Specification

 SUBROUTINE F08NHF ( JOB, N, A, LDA, ILO, IHI, SCALE, INFO)
 INTEGER N, LDA, ILO, IHI, INFO REAL (KIND=nag_wp) A(LDA,*), SCALE(N) CHARACTER(1) JOB
The routine may be called by its LAPACK name dgebal.

## 3  Description

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.
1. The routine first attempts to permute $A$ to block upper triangular form by a similarity transformation:
 $PAPT = A′ = A11′ A12′ A13′ 0 A22′ A23′ 0 0 A33′$
where $P$ is a permutation matrix, and ${A}_{11}^{\prime }$ and ${A}_{33}^{\prime }$ are upper triangular. Then the diagonal elements of ${A}_{11}^{\prime }$ and ${A}_{33}^{\prime }$ are eigenvalues of $A$. The rest of the eigenvalues of $A$ are the eigenvalues of the central diagonal block ${A}_{22}^{\prime }$, in rows and columns ${i}_{\mathrm{lo}}$ to ${i}_{\mathrm{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}_{\mathrm{lo}}>1$ and ${i}_{\mathrm{hi}}. If no suitable permutation exists (as is often the case), the routine sets ${i}_{\mathrm{lo}}=1$ and ${i}_{\mathrm{hi}}=n$, and ${A}_{22}^{\prime }$ is the whole of $A$.
2. The routine applies a diagonal similarity transformation to ${A}^{\prime }$, to make the rows and columns of ${A}_{22}^{\prime }$ as close in norm as possible:
 $A′′ = DA′D-1 = I 0 0 0 D22 0 0 0 I A11′ A12′ A13′ 0 A22′ A23′ 0 0 A33′ I 0 0 0 D22-1 0 0 0 I .$
This scaling can reduce the norm of the matrix (i.e., $‖{A}_{22}^{\prime \prime }‖<‖{A}_{22}^{\prime }‖$) and hence reduce the effect of rounding errors on the accuracy of computed eigenvalues and eigenvectors.

## 4  References

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

## 5  Parameters

1:     JOB – CHARACTER(1)Input
On entry: indicates whether $A$ is to be permuted and/or scaled (or neither).
${\mathbf{JOB}}=\text{'N'}$
$A$ is neither permuted nor scaled (but values are assigned to ILO, IHI and SCALE).
${\mathbf{JOB}}=\text{'P'}$
$A$ is permuted but not scaled.
${\mathbf{JOB}}=\text{'S'}$
$A$ is scaled but not permuted.
${\mathbf{JOB}}=\text{'B'}$
$A$ is both permuted and scaled.
Constraint: ${\mathbf{JOB}}=\text{'N'}$, $\text{'P'}$, $\text{'S'}$ or $\text{'B'}$.
2:     N – INTEGERInput
On entry: $n$, the order of the matrix $A$.
Constraint: ${\mathbf{N}}\ge 0$.
3:     A(LDA,$*$) – REAL (KIND=nag_wp) arrayInput/Output
Note: the second dimension of the array A must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{N}}\right)$.
On entry: the $n$ by $n$ matrix $A$.
On exit: A is overwritten by the balanced matrix. If ${\mathbf{JOB}}=\text{'N'}$, A is not referenced.
4:     LDA – INTEGERInput
On entry: the first dimension of the array A as declared in the (sub)program from which F08NHF (DGEBAL) is called.
Constraint: ${\mathbf{LDA}}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{N}}\right)$.
5:     ILO – INTEGEROutput
6:     IHI – INTEGEROutput
On exit: the values ${i}_{\mathrm{lo}}$ and ${i}_{\mathrm{hi}}$ such that on exit ${\mathbf{A}}\left(i,j\right)$ is zero if $i>j$ and $1\le j<{i}_{\mathrm{lo}}$ or ${i}_{\mathrm{hi}}.
If ${\mathbf{JOB}}=\text{'N'}$ or $\text{'S'}$, ${i}_{\mathrm{lo}}=1$ and ${i}_{\mathrm{hi}}=n$.
7:     SCALE(N) – REAL (KIND=nag_wp) arrayOutput
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
 $SCALEj = pj, j=1,2,…,ilo-1 dj, j=ilo,ilo+1,…,ihi and pj, j=ihi+1,ihi+2,…,n.$
The order in which the interchanges are made is $n$ to ${i}_{\mathrm{hi}}+1$ then $1$ to ${i}_{\mathrm{lo}}-1$.
8:     INFO – INTEGEROutput
On exit: ${\mathbf{INFO}}=0$ unless the routine detects an error (see Section 6).

## 6  Error Indicators and Warnings

Errors or warnings detected by the routine:
${\mathbf{INFO}}<0$
If ${\mathbf{INFO}}=-i$, argument $i$ had an illegal value. An explanatory message is output, and execution of the program is terminated.

## 7  Accuracy

The errors are negligible.

If the matrix $A$ is balanced by F08NHF (DGEBAL), then any eigenvectors computed subsequently are eigenvectors of the matrix ${A}^{\prime \prime }$ (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 ${\mathbf{JOB}}=\text{'S'}$ or $\text{'B'}$, because then the balancing transformation is not orthogonal. If this routine is called with ${\mathbf{JOB}}=\text{'P'}$, then any Schur vectors computed subsequently are Schur vectors of the matrix ${A}^{\prime \prime }$, and F08NJF (DGEBAK) must be called (with ${\mathbf{SIDE}}=\text{'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).

## 9  Example

This example computes all the eigenvalues and right eigenvectors of the matrix $A$, where
 $A = 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 .$
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 $QR$ 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$.

### 9.1  Program Text

Program Text (f08nhfe.f90)

### 9.2  Program Data

Program Data (f08nhfe.d)

### 9.3  Program Results

Program Results (f08nhfe.r)