Font Size: a A A

Parallel Computing The Matrice Generalized Eigenvalue Under Distributed Memory Environments

Posted on:2003-11-24Degree:DoctorType:Dissertation
Country:ChinaCandidate:L F WeiFull Text:PDF
GTID:1118360092998846Subject:Computer Science and Technology
Abstract/Summary:PDF Full Text Request
Generalized eigenvalue problem of matrix pair is an active research task. It plays a very important role in many application, according to the point of mathematics point, its mostly application originate from equations of mathematical physics, difference equations, Markov process, and so on, its purpose is to solve the problems of solid, fluid, electromagnetic, microscopic particles, system control, and etc. In practical science research and engineer applications, such as, architecture project, research of aeronautics and astronautics, bioscience, computing physics and oil reconnoiter, many large scale generalized eigenvalue problems need to be solved.Massively Parallel Processing system (MPP) and PC cluster provide distributed-memory environments for parallel solving the generalized eigenvalue problem. This thesis investigates parallel solving the generalized eigenvalue problem Ax- Bx deeply, and proposes some new algorithms. The main productions are summarized as follows:(1) The symmetric-definite tridiagonal generalized eigenvalue problemsi) A divide-and-conquer algorithm is proposed. The original problem is divided into two subproblems, and the sum of the subproblem's scales is equal to the original problem's scale. The generalized eigenvalues are computed by secant iteration. The advantage of this algorithm is that its computing quantity and computing time are less than the divide-and-conquer algorithm of K.Y. Li. With good parallelism in nature, it is quite suitable for parallel processing. Theoretical analysis and numerical experiments show that this algorithm is faster than the divide-and-conquer of K.Y. Li. About 10%-20% computing time is lessen when the problem's scale is large enough. The speedup satisfy: Sp - p as n - .Good linear speedup and stable efficiency can be achieved under distributed-memory environments.ii) A divide-and-conquer algorithm /with new dividing strategy is proposed. In this new dividing strategy, the sum of the subproblem's scales is equal to the original problem's scale minus 1. An eigenvalue interlacing theorem is given and proved. The interval including every eigenvalue provided by this dividing strategy is better than that provided by the first dividing strategy, with same iterative method, this algorithm has the advantage of less computing quantity and time. About 30% or more computing time is lessen when the problem's scale is large enough. Thisalgorithm has good parallelism in nature, the speedup satisfy: Sp - p as n - .Good linear speedup and stable efficiency can be achieved under distributed-memory environments. (2) The symmetric-definite band generalized eigenvalue problemsi) A parallel divide-and-conquer algorithm combined with multisection method is proposed, the sum of the subproblem's scales is equal to the original problem's scale. An eigenvalue interlacing theorem is given and proved. Each eigenpair is computed by bisection and generalized Rayleigh quotient iteration. For computing all eigenvalues and eigenvectors is O(n2r2), it is less than O(n3), which is the computational complexity of LAPACK, when r n. This divide-and-conquer algorithm is combined with multisection method when it's implemented under distributed environment, high speedup and efficiency can be achieved, ii) A parallel divide-and-conquer algorithm combined with multisection method is proposed, the sum of the subproblem's scales is equal to the original problem's scale minus r, where r is semi-bandwidth. For computing all eigenvalues and eigenvectors is O(玍2). The computing time of this algorithm mostly is less than that of the former algorithm. Combined with multisection method, this divide-and-conquer algorithm has high parallelism, and high speedup and efficiency can be achieved under distributed environments.iii) A parallel homotopy continuation algorithm based on divide-and-conquer is proposed. Efficiency of algorithm is improved by restricting step size and giving up eigenvalue's clusters, the computing ti...
Keywords/Search Tags:generalized eigenvalue problem, parallel algorithm, divide-and-conquer algorithm, homotopy continuation, positive definite, symmetric-definite, symmetric tridiagonal, symmetric band, nonsymmetric
PDF Full Text Request
Related items