Top

BIT Numerical Mathematics

Published in:

22-05-2018

Asymptotic quadratic convergence of the parallel block-Jacobi EVD algorithm with dynamic ordering for Hermitian matrices

Authors: Gabriel Okša, Yusaku Yamamoto, Martin Bečka, Marián Vajteršic

Published in: BIT Numerical Mathematics | Issue 4/2018

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The proof of the asymptotic quadratic convergence is provided for the parallel two-sided block-Jacobi EVD algorithm with dynamic ordering for Hermitian matrices. The discussion covers the case of well-separated eigenvalues as well as clusters of eigenvalues. Having p processors, each parallel iteration step consists of zeroing 2p off-diagonal blocks chosen by dynamic ordering with the aim to maximize the decrease of the off-diagonal Frobenius norm. Numerical experiments illustrate and confirm the developed theory.

previous article The randomized Kaczmarz method with mismatched adjoint

next article On the zero-stability of multistep methods on smooth nonuniform grids

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

Bečka, M., Vajteršic, M.: Block-Jacobi SVD algorithms for distributed memory systems I: hypercubes and rings. Parallel Algorithm Appl. 13, 265–287 (1999)MathSciNetCrossRef

Bečka, M., Okša, G., Vajteršic, M.: Dynamic ordering for a parallel block-Jacobi SVD algorithm. Parallel Comput. 28, 243–262 (2002)CrossRef

Bečka, M., Okša, G., Vajteršic, M.: New dynamic orderings for the parallel one-sided block-Jacobi SVD algorithm. Parallel Proc. Lett. (2015). https://doi.org/10.1142/S0129626415500036 MathSciNetCrossRefMATH

Demmel, J.W., Veselić, K.: Jacobi’s method is more accurate than QR. SIAM J. Matrix Anal. Appl. 13, 1204–1245 (1992)MathSciNetCrossRef

Dopico, F.M., Molera, J.M., Moro, J.: An orthogonal high relative accuracy algorithm for symmetric eigenproblem. SIAM J. Matrix Anal. Appl. 25, 301–351 (2003)MathSciNetCrossRef

Drmač, Z., Veselić, K.: New fast and accurate Jacobi SVD algorithm: I. SIAM J. Matrix Anal. Appl. 29, 1322–1342 (2007)MathSciNetCrossRef

Drmač, Z., Veselić, K.: New fast and accurate Jacobi SVD algorithm: II. SIAM J. Matrix Anal. Appl. 29, 1343–1362 (2007)MathSciNetCrossRef

Drmač, Z.: A global convergence proof for cyclic Jacobi methods with block rotations. SIAM J. Matrix Anal. Appl. 31, 1329–1350 (2010)MathSciNetCrossRef

Golub, G.H., Van Loan, C.F.: Matrix Computations, 4th edn. Johns Hopkins UP, Baltimore (2013)MATH

10.

Hari, V.: On sharp quadratic convergence bounds for the serial Jacobi methods. Numer. Math. 60, 375–406 (1991)MathSciNetCrossRef

11.

Hari, V.: Convergence to diagonal form of block Jacobi-type methods. Numer. Math. 129, 449–481 (2015)MathSciNetCrossRef

12.

Hoffman, A.J., Wielandt, H.W.: The variation of the spectrum of a normal matrix. Duke Math. J. 20, 37–39 (1953)MathSciNetCrossRef

13.

Kudo, S., Yamamoto, Y., Bečka, M., Vajteršic, M.: Performance analysis and optimization of the parallel one-sided block-Jacobi SVD algorithm with dynamic ordering and variable blocking. Concurrency and Computation: Practice and Experience (2016). https://doi.org/10.1002/cpe.4059 CrossRef

14.

Luk, F., Park, H.: On parallel Jacobi orderings. SIAM J. Sci. Stat. Comput. 10, 18–26 (1989)MathSciNetCrossRef

15.

Luk, F., Park, H.: A proof of convergence for two parallel Jacobi SVD algorithms. IEE Trans. Comp. 38, 806–811 (1989)MathSciNetCrossRef

16.

Matejaš, J., Hari, V.: Accuracy of the Kogbetliantz method for the scaled diagonally dominant triangular matrices. Appl. Math. Comput. 217, 3726–3746 (2010)MathSciNetMATH

17.

Mathias, R.: Accurate eigensystem computations by Jacobi methods. SIAM J. Matrix Anal. Appl. 16, 977–1003 (1995)MathSciNetCrossRef

18.

Okša, G., Vajteršic, M.: Efficient pre-processing in the parallel block-Jacobi SVD algorithm. Parallel Comput. 32, 166–176 (2006)MathSciNetCrossRef

19.

Okša, G., Yamamoto, Y., Vajteršic, M.: Asymptotic quadratic convergence of the serial block-Jacobi EVD algorithm for Hermitian matrices. Numer. Math. 136, 1071–1095 (2017)MathSciNetCrossRef

20.

Parlett, B.N.: The Symmetric Eigenvalue Problem. SIAM, Philadelphia (1987)MATH

21.

Sameh, A.H.: On Jacobi and Jacobi-like algorithms for parallel computer. Math. Comput. 25, 579–590 (1971)MathSciNetCrossRef

22.

Schönhage, A.: Zur Konvergenz des Jacobi-Verfahrens. Numer. Math 3, 374–380 (1961)MathSciNetCrossRef

23.

Schönhage, A.: Zur quadratischen Konvergenz des Jacobi-Verfahrens. Numer. Math. 6, 410–412 (1964)MathSciNetCrossRef

24.

Shroff, G., Schreiber, R.: On the convergence of the cyclic Jacobi method for parallel block orderings. SIAM J. Matrix Anal. Appl. 10, 326–346 (1989)MathSciNetCrossRef

25.

Yamamoto, Y., Lan, Z., Kudo, S.: Convergence analysis of the parallel classical block Jacobi method for the symmetric eigenvalue problem. J. SIAM Lett. 6, 57–60 (2014)MathSciNetCrossRef

26.

Zhou, B.B., Brent, R.P.: Jacobi-like algorithms for eigenvalue decomposition of a real normal matrix using real arithmetic. In: Proceedings of IPPS’96, the 10th International Parallel Processing Symposium, 15–19 April, Honolulu, Hawai, USA (1996)

Title: Asymptotic quadratic convergence of the parallel block-Jacobi EVD algorithm with dynamic ordering for Hermitian matrices
Authors: Gabriel Okša
Yusaku Yamamoto
Martin Bečka
Marián Vajteršic
Publication date: 22-05-2018
Publisher: Springer Netherlands
Published in: BIT Numerical Mathematics / Issue 4/2018
Print ISSN: 0006-3835
Electronic ISSN: 1572-9125
DOI: https://doi.org/10.1007/s10543-018-0711-3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 4/2018

An accelerated Poisson solver based on multidomain spectral discretization

On the spectral problem for trivariate functions

Weak convergence of Galerkin approximations for fractional elliptic stochastic PDEs with spatial white noise

Stochastic discrete Hamiltonian variational integrators

Backward error analysis of polynomial approximations for computing the action of the matrix exponential

On the zero-stability of multistep methods on smooth nonuniform grids

Premium Partner