Efficient Scheme for Computing the k-th Eigenvalue
Date Issued
2014
Date
2014
Author(s)
Xia, You-Huai
Abstract
In some applications of physics problems, we may want to know certain eigenvalues we''re interested in. Here our target is an arbitrarily chosen k-th eigenvalue of a generalized eigenvalue problems.
According to the Sylvester''s law of inertia in Linear algebra, we may get the eigenvalue counts before an arbitrarily given number via $LDL^T$ decomposition. If we view the eigenvalue counts before a given number as a step function f, then our problem of finding the k-th eigenvalue can be transformed into a root-finding problem ( solving $f(x)=k$ for x ). As far as our problem concerned, our goals is to find a real value $s$ such that $f(s)=k$ or $f(s)=k-1$ so that we can find the exact k-th eigenvalue by an shift-invert eigenvalue solver. In this paper, we do not emphasize the choice of a specific eigenvalue solver, but focus on developing the root-finding algorithm and introduce an approximating method which can reduce time consuming relative to $LDL^T$ decomposition.
In the literature, the Bisection method is an existing stable root-finding algorithm which can be applied to step functions. Here we will first extend the Bisection method to the Multiple-section method which can be naturally parallelized. We will also developed a sequential method based on piecewise Monotone cubic interpolation and then combine it with Multiple-section method to get a parallel algorithm. With the same number of MPI processes, it can reduce the total number of function evaluations for one time root-solving in most cases relative to the pure Multiple-section method.
On the other hand, besides computing the exact function value via $LDL^T$ decomposition, we also
took a stochastic scheme for estimating the eigenvalue counts as an alternative to achieve the aim for reducing the time consuming for one-time function evaluation. The result of numerical experiment shows that in the case of large sparse matrix, we can save function evaluation time by sacrificing some exactness of function value.
Subjects
廣義特徵值問題
特徵值估計
特徵值個數估計
分段單調三次插值
西爾維斯特慣性定理
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-103-R00221024-1.pdf
Size
23.54 KB
Format
Adobe PDF
Checksum
(MD5):d7e7a81ee1a08676aa4a6cef22c3d05b