Instead, we run the codes in multi-processes. The reason is that Matlab is not available for multi-threaded computation.
#Program for bisection method in fortran code do loop serial#
The parallel efficiency is unsatisfactory, especially for the 10 7 × 10 7 and 10 6 × 10 6 Random Matrices, which are even worse than the serial Bisection algorithm. Specifically, the top one denotes the time cost for 10 8 × 10 8 Random Matrices, the middle 10 7 × 10 7, and the bottom 10 6 × 10 6. The three purple horizontal lines in Figure 7 denote the time cost of the serial Bisection algorithm. However, a distance of 5 × 10 − 14 could not be detected, because it does not meet the conditions of Theorem 4. Recall that Algorithm 7 is for checking similar situations. As a consequence, more iterations are needed to guarantee convergence, which finally results in the efficiency loss of the Divisional Bisection method. The ‘fzero’ scheme uses the linear interpolation to accelerate convergence such a bound produces poor slopes during the linear interpolation process. For example, the sub-eigenvalues give an interval for Algorithm 6 and have an upper or lower bound that has a distance between λ i less than 5 × 10 − 14. The reason is their submatrices have close eigenvalues to the global one but are not equal in finite precision arithmetic.
However, the improvement is less than 50 % in Matrix A and Matrix T2. Such a good result can also be in Matrix T1 and Matrix T3. When the eigenvalues clutter, as in Matrix W, the Divisional Bisection method improves the Bisection method by about 70 %. The machine precision is e p s ≈ 2.2 × 10 − 16. All codes were written in Matlab2017b and executed in IEEE double precision. The data were collected on an Intel Core i5-4590 3.3 GHz CPU and 16 GB RAM machine. The errors in Table 1 refer to the difference between s ¯ i values selected during deflations and λ ¯ i values obtained by the Bisection method. It can be seen that the hit rate and accuracy of our method are acceptable or at least no worse than the DC algorithm. In Table 1, the plan 1 refers to “rough discriminant + Inverse Iteration algorithm”, the plan 2 refer to “rough discriminant + Algorithm 1”, and the hit rates of them were collected similarly. We collected the hit rate of the DC algorithm by checking how many s ¯ i values, which had negligible corresponding v i k values, were really close to λ i values. The averages were calculated and are shown in Table 1. We applied these methods to 20 randomly generated 2001 × 2001 matrices for computation, where T 1 and T 2 are both 1000 × 1000 matrices. Even filtrating directly by | v i k |, as in the DC algorithm, would still leave some out. We have found in our numerical experiments that it is difficult to cover all the deflation situations by this method, even if we set the discriminant quite loosely. Our scheme is to mark those suspicious small | 1 / q i T 1 | values by a rough discriminant, for example | 1 / q i T 1 | < 1, then to substitute the corresponding s ¯ i ± t o l values into Algorithm 1 to check if deflation is available. As a consequence, the order of eigenvalue convergence is not manageable. In detail, both QR and DQDS algorithms use a designed shift, for example, Wilkinson’s shift, to obtain a high-order asymptotic convergence rate. The MRRR algorithm has a similar disadvantage as it is based on the DQDS algorithm to compute the eigenvalues. One more essential trouble is that the QR algorithm is unsuitable for computing one or several selected eigenvalues. However, few seem adequate for the symmetric tridiagonal matrices because most of those attempts are for dense matrices. Many researchers have made attempts, such as blocking the given matrix , look-ahead strategies , load-balancing schemes , pipelining of iterations , or dimensional analysis . However, the parallelization of the QR algorithm is a problem, in this case, requiring more than a straightforward transcription of serial code to parallel code. This was first observed by Ortega and Kaiser in 1963 and a fast, stable algorithm was developed by Pal, Walker, and Kahan (PWK) in 1969 . When only eigenvalues are desired, all square roots can be eliminated in the QR transformation. The most popular algorithm at present for a symmetric eigenproblem is the QR algorithm because of its stability and computational efficiency .
0 kommentar(er)
