Computes the LDU factorization of a complex tridiagonal matrix A using a cyclic reduction algorithm.
Required Arguments
C — Complex array of size 2N containing the upper codiagonal of the N by N tridiagonal matrix in the entries C(1), …, C(N− 1). (Input/Output)
A — Complex array of size 2N containing the diagonal of the N by N tridiagonal matrix in the entries A(1), …, A(N). (Input/Output)
B — Complex array of size 2N containing the lower codiagonal of the N by N tridiagonal matrix in the entries B(1), …, B(N− 1). (Input/Output)
Y — Complex array of size 2N containing the right-hand side of the system Ax = y in the order Y(1), …, Y(N). (Input/Output) The vector x overwrites Y in storage.
U — Real array of size 2N of flags that indicate any singularities of A. (Output) A value U(I) = 1. means that a divide by zero would have occurred during the factoring. Otherwise U(I) = 0.
IR — Array of integers that determine the sizes of loops performed in the cyclic reduction algorithm. (Output)
IS — Array of integers that determine the sizes of loops performed in the cyclic reduction algorithm. (Output) The sizes of these arrays must be at least log2 (N) + 3.
Optional Arguments
N — Order of the matrix. (Input) N must be greater than zero. Default: N = size (C,1).
IJOB — Flag to direct the desired factoring or solving step. (Input) Default: IJOB =1.
IJOB
Action
1
Factor the matrix A and solve the system Ax = y, where y is stored in array Y.
2
Do the solve step only. Use y from array Y. (The factoring step has already been done.)
3
Factor the matrix A but do not solve a system.
4
Same meaning as with the value IJOB = 3. For efficiency, no error checking is done on the validity of any input value.
FORTRAN 90 Interface
Generic: CALL LSLCQ (C, A, B, Y, U, IR, IS[, …])
Specific: The specific interface names are S_LSLCQ and D_LSLCQ.
FORTRAN 77 Interface
Single: CALL LSLCQ (N, C, A, B, IJOB, Y, U, IR, IS)
Double: The double precision name is DLSLCQ.
Description
Routine LSLCQ factors and solves the complex tridiagonal linear system Ax = y. The matrix is decomposed in the form A = LDU, where L is unit lower triangular, U is unit upper triangular, and D is diagonal. The algorithm used for the factorization is effectively that described in Kershaw (1982). More details, tests and experiments are reported in Hanson (1990).
LSLCQ is intended just for tridiagonal systems. The coefficient matrix does not have to be Hermitian. The algorithm amounts to Gaussian elimination, with no pivoting for numerical stability, on the matrix whose rows and columns are permuted to a new order. See Hanson (1990) for details. The expectation is that LSLCQ will outperform either LSLTQ or LSLQB on vector or parallel computers. Its performance may be inferior for small values of n, on scalar computers, or high-performance computers with non-optimizing compilers.
Example
A real skew-symmetric tridiagonal matrix, A, of dimension n = 1000 is given by ck = −k, ak = 0, and bk = k, k = 1, …, n− 1, an = 0. This matrix will have eigenvalues that are purely imaginary. The eigenvalue closest to the imaginary unit is required. This number is obtained by using inverse iteration to approximate a complex eigenvector y. The eigenvalue is approximated by . (This example is contrived in the sense that the given tridiagonal skew-symmetric matrix eigenvalue problem is essentially equivalent to the tridiagonal symmetic eigenvalue problem where the ck = k and the other data are unchanged.)
