From CULLUMJ@IBM-SJ.ARPA Fri Feb 28 00:40:32 1986 Received: from IBM-SJ.ARPA (ibm-sj.arpa.ARPA) by anl-mcs.ARPA (4.12/4.9) id AA01682; Fri, 28 Feb 86 00:39:37 cst Date: Fri, 28 Feb 86 00:38:39 cst From: CULLUMJ@IBM-SJ.ARPA Message-Id: <8602280639.AA01682@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. LEVALIO: Listing of input and output files which must be defined for LEVAL and sample input file for LEVAL. LEVECIO: Listing of input and output files which must be defined for LEVEC and sample input file for LEVEC. 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. HLEVALIO: Listing of input and output files which must be defined for HLEVAL and sample input file for HLEVAL. HLEVECIO: Listing of input and output files which must be defined for HLEVEC and sample input file for 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. LSVALIO: Listing of input and output files which must be defined for LSVAL and sample input file for LSVAL. LSVECIO: Listing of input and output files which must be defined for LSVEC and sample input file for LSVEC.