Three-level parallel J-Jacobi algorithms for Hermitian matrices. (English) Zbl 1244.65055
Summary: The paper describes several efficient parallel implementations of the one-sided hyperbolic Jacobi-type algorithm for computing eigenvalues and eigenvectors of Hermitian matrices. By appropriate blocking of the algorithms an almost ideal load balancing between all available processors/cores is obtained. A similar blocking technique can be used to exploit local cache memory of each processor to further speed up the process. Due to diversity of modern computer architectures, each of the algorithms described here may be the method of choice for a particular hardware and a given matrix size. All proposed block algorithms compute the eigenvalues with relative accuracy similar to the original non-blocked Jacobi algorithm.
MSC:
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
| 65Y05 | Parallel numerical computation |
| 65Y20 | Complexity and performance of numerical algorithms |
Keywords:
Hermitian matrices; eigenvalues; Jacobi algorithm; block strategies; efficiency; parallel computation; numerical examples; algorithm; eigenvectorSoftware:
mctoolboxReferences:
| [1] | P. Arbenz, I. Slapničar, An analysis of parallel implementations of the block-Jacobi algorithm for computing the SVD, in: D. Kalpić, V. Hljuz Dobri ć (Eds.), Proceedings of the 17th International Conference on Information Technology Interfaces ITI’95, Pula, Croatia, June 13-16, 1995, pp. 343-348.; P. Arbenz, I. Slapničar, An analysis of parallel implementations of the block-Jacobi algorithm for computing the SVD, in: D. Kalpić, V. Hljuz Dobri ć (Eds.), Proceedings of the 17th International Conference on Information Technology Interfaces ITI’95, Pula, Croatia, June 13-16, 1995, pp. 343-348. |
| [2] | Bečka, M.; Okša, G.; Vajteršic, M., Dynamic ordering for a parallel block-Jacobi SVD algorithm, Parallel Comput., 28, 243-262 (2002) · Zbl 0983.68251 |
| [3] | Bojanczyk, A. W.; Onn, R.; Steinhardt, A. O., Existence of the hyperbolic singular value decomposition, Linear Algebra Appl., 185, 21-30 (1993) · Zbl 0778.15005 |
| [4] | Brent, R. P.; Luk, F. T., The solution of singular-value and symmetric eigenvalue problems on multiprocessor arrays, SIAM J. Sci. Statist. Comput., 6, 1, 69-84 (1985) · Zbl 0575.65027 |
| [5] | Bunch, J. R.; Kaufman, L. C.; Parlett, B. N., Decomposition of a symmetric matrix, Numer. Math., 27, 1, 95-109 (1976) · Zbl 0342.65026 |
| [6] | 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 |
| [7] | Demmel, J. W.; Veselić, K., Jacobi’s method is more accurate than QR, SIAM J. Matrix Anal. Appl., 13, 4, 1204-1245 (1992) · Zbl 0759.65011 |
| [8] | Dopico, F. M.; Koev, P.; Molera, J. M., Implicit standard Jacobi gives high relative accuracy, Numer. Math., 113, 519-553 (2009) · Zbl 1223.65025 |
| [9] | Drmač, Z.; Hari, V., On quadratic convergence bounds for the \(J\)-symmetric Jacobi method, Numer. Math., 64, 1, 147-180 (1993) · Zbl 0761.65026 |
| [10] | Eberlein, P. J., A one-sided Jacobi methods for parallel computation, SIAM J. Alg. Disc. Methods, 8, 4, 790-796 (1987) · Zbl 0653.65026 |
| [11] | Hansen, E. R., On cyclic Jacobi methods, SIAM J., 11, 2, 448-459 (1963) · Zbl 0118.12201 |
| [12] | Hari, V., Accelerating the SVD block-Jacobi method, Computing, 75, 27-53 (2005) · Zbl 1079.65046 |
| [13] | V. Hari, Convergence to diagonal form of block Jacobi-type methods, preprint, Faculty of Science, Department of Mathematics, University of Zagreb, submitted for publication.; V. Hari, Convergence to diagonal form of block Jacobi-type methods, preprint, Faculty of Science, Department of Mathematics, University of Zagreb, submitted for publication. · Zbl 1326.65046 |
| [14] | Hari, V.; Singer, S.; Singer, S., Block-oriented \(J\)-Jacobi methods for Hermitian matrices, Linear Algebra Appl., 433, 8-10, 1491-1512 (2010) · Zbl 1205.65152 |
| [15] | V. Hari, S. Singer, S. Singer, Full block \(J\); V. Hari, S. Singer, S. Singer, Full block \(J\) |
| [16] | Higham, N. J., Accuracy and Stability of Numerical Algorithms (2002), SIAM: SIAM Philadelphia · Zbl 1011.65010 |
| [17] | Luk, F. T.; Park, H., On parallel Jacobi orderings, SIAM J. Sci. Statist. Comput., 10, 1, 18-26 (1987) · Zbl 0666.65031 |
| [18] | Luk, F. T.; Park, H., A proof of convergence for two parallel Jacobi SVD algorithms, IEEE Trans. Comput., 38, 6, 806-811 (1989) · Zbl 1396.65088 |
| [19] | Okša, G.; Vajteršic, M., Efficient pre-processing in the parallel block-Jacobi SVD algorithm, Parallel Comput., 32, 2, 166-176 (2006) |
| [20] | Parlett, B. N., The symmetric eigenvalue problem, Classics in Applied Mathematics, vol. 20 (1998), SIAM: SIAM Philadelphia · Zbl 0885.65039 |
| [21] | Royo, D.; Velero-Garcı´a, M.; González, A., Implementing the one-sided Jacobi method on a 2D/3D mesh multicomputer, Parallel Comput., 27, 1253-1271 (2001) · Zbl 0971.68216 |
| [22] | Rutishauser, H., Lectures on Numerical Mathematics (1990), Birkhäuser: Birkhäuser Boston · Zbl 0699.65002 |
| [23] | Shroff, G.; Schreiber, R. S., On the convergence of the cyclic Jacobi method for parallel block orderings, SIAM J. Matrix Anal. Appl., 10, 3, 326-346 (1989) · Zbl 0683.65021 |
| [24] | S. Singer, Computing the eigendecomposition of a positive definite matrix, Master’s thesis, Faculty of Science, Department of Mathematics, University of Zagreb, 1993, (in Croatian).; S. Singer, Computing the eigendecomposition of a positive definite matrix, Master’s thesis, Faculty of Science, Department of Mathematics, University of Zagreb, 1993, (in Croatian). |
| [25] | Singer, S., Indefinite QR factorization, BIT, 46, 1, 141-161 (2006) · Zbl 1093.65029 |
| [26] | Singer, S.; Singer, S., Rounding-error and perturbation bounds for the indefinite QR factorization, Linear Algebra Appl., 309, 1-3, 103-119 (2000) · Zbl 0948.65042 |
| [27] | I. Slapničar, Accurate symmetric eigenreduction by a Jacobi method, Ph.D. thesis, FernUniversität-Gesamthochschule, Hagen, 1992.; I. Slapničar, Accurate symmetric eigenreduction by a Jacobi method, Ph.D. thesis, FernUniversität-Gesamthochschule, Hagen, 1992. · Zbl 0768.65011 |
| [28] | Slapničar, I., Componentwise analysis of direct factorization of real symmetric and Hermitian matrices, Linear Algebra Appl., 272, 227-275 (1998) · Zbl 0894.65009 |
| [29] | Slapničar, I., Highly accurate symmetric eigenvalue decomposition and hyperbolic SVD, Linear Algebra Appl., 358, 387-424 (2003) · Zbl 1030.65026 |
| [30] | van der Sluis, A., Condition numbers and equilibration of matrices, Numer. Math., 14, 1, 14-23 (1969) · Zbl 0182.48906 |
| [31] | Veselić, K., A Jacobi eigenreduction algorithm for definite matrix pairs, Numer. Math., 64, 1, 241-269 (1993) · Zbl 0805.65038 |
| [32] | Whiteside, R. A.; Ostlund, N. S.; Hibbard, P. G., A parallel Jacobi diagonalization algorithm for a loop multiple processor system, IEEE Trans. Comput. C, 33, 5, 409-413 (1984) · Zbl 0528.68017 |
| [33] | Zha, H., A note on the existence of the hyperbolic singular value decomposition, Linear Algebra Appl., 240, 199-205 (1996) · Zbl 0923.15007 |
| [34] | Zhou, B. B.; Brent, R. P., A parallel ring ordering algorithm for efficient one-sided Jacobi SVD computations, J. Parallel Distrib. Comput., 42, 1-10 (1997) · Zbl 0880.68055 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
