# ?hseqr

Computes all eigenvalues and (optionally) the Schur factorization of a matrix reduced to Hessenberg form.

## Syntax

FORTRAN 77:

call shseqr(job, compz, n, ilo, ihi, h, ldh, wr, wi, z, ldz, work, lwork, info)

call dhseqr(job, compz, n, ilo, ihi, h, ldh, wr, wi, z, ldz, work, lwork, info)

call chseqr(job, compz, n, ilo, ihi, h, ldh, w, z, ldz, work, lwork, info)

call zhseqr(job, compz, n, ilo, ihi, h, ldh, w, z, ldz, work, lwork, info)

Fortran 95:

call hseqr(h, wr, wi [,ilo] [,ihi] [,z] [,job] [,compz] [,info])

call hseqr(h, w [,ilo] [,ihi] [,z] [,job] [,compz] [,info])

## Description

This routine computes all the eigenvalues, and optionally the Schur factorization, of an upper Hessenberg matrix H: `H = Z*T*ZH`, where T is an upper triangular (or, for real flavors, quasi-triangular) matrix (the Schur form of H), and Z is the unitary or orthogonal matrix whose columns are the Schur vectors zi.

You can also use this routine to compute the Schur factorization of a general matrix A which has been reduced to upper Hessenberg form H:

`A = Q*H*QH`, where Q is unitary (orthogonal for real flavors);

`A = (QZ)*H*(QZ)H`.

In this case, after reducing A to Hessenberg form by ?gehrd, call ?orghr to form Q explicitly and then pass Q to ?hseqr with `compz = 'V'`.

You can also call ?gebal to balance the original matrix before reducing it to Hessenberg form by ?hseqr, so that the Hessenberg matrix H will have the structure:

where H11 and H33 are upper triangular.

If so, only the central diagonal block H22 (in rows and columns ilo to ihi) needs to be further reduced to Schur form (the blocks H12 and H23 are also affected). Therefore the values of ilo and ihi can be supplied to ?hseqr directly. Also, after calling this routine you must call ?gebak to permute the Schur vectors of the balanced matrix to those of the original matrix.

If ?gebal has not been called, however, then ilo must be set to 1 and ihi to n. Note that if the Schur factorization of A is required, ?gebal must not be called with `job = 'S'` or 'B', because the balancing transformation is not unitary (for real flavors, it is not orthogonal).

?hseqr uses a multishift form of the upper Hessenberg QR algorithm. The Schur vectors are normalized so that `||zi||2 = 1`, but are determined only to within a complex factor of absolute value 1 (for the real flavors, to within a factor ±1).

## Input Parameters

job

  CHARACTER*1. Must be 'E' or 'S'.

  If `job = 'E'`, then eigenvalues only are required.

  If `job = 'S'`, then the Schur form T is required.

compz

  CHARACTER*1. Must be 'N' or 'I' or 'V'.

  If compz = 'N', then no Schur vectors are computed (and the array z is not referenced).

  If compz = 'I', then the Schur vectors of H are computed (and the array z is initialized by the routine).

  If compz = 'V', then the Schur vectors of A are computed (and the array z must contain the matrix Q on entry).

n

  INTEGER. The order of the matrix H (`n ≥ 0`).

ilo, ihi

  INTEGER. If A has been balanced by ?gebal, then ilo and ihi must contain the values returned by ?gebal. Otherwise, ilo must be set to 1 and ihi to n.

h, z, work

  REAL for shseqr

  DOUBLE PRECISION for dhseqr

  COMPLEX for chseqr

  DOUBLE COMPLEX for zhseqr.

  Arrays:

  h(ldh,*) The n-by-n upper Hessenberg matrix H.

  The second dimension of h must be at least max(1, n).

  z(ldz,*)

  If `compz = 'V'`, then z must contain the matrix Q from the reduction to Hessenberg form.

  If `compz = 'I'`, then z need not be set.

  If `compz = 'N'`, then z is not referenced.

  The second dimension of z must be

  at least max(1, n) if `compz = 'V'` or 'I';

  at least 1 if `compz = 'N'`.

  work(lwork) is a workspace array.

  The dimension of work must be at least max (1, n).

ldh

  INTEGER. The first dimension of h; at least max(1, n).

ldz

  INTEGER. The first dimension of z;

  If `compz = 'N'`, then `ldz ≥ 1`.

  If `compz = 'V'` or 'I', then `ldz ≥ max(1, n)`.

lwork

  INTEGER. The dimension of the array work.

  `lwork ≥ max(1, n)`is sufficient, but lwork typically as large as `6*n` may be required for optimal performance. A workspace query to determine the optimal workspace size is recommended.

  If `lwork = -1`, then a workspace query is assumed; the routine only estimates the optimal size of the work array, returns this value as the first entry of the work array, and no error message related to lwork is issued by xerbla. See Application Notes for details.

## Output Parameters

w

  COMPLEX for chseqr

  DOUBLE COMPLEX for zhseqr.

  Array, DIMENSION at least max (1, n). Contains the computed eigenvalues, unless info>0. The eigenvalues are stored in the same order as on the diagonal of the Schur form T (if computed).

wr, wi

  REAL for shseqr

  DOUBLE PRECISION for dhseqr

  Arrays, DIMENSION at least max (1, n) each.

  Contain the real and imaginary parts, respectively, of the computed eigenvalues, unless `info > 0`. Complex conjugate pairs of eigenvalues appear consecutively with the eigenvalue having positive imaginary part first. The eigenvalues are stored in the same order as on the diagonal of the Schur form T (if computed).

h

  If `info = 0` and `job = 'S'`, h contains the upper triangular matrix T from the Schur decomposition (the Schur form).

  If `info = 0` and `job = 'E'`, the contents of h are unspecified on exit. (The output value of h when `info > 0` is given under the description of info below.)

z

  If `compz = 'V'` and `info = 0`, then z contains `Q*Z`.

  If `compz = 'I'` and `info = 0`, then z contains the unitary or orthogonal matrix Z of the Schur vectors of H.

  If `compz = 'N'`, then z is not referenced.

work(1)

  On exit, if `info = 0`, then work(1) returns the optimal lwork.

info

  INTEGER.

  If `info = 0`, the execution is successful.

  If `info = -i`, the i-th parameter had an illegal value.

  If `info = i`, elements 1,2, ..., ilo-1 and i+1, i+2, ..., n of wr and wi contain the real and imaginary parts of those eigenvalues that have been succesively found.

  If `info > 0`, and `job = 'E'`, then on exit, the remaining unconverged eigenvalues are the eigenvalues of the upper Hessenberg matrix rows and columns ilo through info of the final output value of H.

  If `info > 0`, and `job = 'S'`, then on exit (initial value of H)*U = U*(final value of H), where U is a unitary matrix. The final value of H is upper Hessenberg and triangular in rows and columns `info+1` through ihi.

  If `info > 0`, and `compz = 'V'`, then on exit (final value of Z) = (initial value of Z)*U, where U is the unitary matrix (regardless of the value of job).

  If `info > 0`, and `compz = 'I'`, then on exit (final value of Z) = U, where U is the unitary matrix (regardless of the value of job).

  If `info > 0`, and `compz = 'N'`, then Z is not accessed.

## Fortran 95 Interface Notes

Routines in Fortran 95 interface have fewer arguments in the calling sequence than their FORTRAN 77 counterparts. For general conventions applied to skip redundant or restorable arguments, see Fortran 95 Interface Conventions.

Specific details for the routine hseqr interface are the following:

h

  Holds the matrix H of size (n,n).

wr

  Holds the vector of length (n). Used in real flavors only.

wi

  Holds the vector of length (n). Used in real flavors only.

w

  Holds the vector of length (n). Used in complex flavors only.

z

  Holds the matrix Z of size (n,n).

job

  Must be 'E' or 'S'. The default value is 'E'.

compz

  If omitted, this argument is restored based on the presence of argument z as follows: `compz = 'I'`, if z is present, `compz = 'N'`, if z is omitted.

  If present, compz must be equal to 'I' or 'V' and the argument z must also be present. Note that there will be an error condition if compz is present and z omitted.

## Application Notes

The computed Schur factorization is the exact factorization of a nearby matrix `H + E`, where `||E||2 < O(ε) ||H||2/si`, and ε is the machine precision.

If λi is an exact eigenvalue, and μi is the corresponding computed value, then ``|λi - μi|≤ c(n)*ε*||H||2/si`` , where `c(n)` is a modestly increasing function of n, and si is the reciprocal condition number of λi. The condition numbers si may be computed by calling ?trsna.

The total number of floating-point operations depends on how rapidly the algorithm converges; typical numbers are as follows.

If only eigenvalues are computed:

  7n3 for real flavors

  25n3 for complex flavors.

If the Schur form is computed:

  10n3 for real flavors

  35n3 for complex flavors.

If the full Schur factorization is computed:

  20n3 for real flavors

  70n3 for complex flavors.

If you are in doubt how much workspace to supply, use a generous value of lwork for the first run or set `lwork = -1`.

If you choose the first option and set any of admissible lwork sizes, which is no less than the minimal value described, the routine completes the task, though probably not so fast as with a recommended workspace, and provides the recommended workspace in the first element of the corresponding array work on exit. Use this value (`work(1)`) for subsequent runs.

If you set `lwork = -1`, the routine returns immediately and provides the recommended workspace in the first element of the corresponding array (work). This operation is called a workspace query.

Note that if you set lwork to less than the minimal required value and not -1, the routine returns immediately with an error exit and does not provide any information on the recommended workspace.

Parent topic: Nonsymmetric Eigenvalue Problems