From CULLUMJ@IBM-SJ.ARPA Fri Feb 28 00:37:41 1986
Received: from IBM-SJ.ARPA (ibm-sj.arpa.ARPA) by anl-mcs.ARPA (4.12/4.9)
id AA01650; Fri, 28 Feb 86 00:36:53 cst
Date: Fri, 28 Feb 86 00:36:36 cst
From: CULLUMJ@IBM-SJ.ARPA
Message-Id: <8602280636.AA01650@anl-mcs.ARPA>
Apparently-To:
Status: RO
INDEX
LANCZOS CODES WITH NO REORTHOGONALIZATION
The Argonne Library contains Lanczos codes with no reorthogonalization
for computing eigenvalues and eigenvectors of (1) real symmetric
matrices and (2) of Hermitian matrices,
and (3) for computing singular values and corresponding
singular vectors of real, rectangular matrices. (8/84 codes)
Similar codes for computing eigenvalues and eigenvectors of
(4) factored inverses of real symmetric matrices, (5) of real symmetric
generalized problems, and (6) of diagonalizable, complex symmetric
matrices are available from the authors. Block Lanczos codes
for computing a few extreme eigenvalues and corresponding
eigenvectors of real symmetric matrices are also available from
the authors. The Block codes use limited reorthogonalization of
the Lanczos vectors with respect to converged Ritz vectors.
The authors are currently developing Lanczos codes for
diagonalizable nonsymmetric matrices which should be available
by the end of 1986.
Jane Cullum and Ralph Willoughby
IBM Research
Yorktown Heights, N.Y. 10598
Phone: 914-945-2227
Please contact the authors if you encounter any problems.
Detailed comments and documentation for these and for the other
Lanczos codes are available in the 2-volume book.
Anyone contemplating using these codes should read the detailed
documentation first.
LANCZOS ALGORITHMS FOR LARGE SYMMETRIC EIGENVALUE COMPUTATIONS
Jane K. Cullum and Ralph A. Willoughby
Volume 1. Theory: ($30) Volume 2. Programs ($50)
Volumes 3 and 4 in Progress in Scientific Computing
Series, Edited by S. Abarbanel, R. Glowinski, G. Golub,
P. Henrici, H. O. Kreiss. Published by Birkhauser,
Basel, Switzerland, January 1985.
Observed user problems with these codes have been (1) Failure to
define large enough working arrays; (2) Subtle bugs in the user-
supplied subroutines which define the matrix and perform the
matrix-vector multiplies or solves (see USPEC, CMATV, AMATV, BSOLV,
and LSOLV below), and (3) The BISEC subroutine assumes that no more
than KMAX/2 eigenvalues are to be computed in any subinterval supplied
to it. These Lanczos codes assume that all of the required
computations are done in at least IBM double precision arithmetic.
The presence of bugs in the user-supplied subroutines should be
readily identifiable by the subsequent observed nonconvergence
of 'all' of the eigenvalues approximations.
LANCZOS CODES FOR REAL SYMMETRIC MATRICES (No reorthogonalization)
DOCUMENTATION: The file LEVALHED contains the required documentation
for the Real Symmetric, the Hermitian, the Factored Inverse,
and the Generalized Real Symmetric Lanczos Codes with no
reorthogonalization.
LEVAL: This is the main program for computing eigenvalues of a real
symmetric matrix using a Lanczos recursion with no
reorthogonalization. Eigenvalue/eigenvector computations proceed
in 2 stages. Eigenvalues must be computed first. Then a
second program LEVEC can be used to compute eigenvectors
corresponding to each of the eigenvalues in a
user-specified subset of the eigenvalues computed by LEVAL.
LEVAL calls subroutines from the set of subroutines LEMULT
and from the set of subroutines LESUB. The USPEC and CMATV
subroutines in the LEMULT file provided are samples
of matrix-specification and matrix-vector multiply subroutines.
Users may use these sample subroutines. However, in general
maximum efficiency will be achieved only when the user supplies
similar subroutines which are specialized for the particular
matrix or family of matrices being used. The main Lanczos
programs do not 'see' the user's matrix. All information about
the matrix is passed to the program as vectors of the form A*x.
These subroutines must be efficient, consistent, and accurate.
LEVEC: This is the Main Program for computing eigenvectors of a real
symmetric matrix using the Lanczos recursion used in LEVAL.
This program accepts eigenvalue
approximations computed using corresponding LEVAL program.
For each such eigenvalue supplied a corresponding
eigenvector will be computed.
LEMULT: This file contains the subroutine LANCZS which computes
the Lanczos matrices used in both LEVAL and LEVEC. It
also contains sample matrix specification subroutines
USPEC and sample matrix-vector multiply subroutines
CMATV for three sets of matrices, (1) Real, sparse,
and symmetric matrices, (2) Diagonal matrices and
(3) Poisson Matrices. The user should devise
analogous USPEC and CMATV subroutines for the particular
matrices being used. Three additional subroutines,
EXEVG, EXERR and EXVEC, are applicable only for the
Poisson test matrices and compute respectively, the
true eigenvalues of Poisson test matrices,
the corresponding
errors in the eigenvalue approximations computed
by LEVAL, and the corresponding
errors in the eigenvector approximations
computed by LEVEC.
LESUB: Contains the other subroutines used by the main
programs for the Lanczos programs with no
reorthogonalization for Real Symmetric matrices, for Hermitian
matrices, for Factored Inverses of Real Symmetric
Matrices, and for Generalized Real Symmetric Problems.
In particular these subroutines are called by
the two main programs LEVAL and LEVEC.
BISEC: Computes eigenvalues of real symmetric Lanczos
matrices by bisection
INVERR: Uses inverse iteration on real symmetric Lanczos
matrix to compute error estimates for computed
eigenvalue approximations.
TNORM: Computes scaling factors used in setting tolerances.
LUMP: 'Combines' 'good' Lanczos eigenvalues.
ISOEV: Determines isolated 'good' Lanczos eigenvalues.
PRTEST: Checks for 'hidden' eigenvalues once convergence is
achieved.
STURMI: Determines initial sizes of Lanczos matrices used
in eigenvector computations.
INVERM: Computes Lanczos eigenvectors in LEVEC.
LBISEC: Recomputes eigenvalue for eigenvector computations.
CINPRD: Computes Hermitian inner products.
LPERM: Computes permutation of vector, used in factored
versions and generalized real symmetric codes.
LECOMPAC: Optional program used to determine sparse format.
LANCZOS CODES FOR HERMITIAN MATRICES (No reorthogonalization)
HLEVAL: This is the main program for computing eigenvalues of a
Hermitian matrix using a Lanczos recursion with no
reorthogonalization. Eigenvalue/eigenvector computations proceed
in 2 stages. Eigenvalues must be computed first. Then a
second program HLEVEC can be used to compute eigenvectors
corresponding to each of the eigenvalues in a
user-specified subset of the eigenvalues computed by HLEVAL.
HLEVAL calls subroutines from the set of subroutines HLEMULT
and from the set of subroutines LESUB. The USPEC and CMATV
subroutines in the HLEMULT file provided are samples
of matrix-specification and matrix-vector multiply subroutines.
Users may use these sample subroutines. However, in general,
maximum efficiency will be achieved only when the user supplies
similar subroutines which are specialized for the particular
matrix or family of matrices being used. The main Lanczos
programs do not 'see' the user's matrix. All information about
the matrix is passed to the program as vectors of the form A*x.
CMATV computations must be efficient, consistent and accurate.
HLEVEC: This is the Main Program for computing eigenvectors of a
Hermitian matrix using a Lanczos recursion with no
reorthogonalization. Program accepts eigenvalue
approximations computed using corresponding HLEVAL program.
For each such eigenvalue supplied a corresponding
eigenvector will be computed.
HLEMULT:This file contains the subroutine LANCZS which computes
the Lanczos matrices used in both HLEVAL and HLEVEC. It
also contains sample matrix specification subroutines
USPEC and sample matrix-vector multiply subroutines
CMATV for four sets of matrices, (1) sparse and
Hermitian matrices, (2) and (3) Hermitian 'Poisson' matrices
cases I and II, and (4) Hermitian tridiagonal matrices.
The user should devise analogous subroutines specific
to the particular matrices being used. Two
additional subroutines, EXEVG and HEXVEC, are applicable
only for the 'Poisson' test matrices, case I, and
compute respectively, the true eigenvalues of
these test matrices, and the corresponding
errors in the eigenvalue approximations computed
by HLEVAL, and in the corresponding
eigenvector approximations computed by HLEVEC.
LANCZOS CODES FOR REAL, RECTANGULAR MATRICES (No reorthogonalization)
DOCUMENTATION: The file LSVALHED contains the required documentation
for the real, rectangular singular value and vector Lanczos computaions.
LSVAL: This is the main program for computing singular values of a
real, rectangular matrix using a Lanczos recursion with no
reorthogonalization. Singular value/vector computations proceed
in 2 stages. Singular values must be computed first. Then a
second program LSVEC can be used to compute singluar vectors
corresponding to each of the singular values in a
user-specified subset of the singular values computed by LSVAL.
LSVAL calls subroutines from the set of subroutines LSMULT
and from the set of subroutines LSSUB. The USPEC, STRAN and
SVMAT subroutines in the LSMULT file provided are samples,
of matrix-specification and matrix-vector multiply subroutines.
LSVAL and LSVEC use both A*x and A-transpose*y subroutines.
Users may use these sample subroutines. However, in general
maximum efficiency will be achieved only when the user supplies
similar subroutines which are specialized for the particular
matrix or family of matrices being used. The main Lanczos
programs do not 'see' the user's matrix. All information about
the matrix is passed to the program as vectors of the form A*x
and A-transpose*y and these computations must be efficient,
consistent and accurate.
LSVEC: This is the main program for computing singular vectors of a
real rectangular matrix using a Lanczos recursion with no
reorthogonalization. This program accepts singular value
approximations computed using corresponding LSVAL program.
For each such singular value supplied a corresponding
singular vector will be computed.
LSMULT: This file contains the subroutine LANCZS which computes
the Lanczos matrices used in both LSVAL and LSVEC. It
also contains sample matrix specification subroutines
USPEC and sample matrix-vector multiply subroutines
STRAN and SVMAT for two sets of matrices, (1) Real, sparse,
and rectangular matrices and (2) Diagonal matrices.
The user should devise analogous subroutines specific
to the particular matrix being used.
LSSUB: Contains the other subroutines used by the main
programs for the singular value/vector Lanczos
codes with no reorthogonalization. These subroutines
are called by the two main programs LSVAL and LSVEC.
BISEC: Computes eigenvalues of real symmetric Lanczos
matrices by bisection
INVERR: Uses inverse iteration on real symmetric Lanczos
matrix to compute error estimates for computed
eigenvalue approximations.
TNORM: Computes scaling factors used in setting tolerances.
LUMP: 'Combines' 'good' Lanczos eigenvalues.
ISOEV: Determines isolated 'good' Lanczos eigenvalues.
PRTEST: Checks for 'hidden' singular values once convergence
is achieved.
STURMI: Determines initial sizes of Lanczos matrices used
in singular vector computations.
INVERM: Computes Lanczos eigenvectors in LEVEC.
LBISEC: Recomputes singular value for singular vector
computations.
LSCOMPAC: Optional program used to determine sparse format.