# ?herdb

Reduces a complex Hermitian matrix to tridiagonal form with Successive Bandwidth Reduction approach.

## Syntax

FORTRAN 77:

call cherdb(jobz, uplo, n, kd, a, lda, d, e, tau, z, ldz, work, lwork, info)

call zherdb(jobz, uplo, n, kd, a, lda, d, e, tau, z, ldz, work, lwork, info)

## Description

This routine reduces a complex Hermitian matrix A to symmetric tridiagonal form T by a unitary similarity transformation: `A = Q*T*QT` and optionally multuplies matrix Z by Q, or simply forms Q.

This routine reduces a full Hermitian matrix to the banded Hermitian form, and then to the tridiagonal symmetric form with a Successive Bandwidth Reduction approach after Prof. C.Bischof's works (see for instance, [Bischof92]). ?herdb is functionally close to ?hetrd routine but the tridiagonal form may differ from those obtained by ?hetrd. Unlike ?hetrd, the orthogonal matrix Q cannot be restored from the details of matrix A on exit.

## Input Parameters

jobz

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

  If `jobz = 'N'`, then only A is reduced to T.

  If `jobz = 'V'`, then A is reduced to T and A contains Q on exit.

  If `jobz = 'U'`, then A is reduced to T and Z contains `Z*Q` on exit.

uplo

  CHARACTER*1. Must be 'U' or 'L'.

  If `uplo = 'U'`, a stores the upper triangular part of A.

  If `uplo = 'L'`, a stores the lower triangular part of A.

n

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

kd

  INTEGER. The bandwidth of the banded matrix B (`kd ≥ 1`).

a,z, work

  COMPLEX for cherdb.

  DOUBLE COMPLEX for zherdb.

  a(lda,*) is an array containing either upper or lower triangular part of the matrix A, as specified by uplo.

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

  z(ldz,*), the second dimension of z must be at least `max(1, n)`.

  If `jobz = 'U'`, then the matrix z is multiplied by Q.

  If `jobz = 'N'` or 'V', then z is not referenced.

  work(lwork) is a workspace array.

lda

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

ldz

  INTEGER. The first dimension of z; at least `max(1, n)`. Not referenced if `jobz = 'N'`

lwork

  INTEGER. The size of the work array (`lwork ≥ (2kd+1)n+kd`).

  If `lwork = -1`, then a workspace query is assumed; the routine only calculates 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 the suggested value of lwork.

## Output Parameters

a

  If `jobz = 'V'`, then overwritten by Q matrix.

  If `jobz = 'N'` or `'U'`, then overwritten by the banded matrix B and details of the unitary matrix QB to reduce A to B as specified by uplo.

z

  On exit,

  if `jobz = 'U'`, then the matrix z is overwritten by `Z*Q` .

  If `jobz = 'N'` or `'V'`, then z is not referenced.

d, e

  COMPLEX for cherdb.

  DOUBLE COMPLEX for zherdb.

  Arrays:

  d(*) contains the diagonal elements of the matrix T.

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

  e(*) contains the off-diagonal elements of T.

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

  tau(*) stores further details of the orthogonal matrix Q.

  The dimension of tau must be at least max(1, n-kd-1).

tau

  COMPLEX for cherdb.

  DOUBLE COMPLEX for zherdb.

  Array, DIMENSION at least max(1, n-1)

  Stores further details of the unitary matrix QB. The dimension of tau must be at least max(1, n-kd-1).

`work(1)`

  If `info=0`, on exit `work(1)` contains the minimum value of lwork required for optimum performance. Use this lwork for subsequent runs.

info

  INTEGER.

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

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

## Application Notes

For better performance, try using `lwork = n*(3*kd+3)`.

If it is not clear how much workspace to supply, use a generous value of lwork for the first run, or set `lwork = -1`.

In first case 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 `lwork = -1`, then 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 lwork is less than the minimal required value and is not equal to -1, then the routine returns immediately with an error exit and does not provide any information on the recommended workspace.

For better performance, try using kd equal to 40 if `n ≤ 2000` and `64` otherwise.

Try using ?herdb instead of ?hetrd on large matrices obtaining only eigenvalues - when no eigenvectors are needed, especially in multi-threaded environment. ?herdb becomes faster beginning approximately with `n = 1000`, and much faster at larger matrices with a better scalability than ?hetrd.

Avoid applying ?herdb for computing eigenvectors due to the two-step reduction, that is, the number of operations needed to apply orthogonal transformations to Z is doubled compared to the traditional one-step reduction. In that case it is better to apply ?hetrd and ?unmtr/?ungtr to obtain tridiagonal form along with the unitary transformation matrix Q.

Parent topic: Symmetric Eigenvalue Problems