## MB04FP

### Eigenvalues and orthogonal decomposition of a real skew-Hamiltonian/skew-Hamiltonian pencil (applying transformations on panels of columns)

[Specification] [Arguments] [Method] [References] [Comments] [Example]

Purpose

To compute the eigenvalues of a real N-by-N skew-Hamiltonian/
skew-Hamiltonian pencil aS - bT with

(  A  D  )         (  B  F  )
S = (        ) and T = (        ).                           (1)
(  E  A' )         (  G  B' )

Optionally, if JOB = 'T', the pencil aS - bT will be transformed
to the structured Schur form: an orthogonal transformation matrix
Q is computed such that

(  Aout  Dout  )
J Q' J' S Q = (              ), and
(   0    Aout' )
(2)
(  Bout  Fout  )            (  0  I  )
J Q' J' T Q = (              ), where J = (        ),
(   0    Bout' )            ( -I  0  )

Aout is upper triangular, and Bout is upper quasi-triangular. The
notation M' denotes the transpose of the matrix M.
Optionally, if COMPQ = 'I' or COMPQ = 'U', the orthogonal
transformation matrix Q will be computed.

Specification
SUBROUTINE MB04FP( JOB, COMPQ, N, A, LDA, DE, LDDE, B, LDB, FG,
\$                   LDFG, Q, LDQ, ALPHAR, ALPHAI, BETA, IWORK,
\$                   DWORK, LDWORK, INFO )
C     .. Scalar Arguments ..
CHARACTER          COMPQ, JOB
INTEGER            INFO, LDA, LDB, LDDE, LDFG, LDQ, LDWORK, N
C     .. Array Arguments ..
DOUBLE PRECISION   A( LDA, * ), ALPHAI( * ), ALPHAR( * ),
\$                   B( LDB, * ), BETA( * ), DE( LDDE, * ),
\$                   DWORK( * ), FG( LDFG, * ), Q( LDQ, * )
INTEGER            IWORK( * )

Arguments

Mode Parameters

JOB     CHARACTER*1
Specifies the computation to be performed, as follows:
= 'E':  compute the eigenvalues only; S and T will not
necessarily be put into skew-Hamiltonian
triangular form (2);
= 'T':  put S and T into skew-Hamiltonian triangular form
(2), and return the eigenvalues in ALPHAR, ALPHAI
and BETA.

COMPQ   CHARACTER*1
Specifies whether to compute the orthogonal transformation
matrix Q as follows:
= 'N':  Q is not computed;
= 'I':  the array Q is initialized internally to the unit
matrix, and the orthogonal matrix Q is returned;
= 'U':  the array Q contains an orthogonal matrix Q0 on
entry, and the product Q0*Q is returned, where Q
is the product of the orthogonal transformations
that are applied to the pencil aS - bT to reduce
S and T to the forms in (2), for COMPQ = 'I'.

Input/Output Parameters
N       (input) INTEGER
The order of the pencil aS - bT.  N >= 0, even.

A       (input/output) DOUBLE PRECISION array, dimension
(LDA, N/2)
On entry, the leading N/2-by-N/2 part of this array must
contain the matrix A.
On exit, if JOB = 'T', the leading N/2-by-N/2 part of this
array contains the matrix Aout; otherwise, it contains
meaningless elements, except for the diagonal blocks,
which are correctly set.

LDA     INTEGER
The leading dimension of the array A.  LDA >= MAX(1, N/2).

DE      (input/output) DOUBLE PRECISION array, dimension
(LDDE, N/2+1)
On entry, the leading N/2-by-N/2 strictly lower triangular
part of this array must contain the strictly lower
triangular part of the skew-symmetric matrix E, and the
N/2-by-N/2 strictly upper triangular part of the submatrix
in the columns 2 to N/2+1 of this array must contain the
strictly upper triangular part of the skew-symmetric
matrix D.
The entries on the diagonal and the first superdiagonal of
this array are not referenced, but are assumed to be zero.
On exit, if JOB = 'T', the leading N/2-by-N/2 strictly
upper triangular part of the submatrix in the columns
2 to N/2+1 of this array contains the strictly upper
triangular part of the skew-symmetric matrix Dout.
If JOB = 'E', the leading N/2-by-N/2 strictly upper
triangular part of the submatrix in the columns 2 to N/2+1
of this array contains the strictly upper triangular part
of the skew-symmetric matrix D just before the application
of the QZ algorithm. The remaining entries are
meaningless.

LDDE    INTEGER
The leading dimension of the array DE.
LDDE >= MAX(1, N/2).

B       (input/output) DOUBLE PRECISION array, dimension
(LDB, N/2)
On entry, the leading N/2-by-N/2 part of this array must
contain the matrix B.
On exit, if JOB = 'T', the leading N/2-by-N/2 part of this
array contains the matrix Bout; otherwise, it contains
meaningless elements, except for the diagonal 1-by-1 and
2-by-2 blocks, which are correctly set.

LDB     INTEGER
The leading dimension of the array B.  LDB >= MAX(1, N/2).

FG      (input/output) DOUBLE PRECISION array, dimension
(LDFG, N/2+1)
On entry, the leading N/2-by-N/2 strictly lower triangular
part of this array must contain the strictly lower
triangular part of the skew-symmetric matrix G, and the
N/2-by-N/2 strictly upper triangular part of the submatrix
in the columns 2 to N/2+1 of this array must contain the
strictly upper triangular part of the skew-symmetric
matrix F.
The entries on the diagonal and the first superdiagonal of
this array are not referenced, but are assumed to be zero.
On exit, if JOB = 'T', the leading N/2-by-N/2 strictly
upper triangular part of the submatrix in the columns
2 to N/2+1 of this array contains the strictly upper
triangular part of the skew-symmetric matrix Fout.
If JOB = 'E', the leading N/2-by-N/2 strictly upper
triangular part of the submatrix in the columns 2 to N/2+1
of this array contains the strictly upper triangular part
of the skew-symmetric matrix F just before the application
of the QZ algorithm. The remaining entries are
meaningless.

LDFG    INTEGER
The leading dimension of the array FG.
LDFG >= MAX(1, N/2).

Q       (input/output) DOUBLE PRECISION array, dimension (LDQ, N)
On entry, if COMPQ = 'U', then the leading N-by-N part of
this array must contain a given matrix Q0, and on exit,
the leading N-by-N part of this array contains the product
of the input matrix Q0 and the transformation matrix Q
used to transform the matrices S and T.
On exit, if COMPQ = 'I', then the leading N-by-N part of
this array contains the orthogonal transformation matrix
Q.
If COMPQ = 'N', this array is not referenced.

LDQ     INTEGER
The leading dimension of the array Q.
LDQ >= 1,         if COMPQ = 'N';
LDQ >= MAX(1, N), if COMPQ = 'I' or COMPQ = 'U'.

ALPHAR  (output) DOUBLE PRECISION array, dimension (N/2)
The real parts of each scalar alpha defining an eigenvalue
of the pencil aS - bT.

ALPHAI  (output) DOUBLE PRECISION array, dimension (N/2)
The imaginary parts of each scalar alpha defining an
eigenvalue of the pencil aS - bT.
If ALPHAI(j) is zero, then the j-th eigenvalue is real; if
positive, then the j-th and (j+1)-st eigenvalues are a
complex conjugate pair.

BETA    (output) DOUBLE PRECISION array, dimension (N/2)
The scalars beta that define the eigenvalues of the pencil
aS - bT.
Together, the quantities alpha = (ALPHAR(j),ALPHAI(j)) and
beta = BETA(j) represent the j-th eigenvalue of the pencil
aS - bT, in the form lambda = alpha/beta. Since lambda may
overflow, the ratios should not, in general, be computed.
Due to the skew-Hamiltonian/skew-Hamiltonian structure of
the pencil, every eigenvalue occurs twice and thus it has
only to be saved once in ALPHAR, ALPHAI and BETA.

Workspace
IWORK   INTEGER array, dimension (N/2+1)
On exit, IWORK(1) contains the number of (pairs of)
possibly inaccurate eigenvalues, q <= N/2, and the
absolute values in IWORK(2), ..., IWORK(q+1) are their
indices, as well as of the corresponding diagonal blocks.
Specifically, a positive value is an index of a real
eigenvalue, corresponding to a 1-by-1 block pair, while
the absolute value of a negative entry in IWORK is an
index to the first eigenvalue in a pair of consecutively
stored eigenvalues, corresponding to a 2-by-2 block pair.

DWORK   DOUBLE PRECISION array, dimension (LDWORK)
On exit, if INFO = 0, DWORK(1) returns the optimal LDWORK;
DWORK(2) and DWORK(3) contain the Frobenius norms of the
matrices S and T on entry. These norms are used in the
tests to decide that some eigenvalues are considered as
unreliable.
On exit, if INFO = -19, DWORK(1) returns the minimum
value of LDWORK.

LDWORK  INTEGER
The dimension of the array DWORK.
LDWORK >= MAX(3,N/2,2*N-6),  if JOB = 'E' and COMPQ = 'N';
LDWORK >= MAX(3,N**2/4+N/2), if JOB = 'T' and COMPQ = 'N';
LDWORK >= MAX(1,3*N**2/4),   if               COMPQ<> 'N'.
For good performance LDWORK should generally be larger.

If LDWORK = -1, then a workspace query is assumed;
the routine only calculates the optimal size of the
DWORK array, returns this value as the first entry of
the DWORK array, and no error message related to LDWORK
is issued by XERBLA.

Error Indicator
INFO    INTEGER
= 0: succesful exit;
< 0: if INFO = -i, the i-th argument had an illegal value;
= 1: QZ iteration failed in the LAPACK Library routine
DHGEQZ. (QZ iteration did not converge or computation
of the shifts failed.)
= 2: warning: the pencil is numerically singular.

Method
The algorithm uses Givens rotations and Householder reflections to
annihilate elements in S and T such that S is in skew-Hamiltonian
triangular form and T is in skew-Hamiltonian Hessenberg form:

(  A1  D1  )      (  B1  F1  )
S = (          ), T = (          ),
(   0  A1' )      (   0  B1' )

where A1 is upper triangular and B1 is upper Hessenberg.
Subsequently, the QZ algorithm is applied to the pencil aA1 - bB1
to determine orthogonal matrices Q1 and Q2 such that
Q2' A1 Q1 is upper triangular and Q2' B1 Q1 is upper quasi-
triangular.
See also page 40 in [1] for more details.

References
[1] Benner, P., Byers, R., Mehrmann, V. and Xu, H.
Numerical Computation of Deflating Subspaces of Embedded
Hamiltonian Pencils.
Tech. Rep. SFB393/99-15, Technical University Chemnitz,
Germany, June 1999.

Numerical Aspects
3
The algorithm is numerically backward stable and needs O(N )
real floating point operations.

Further Comments
For large values of N, the routine applies the transformations
for reducing T on panels of columns. The user may specify in INFO
the desired number of columns. If on entry INFO <= 0, then the
routine estimates a suitable value of this number.

Example

Program Text

None
Program Data
None
Program Results
None