zbMATH — the first resource for mathematics

Parallel homotopy algorithm for symmetric large sparse eigenproblems. (English) Zbl 0839.65048
The homotopy method is applied to solve the eigenproblem \(Ax= \lambda x\) for real symmetric large sparse matrices \(A\). That is, a simpler nearby matrix \(D\) is introduced and its eigenpairs are continuously mapped to those of \(A\). The problem of choosing an appropriate starting matrix \(D\) as well as regularity and bifurcation issues for \(\lambda(t)\) and \(x(t)\) are discussed. A parallel homotopy algorithm is presented and its performance is compared to that of the Lanczos algorithm.
Reviewer: W.Gander (Zürich)

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65Y05 Parallel numerical computation
65H20 Global methods, including homotopy approaches to the numerical solution of nonlinear equations
Full Text: DOI
[1] Arbenz, P.; Golub, G.H., On the spectral decomposition of Hermitian matrices modified by low rank perturbations with applications, SIAM J. matrix anal. appl., 9, 1, 40-58, (1988) · Zbl 0646.65033
[2] Bunch, J.R.; Parlett, B.N., Direct methods for solving symmetric indefinite systems of linear equations, SIAM J. numer. anal., 8, 4, 639-655, (1971) · Zbl 0199.49802
[3] Chu, E.; George, A.; Liu, J.; Ng, E., Sparspack: Waterloo sparse matrix package User’s guide for sparspack-a, ()
[4] Cullum, J.K.; Wiloughby, K.A., Lanczos algorithms for large symmetric eigenvalue computations, vol. I: theory, (1985), Birkhäuser Boston · Zbl 0574.65028
[5] Cuppen, J.J.M., A divide and conquer method for the symmetric eigenproblem, Numer. math., 36, 195-197, (1981) · Zbl 0431.65022
[6] Dongarra, J.J.; Sorensen, D.C., A fully parallel algorithm for the symmetric eigenvalue problem, SIAM J. sci. statist. comput., 8, 2, 139-154, (1987)
[7] Duff, I.S.; Erisman, A.M.; Reid, J.K., Direct methods for sparse matrices, (1986), Clarendon Press Oxford · Zbl 0604.65011
[8] Eisenstat, S.C.; Gursky, M.C.; Schultz, M.H.; Sherman, A.H., Yale sparse matrix package, 1: the symmetric codes, Internat. J. numer. methods engrg., 18, 1145-1151, (1982) · Zbl 0492.65012
[9] Fan, K., Maximum properties and inequalities for eigenvalues of completely continuous operators, (), 760-766 · Zbl 0044.11502
[10] George, A.; Liu, J.W.H., Computer solution of large sparse positive-definite systems, (1981), Prentice-Hall New York
[11] Golub, G.H.; Van Loan, C.F., Matrix computations, (1983), Johns Hopkins University Press Baltimore, MD · Zbl 0559.65011
[12] Jenson, P.S., The solution of large symmetric eigenproblems by sectioning, SIAM J. numer. anal., 9, 534-545, (1972) · Zbl 0258.65040
[13] Kato, T., Perturbation theory for linear operators, (1966), Springer New York · Zbl 0148.12601
[14] Kirkpatrick, S.; Eggarter, T.P., Localized states of a binary alloy, Phys. rev. B, 6, 3589-3600, (1972)
[15] Li, K.; Li, T.Y., An algorithm for symmetric tridiagonal eigenproblems - divide and conquer with homotopy continuation, SIAM J. sci. comput., 14, 3, 735-751, (1993) · Zbl 0790.65032
[16] Li, T.Y.; Zeng, Z.; Cong, L., Solving eigenvalue problems of real nonsymmetric matrices with real homotopies, SIAM J. numer. anal., 29, 1, 229-248, (1992) · Zbl 0749.65028
[17] Li, T.Y.; Rhee, N.H., Homotopy algorithm for symmetric eigenvalue problems, Numer. math., 55, 3, 265-280, (1989) · Zbl 0653.65025
[18] Li, T.Y.; Zeng, Z., Homotopy-determinant algorithm for solving nonsymmetric eigenvalue problems, Math. comput., 59, 200, 483-502, (1992) · Zbl 0783.65034
[19] Li, T.Y.; Zhang, H.Z.; Sun, X.H., Parallel homotopy algorithm for symmetric tridiagonal eigenvalue problem, SIAM J. sci. statist. comput., 12, 3, 155-165, (1988)
[20] Lo, S.S.; Philippe, B.; Sameh, A., A multiprocessor algorithm for the symmetric eigenvalue problem, SIAM J. sci. statist. comput., 8, 2, 155-165, (1987)
[21] Ma, S.C.; Patrick, M.L.; Szyld, D.B., A parallel, hybrid algorithm for the generalized eigenproblem, (1988), preprint
[22] Murata; Horikoshi, A new method for the tridiagonalization of the symmetric band matrix, Inform. process. in Japan, 15, 108-112, (1975) · Zbl 0335.65012
[23] Ortega, J., Numerical analysis; A second course, (1972), Academic Press New York · Zbl 0248.65001
[24] Parlett, B.N., The symmetric eigenvalue problem, (1980), Prentice-Hall Englewood Cliffs, NJ · Zbl 0431.65016
[25] Smith, B.T.; Boyle, J.M.; Dongarra, J.J.; Garbow, B.S.; Ikebe, Y.; Klema, V.C.; Moler, C.B., Matrix eigensystem routines — EISPACK guide, () · Zbl 0325.65016
[26] Szyld, D., Criteria for combining inverse and Rayleigh quotient iterations, SIAM J. numer. anal., 25, 6, 1369-1375, (1988) · Zbl 0665.65031
[27] Wilkinson, J.H., The algebraic eigenvalue problem, (1965), Oxford University Press Oxford · Zbl 0258.65037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.