NAG Library Function Document

nag_zhseqr (f08psc)

+− Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

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

nag_zhseqr (f08psc) computes all the eigenvalues and, optionally, the Schur factorization of a complex Hessenberg matrix or a complex general matrix which has been reduced to Hessenberg form.

2 Specification

#include <nag.h>

#include <nagf08.h>

void	nag_zhseqr (Nag_OrderType order, Nag_JobType job, Nag_ComputeZType compz, Integer n, Integer ilo, Integer ihi, Complex h[], Integer pdh, Complex w[], Complex z[], Integer pdz, NagError *fail)

3 Description

nag_zhseqr (f08psc) computes all the eigenvalues and, optionally, the Schur factorization of a complex upper Hessenberg matrix

H

H = Z T Z^{H},

where

T

is an upper triangular matrix (the Schur form of

H

), and

Z

is the unitary matrix whose columns are the Schur vectors

z_{i}

. The diagonal elements of

T

are the eigenvalues of

H

The function may also be used to compute the Schur factorization of a complex general matrix

A

which has been reduced to upper Hessenberg form

H

\begin{array}{l} A & = & Q H Q^{H}, where ​ Q ​ is unitary, \\ = & (Q Z) T {(Q Z)}^{H} . \end{array}

In this case, after nag_zgehrd (f08nsc) has been called to reduce

A

to Hessenberg form, nag_zunghr (f08ntc) must be called to form

Q

explicitly;

Q

is then passed to nag_zhseqr (f08psc), which must be called with

compz = Nag_UpdateZ

The function can also take advantage of a previous call to nag_zgebal (f08nvc) which may have balanced the original matrix before reducing it to Hessenberg form, so that the Hessenberg matrix

H

has the structure:

(\begin{matrix} H_{11} & H_{12} & H_{13} \\ H_{22} & H_{23} \\ H_{33} \end{matrix})

where

H_{11}

and

H_{33}

are upper triangular. If so, only the central diagonal block

H_{22}

(in rows and columns

i_{lo}

i_{hi}

) needs to be further reduced to Schur form (the blocks

H_{12}

and

H_{23}

are also affected). Therefore the values of

i_{lo}

and

i_{hi}

can be supplied to nag_zhseqr (f08psc) directly. Also, nag_zgebak (f08nwc) must be called after this function to permute the Schur vectors of the balanced matrix to those of the original matrix. If nag_zgebal (f08nvc) has not been called however, then

i_{lo}

must be set to

1

and

i_{hi}

n

. Note that if the Schur factorization of

A

is required, nag_zgebal (f08nvc) must not be called with

job = Nag_Schur

Nag_DoBoth

, because the balancing transformation is not unitary.

nag_zhseqr (f08psc) uses a multishift form of the upper Hessenberg

Q R

algorithm, due to Bai and Demmel (1989). The Schur vectors are normalized so that

{‖z_{i}‖}_{2} = 1

, but are determined only to within a complex factor of absolute value

1

4 References

Bai Z and Demmel J W (1989) On a block implementation of Hessenberg multishift

Q R

iteration Internat. J. High Speed Comput. 1 97–112

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

5 Arguments

1: order – Nag_OrderTypeInput

On entry: the order argument specifies the two-dimensional storage scheme being used, i.e., row-major ordering or column-major ordering. C language defined storage is specified by

order = Nag_RowMajor

. See Section 3.2.1.3 in the Essential Introduction for a more detailed explanation of the use of this argument.

Constraint:

order = Nag_RowMajor

or Nag_ColMajor.

2: job – Nag_JobTypeInput

On entry: indicates whether eigenvalues only or the Schur form

T

is required.

$job = Nag_EigVals$: Eigenvalues only are required.
$job = Nag_Schur$: The Schur form $T$ is required.

Constraint:

job = Nag_EigVals

Nag_Schur

3: compz – Nag_ComputeZTypeInput

On entry: indicates whether the Schur vectors are to be computed.

$compz = Nag_NotZ$: No Schur vectors are computed (and the array z is not referenced).
$compz = Nag_InitZ$: The Schur vectors of $H$ are computed (and the array z is initialized by the function).
$compz = Nag_UpdateZ$: The Schur vectors of $A$ are computed (and the array z must contain the matrix $Q$ on entry).

Constraint:

compz = Nag_NotZ

Nag_UpdateZ

Nag_InitZ

4: n – IntegerInput

On entry:

n

, the order of the matrix

H

Constraint:

n \geq 0

5: ilo – IntegerInput

6: ihi – IntegerInput

On entry: if the matrix

A

has been balanced by nag_zgebal (f08nvc), then ilo and ihi must contain the values returned by that function. Otherwise, ilo must be set to

1

and ihi to n.

Constraint:

ilo \geq 1

and

\min (ilo, n) \leq ihi \leq n

7: h[ $\dim$ ] – ComplexInput/Output

Note: the dimension, dim, of the array h must be at least

\max (1, pdh \times n)

Where

H (i, j)

appears in this document, it refers to the array element

$h [(j - 1) \times pdh + i - 1]$ when $order = Nag_ColMajor$ ;
$h [(i - 1) \times pdh + j - 1]$ when $order = Nag_RowMajor$ .

On entry: the

n

n

upper Hessenberg matrix

H

, as returned by nag_zgehrd (f08nsc).

On exit: if

job = Nag_EigVals

, the array contains no useful information.

job = Nag_Schur

, h is overwritten by the upper triangular matrix

T

from the Schur decomposition (the Schur form) unless

fail . code =

NE_CONVERGENCE.

8: pdh – IntegerInput

On entry: the stride separating row or column elements (depending on the value of order) in the array h.

Constraint:

pdh \geq \max (1, n)

9: w[ $\dim$ ] – ComplexOutput

Note: the dimension, dim, of the array w must be at least

\max (1, n)

On exit: the computed eigenvalues, unless

fail . code =

NE_CONVERGENCE (in which case see Section 6). The eigenvalues are stored in the same order as on the diagonal of the Schur form

T

(if computed).

10: z[ $\dim$ ] – ComplexInput/Output

Note: the dimension, dim, of the array z must be at least

$\max (1, pdz \times n)$ when $compz = Nag_UpdateZ$ or $Nag_InitZ$ and $order = Nag_ColMajor$ ;
$\max (1, \times pdz)$ when $compz = Nag_UpdateZ$ or $Nag_InitZ$ and $order = Nag_RowMajor$ ;
$1$ when $compz = Nag_NotZ$ .

The

(i, j)

th element of the matrix

Z

is stored in

$z [(j - 1) \times pdz + i - 1]$ when $order = Nag_ColMajor$ ;
$z [(i - 1) \times pdz + j - 1]$ when $order = Nag_RowMajor$ .

On entry: if

compz = Nag_UpdateZ

, z must contain the unitary matrix

Q

from the reduction to Hessenberg form.

compz = Nag_InitZ

, z need not be set.

On exit: if

compz = Nag_UpdateZ

Nag_InitZ

, z contains the unitary matrix of the required Schur vectors, unless

fail . code =

NE_CONVERGENCE.

compz = Nag_NotZ

, z is not referenced.

11: pdz – IntegerInput

On entry: the stride separating row or column elements (depending on the value of order) in the array z.

Constraints:

if order=Nag_ColMajor,
- if $compz = Nag_InitZ$ or $Nag_UpdateZ$ , $pdz \geq \max (1, n)$ ;
- if $compz = Nag_NotZ$ , $pdz \geq 1$ ;
if order=Nag_RowMajor,
- if $compz = Nag_UpdateZ$ or $Nag_InitZ$ , $pdz \geq \max (1, n)$ ;
- if $compz = Nag_NotZ$ , $pdz \geq 1$ .

12: fail – NagError *Input/Output

The NAG error argument (see Section 3.6 in the Essential Introduction).

6 Error Indicators and Warnings

NE_ALLOC_FAIL: Dynamic memory allocation failed.
NE_BAD_PARAM: On entry, argument $〈value〉$ had an illegal value.
NE_CONVERGENCE: The algorithm has failed to find all the eigenvalues after a total of $30 (ihi - ilo + 1)$ iterations.
NE_ENUM_INT_2: On entry, $compz = 〈value〉$ , $pdz = 〈value〉$ and $n = 〈value〉$ .
Constraint: if $compz = Nag_InitZ$ or $Nag_UpdateZ$ , $pdz \geq \max (1, n)$ ;
if $compz = Nag_NotZ$ , $pdz \geq 1$ .
NE_INT: On entry, $n = 〈value〉$ .
Constraint: $n \geq 0$ .; On entry, $pdh = 〈value〉$ .
Constraint: $pdh > 0$ .; On entry, $pdz = 〈value〉$ .
Constraint: $pdz > 0$ .
NE_INT_2: On entry, $pdh = 〈value〉$ and $n = 〈value〉$ .
Constraint: $pdh \geq \max (1, n)$ .
NE_INT_3: On entry, $n = 〈value〉$ , $ilo = 〈value〉$ and $ihi = 〈value〉$ .
Constraint: $ilo \geq 1$ and $\min (ilo, n) \leq ihi \leq n$ .
NE_INTERNAL_ERROR: An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact NAG for assistance.

7 Accuracy

The computed Schur factorization is the exact factorization of a nearby matrix

(H + E)

, where

{‖E‖}_{2} = O (ε) {‖H‖}_{2},

and

ε

is the machine precision.

λ_{i}

is an exact eigenvalue, and

{\tilde{λ}}_{i}

is the corresponding computed value, then

|{\tilde{λ}}_{i} - λ_{i}| \leq \frac{c (n) ε {‖H‖}_{2}}{s_{i}},

where

c (n)

is a modestly increasing function of

n

, and

s_{i}

is the reciprocal condition number of

λ_{i}

. The condition numbers

s_{i}

may be computed by calling nag_ztrsna (f08qyc).

8 Further Comments

The total number of real floating point operations depends on how rapidly the algorithm converges, but is typically about:

$25 n^{3}$ if only eigenvalues are computed;
$35 n^{3}$ if the Schur form is computed;
$70 n^{3}$ if the full Schur factorization is computed.

The real analogue of this function is nag_dhseqr (f08pec).

9 Example

This example computes all the eigenvalues and the Schur factorization of the upper Hessenberg matrix

H

, where

H = (\begin{array}{r} - 3.9700 - 5.0400 i & - 1.1318 - 2.5693 i & - 4.6027 - 0.1426 i & - 1.4249 + 1.7330 i \\ - 5.4797 + 0.0000 i & 1.8585 - 1.5502 i & 4.4145 - 0.7638 i & - 0.4805 - 1.1976 i \\ 0.0000 + 0.0000 i & 6.2673 + 0.0000 i & - 0.4504 - 0.0290 i & - 1.3467 + 1.6579 i \\ 0.0000 + 0.0000 i & 0.0000 + 0.0000 i & - 3.5000 + 0.0000 i & 2.5619 - 3.3708 i \end{array}) .

See also Section 9 in nag_zunghr (f08ntc), which illustrates the use of this function to compute the Schur factorization of a general matrix.

NAG Library Function Documentnag_zhseqr (f08psc)

+− Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

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 Function Document

nag_zhseqr (f08psc)