NAG Library Function Document

nag_dtgsyl (f08yhc)

nag_dtgsyl (Nag_OrderType order, Nag_TransType trans, Integer ijob, Integer m, Integer n, const double a[], Integer pda, const double b[], Integer pdb, double c[], Integer pdc, const double d[], Integer pdd, const double e[], Integer pde, double f[], Integer pdf, double *scale, double *dif, NagError *fail)

3 Description

nag_dtgsyl (f08yhc) solves either the generalized real Sylvester equations

\begin{matrix} A R - L B & = α C \\ D R - L E & = α F, \end{matrix}

(1)

or the equations

\begin{matrix} A^{T} R + D^{T} L & = α C \\ R B^{T} + L E^{T} & = - α F, \end{matrix}

(2)

where the pair

(A, D)

are given

m

m

matrices in real generalized Schur form,

(B, E)

are given

n

n

matrices in real generalized Schur form and

(C, F)

are given

m

n

matrices. The pair

(R, L)

are the

m

n

solution matrices, and

α

is an output scaling factor determined by the function to avoid overflow in computing

(R, L)

Equations (1) are equivalent to equations of the form

Z x = α b,

where

Z = (\begin{matrix} I \otimes A - B^{T} \otimes I \\ I \otimes D - E^{T} \otimes I \end{matrix})

and

\otimes

is the Kronecker product. Equations (2) are then equivalent to

Z^{T} y = α b .

The pair

(S, T)

are in real generalized Schur form if

S

is block upper triangular with

1

1

and

2

2

diagonal blocks on the diagonal and

T

is upper triangular as returned, for example, by nag_dgges (f08xac), or nag_dhgeqz (f08xec) with

job = Nag_Schur

Optionally, the function estimates

Dif [(A, D), (B, E)]

, the separation between the matrix pairs

(A, D)

and

(B, E)

, which is the smallest singular value of

Z

. The estimate can be based on either the Frobenius norm, or the

1

-norm. The

1

-norm estimate can be three to ten times more expensive than the Frobenius norm estimate, but makes the condition estimation uniform with the nonsymmetric eigenproblem. The Frobenius norm estimate provides a low cost, but equally reliable estimate. For more information see Sections 2.4.8.3 and 4.11.1.3 of Anderson et al. (1999) and Kågström and Poromaa (1996).

4 References

Anderson E, Bai Z, Bischof C, Blackford S, Demmel J, Dongarra J J, Du Croz J J, Greenbaum A, Hammarling S, McKenney A and Sorensen D (1999) LAPACK Users' Guide (3rd Edition) SIAM, Philadelphia http://www.netlib.org/lapack/lug

Kågström B (1994) A perturbation analysis of the generalized Sylvester equation

(A R - L B, D R - L E) = (c, F)

SIAM J. Matrix Anal. Appl. 15 1045–1060

Kågström B and Poromaa P (1996) LAPACK-style algorithms and software for solving the generalized Sylvester equation and estimating the separation between regular matrix pairs ACM Trans. Math. Software 22 78–103

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: trans – Nag_TransTypeInput

On entry: if

trans = Nag_NoTrans

, solve the generalized Sylvester equation (1).

trans = Nag_Trans

, solve the ‘transposed’ system (2).

Constraint:

trans = Nag_NoTrans

Nag_Trans

3: ijob – IntegerInput

On entry: specifies what kind of functionality is to be performed when

trans = Nag_NoTrans

$ijob = 0$: Solve (1) only.
$ijob = 1$: The functionality of $ijob = 0$ and $3$ .
$ijob = 2$: The functionality of $ijob = 0$ and $4$ .
$ijob = 3$: Only an estimate of $Dif [(A, D), (B, E)]$ is computed based on the Frobenius norm.
$ijob = 4$: Only an estimate of $Dif [(A, D), (B, E)]$ is computed based on the $1$ -norm.

trans = Nag_Trans

, ijob is not referenced.

Constraint: if

trans = Nag_NoTrans

0 \leq ijob \leq 4

4: m – IntegerInput

On entry:

m

, the order of the matrices

A

and

D

, and the row dimension of the matrices

C

F

R

and

L

Constraint:

m \geq 0

5: n – IntegerInput

On entry:

n

, the order of the matrices

B

and

E

, and the column dimension of the matrices

C

F

R

and

L

Constraint:

n \geq 0

6: a[ $\dim$ ] – const doubleInput

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

\max (1, pda \times m)

The

(i, j)

th element of the matrix

A

is stored in

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

On entry: the upper quasi-triangular matrix

A

7: pda – IntegerInput

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

Constraint:

pda \geq \max (1, m)

8: b[ $\dim$ ] – const doubleInput

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

\max (1, pdb \times n)

The

(i, j)

th element of the matrix

B

is stored in

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

On entry: the upper quasi-triangular matrix

B

9: pdb – IntegerInput

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

Constraint:

pdb \geq \max (1, n)

10: c[ $\dim$ ] – doubleInput/Output

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

$\max (1, pdc \times n)$ when $order = Nag_ColMajor$ ;
$\max (1, m \times pdc)$ when $order = Nag_RowMajor$ .

The

(i, j)

th element of the matrix

C

is stored in

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

On entry: contains the right-hand-side matrix

C

On exit: if

ijob = 0

1

2

, c is overwritten by the solution matrix

R

trans = Nag_NoTrans

and

ijob = 3

4

, c holds

R

, the solution achieved during the computation of the Dif estimate.

11: pdc – IntegerInput

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

Constraints:

if $order = Nag_ColMajor$ , $pdc \geq \max (1, m)$ ;
if $order = Nag_RowMajor$ , $pdc \geq \max (1, n)$ .

12: d[ $\dim$ ] – const doubleInput

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

\max (1, pdd \times m)

The

(i, j)

th element of the matrix

D

is stored in

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

On entry: the upper triangular matrix

D

13: pdd – IntegerInput

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

Constraint:

pdd \geq \max (1, m)

14: e[ $\dim$ ] – const doubleInput

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

\max (1, pde \times n)

The

(i, j)

th element of the matrix

E

is stored in

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

On entry: the upper triangular matrix

E

15: pde – IntegerInput

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

Constraint:

pde \geq \max (1, n)

16: f[ $\dim$ ] – doubleInput/Output

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

$\max (1, pdf \times n)$ when $order = Nag_ColMajor$ ;
$\max (1, m \times pdf)$ when $order = Nag_RowMajor$ .

The

(i, j)

th element of the matrix

F

is stored in

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

On entry: contains the right-hand side matrix

F

On exit: if

ijob = 0

1

2

, f is overwritten by the solution matrix

L

trans = Nag_NoTrans

and

ijob = 3

4

, f holds

L

, the solution achieved during the computation of the Dif estimate.

17: pdf – IntegerInput

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

Constraints:

if $order = Nag_ColMajor$ , $pdf \geq \max (1, m)$ ;
if $order = Nag_RowMajor$ , $pdf \geq \max (1, n)$ .

18: scale – double *Output

On exit:

α

, the scaling factor in (1) or (2).

0 < scale < 1

, c and f hold the solutions

R

and

L

, respectively, to a slightly perturbed system but the input arrays a, b, d and e have not been changed.

scale = 0

, c and f hold the solutions

R

and

L

, respectively, to the homogeneous system with

C = F = 0

. In this case dif is not referenced.

Normally,

scale = 1

19: dif – double *Output

On exit: the estimate of

Dif

. If

ijob = 0

, dif is not referenced.

20: 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_EIGENVALUES: $(A, D)$ and $(B, E)$ have common or close eigenvalues and so no solution could be computed.
NE_ENUM_INT: On entry, $ijob = 〈value〉$ and $trans = 〈value〉$ .
Constraint: if $trans = Nag_NoTrans$ , $0 \leq ijob \leq 4$ .
NE_INT: On entry, $m = 〈value〉$ .
Constraint: $m \geq 0$ .; On entry, $n = 〈value〉$ .
Constraint: $n \geq 0$ .; On entry, $pda = 〈value〉$ .
Constraint: $pda > 0$ .; On entry, $pdb = 〈value〉$ .
Constraint: $pdb > 0$ .; On entry, $pdc = 〈value〉$ .
Constraint: $pdc > 0$ .; On entry, $pdd = 〈value〉$ .
Constraint: $pdd > 0$ .; On entry, $pde = 〈value〉$ .
Constraint: $pde > 0$ .; On entry, $pdf = 〈value〉$ .
Constraint: $pdf > 0$ .
NE_INT_2: On entry, $pda = 〈value〉$ and $m = 〈value〉$ .
Constraint: $pda \geq \max (1, m)$ .; On entry, $pdb = 〈value〉$ and $n = 〈value〉$ .
Constraint: $pdb \geq \max (1, n)$ .; On entry, $pdc = 〈value〉$ and $m = 〈value〉$ .
Constraint: $pdc \geq \max (1, m)$ .; On entry, $pdc = 〈value〉$ and $n = 〈value〉$ .
Constraint: $pdc \geq \max (1, n)$ .; On entry, $pdd = 〈value〉$ and $m = 〈value〉$ .
Constraint: $pdd \geq \max (1, m)$ .; On entry, $pde = 〈value〉$ and $n = 〈value〉$ .
Constraint: $pde \geq \max (1, n)$ .; On entry, $pdf = 〈value〉$ and $m = 〈value〉$ .
Constraint: $pdf \geq \max (1, m)$ .; On entry, $pdf = 〈value〉$ and $n = 〈value〉$ .
Constraint: $pdf \geq \max (1, 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

See Kågström (1994) for a perturbation analysis of the generalized Sylvester equation.

8 Further Comments

The total number of floating point operations needed to solve the generalized Sylvester equations is approximately

2 m n (n + m)

. The Frobenius norm estimate of

Dif

does not require additional significant computation, but the

1

-norm estimate is typically five times more expensive.

The complex analogue of this function is nag_ztgsyl (f08yvc).

9 Example

This example solves the generalized Sylvester equations

\begin{matrix} A R - L B & = α C \\ D R - L E & = α F, \end{matrix}

where

A = (\begin{array}{r} 4.0 & 1.0 & 1.0 & 2.0 \\ 0 & 3.0 & 4.0 & 1.0 \\ 0 & 1.0 & 3.0 & 1.0 \\ 0 & 0 & 0 & 6.0 \end{array}), B = (\begin{array}{r} 1.0 & 1.0 & 1.0 & 1.0 \\ 0 & 3.0 & 4.0 & 1.0 \\ 0 & 1.0 & 3.0 & 1.0 \\ 0 & 0 & 0 & 4.0 \end{array}),

D = (\begin{array}{r} 2.0 & 1.0 & 1.0 & 3.0 \\ 0 & 1.0 & 2.0 & 1.0 \\ 0 & 0 & 1.0 & 1.0 \\ 0 & 0 & 0 & 2.0 \end{array}), E = (\begin{array}{r} 1.0 & 1.0 & 1.0 & 2.0 \\ 0 & 1.0 & 4.0 & 1.0 \\ 0 & 0 & 1.0 & 1.0 \\ 0 & 0 & 0 & 1.0 \end{array}),

C = (\begin{array}{r} - 4.0 & 7.0 & 1.0 & 12.0 \\ - 9.0 & 2.0 & - 2.0 & - 2.0 \\ - 4.0 & 2.0 & - 2.0 & 8.0 \\ - 7.0 & 7.0 & - 6.0 & 19.0 \end{array}) and F = (\begin{array}{r} - 7.0 & 5.0 & 0.0 & 7.0 \\ - 5.0 & 1.0 & - 8.0 & 0.0 \\ - 1.0 & 2.0 & - 3.0 & 5.0 \\ - 3.0 & 2.0 & 0.0 & 5.0 \end{array}) .

NAG Library Function Documentnag_dtgsyl (f08yhc)

+− 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_dtgsyl (f08yhc)