nach oben

Calcolo

Erschienen in:

01.06.2021

On the global convergence of the block Jacobi method for the positive definite generalized eigenvalue problem

verfasst von: Vjeran Hari

Erschienen in: Calcolo | Ausgabe 2/2021

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The paper proves the global convergence of a general block Jacobi method for the generalized eigenvalue problem \(\mathbf {A}x=\lambda \mathbf {B}x\) with symmetric matrices \(\mathbf {A}\), \(\mathbf {B}\) such that \(\mathbf {B}\) is positive definite. The proof is made for a large class of generalized serial strategies that includes important serial and parallel strategies. The sequence of matrix pairs generated by the block method converges to \((\varvec{\varLambda } , \mathbf {I})\) where \(\varvec{\varLambda }\) is a diagonal matrix of the eigenvalues of the initial matrix pair \((\mathbf {A},\mathbf {B})\) and \(\mathbf {I}\) is the identity matrix. First, the convergence to diagonal form is proved. After that several conditions are imposed to ensure the global convergence of the block method.

Vorheriger Artikel Error control for statistical solutions of hyperbolic systems of conservation laws

Nächster Artikel Lidstone–Euler interpolation and related high even order boundary value problem

Hari, V., Begović Kovač, E.: Convergence of the cyclic and quasi-cyclic block Jacobi methods. Electron. Trans. Numer. Anal. 46, 107–147 (2017)MathSciNetMATH

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

Slapničar, I.: Accurate symmetric eigenreduction by a Jacobi method. Ph.D. thesis, University of Hagen (1992)

Drmač, Z.: Implementation of Jacobi rotations for accurate singular value computation in floating-point arithmetic. SIAM J. Sci. Stat. Comp. 18(4), 1200–1222 (1997)MathSciNetCrossRef

Demmel, W.J., Gu, M., Eisenstat, S., Slapničar, I., Veselić, K., Drmač, Z.: Computing the singular value decomposition with high relative accuracy. Linear Algebra Appl. 299, 21–80 (1999)MathSciNetCrossRef

Slapničar, I.: Highly accurate symmetric eigenvalue decomposition and hyperbolic SVD. Linear Algebra Appl. 358, 387–424 (2002)MathSciNetCrossRef

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

Matejaš, J.: Accuracy of the Jacobi method on scaled diagonally dominant symmetric matrices. SIAM J. Matrix Anal. Appl. 31(1), 133–153 (2009)MathSciNetCrossRef

Matejaš, J., Hari, V.: On high relative accuracy of the Kogbetliantz method. Linear Algebra Appl. 464, 100–129 (2015)MathSciNetCrossRef

10.

Hari, V.: Globally convergent Jacobi methods for positive definite matrix pairs. Numer. Algor. 79(1), 221–249 (2018). https://doi.org/10.1007/s11075-017-0435-5MathSciNetCrossRefMATH

11.

de Rijk, P.P.M.: A one-sided Jacobi algorithm for computing the singular-value decomposition on a vector computer. SIAM J. Sci. Stat. Comp. 10(2), 359–371 (1989)MathSciNetCrossRef

12.

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

13.

Hari, V., Veselić, K.: On Jacobi methods for singular value decompositions. SIAM J. Sci. Stat. Comput. 8(5), 741–754 (1987)MathSciNetCrossRef

14.

Eberlein, P.J., Park, H.: Efficient implementation of Jacobi algorithms and Jacobi sets on distributed memory architectures. J. Parallel Distrib. Comput. 8, 358–366 (1990)CrossRef

15.

Hari, V., Zadelj-Martić, V.: Parallelizing the Kogbetliantz method: a first attempt. JNAIAM 2(1–2), 49–66 (2007)MathSciNetMATH

16.

Drmač, Z.: A posteriori computation of the singular vectors in a preconditioned Jacobi SVD algorithm. IMA J. Numer. Anal. 19, 191–213 (1999)MathSciNetCrossRef

17.

Hari, V.: Accelerating the SVD block-Jacobi method. Computing 75, 27–53 (2005)MathSciNetCrossRef

18.

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

19.

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

20.

Bečka, M., Okša, G., Vajtersic, M.: Parallel Block-Jacobi SVD Methods. In: Berry, M., et al. (eds.) High-Performance Scientific Computing, pp. 185–197. Springer, London (2012)CrossRef

21.

Bečka, M., Okša, G., Vajtersic, M.: New dynamic orderings for the parallel one-sided block-Jacobi SVD algorithm. Parallel Process. Lett. 25(2), 1–19 (2015)MathSciNetCrossRef

22.

Novaković, J., Singer, S., Singer, S.: Blocking and parallelization of the Hari-Zimmermann variant of the Falk-Langemeyer algorithm for the generalized SVD. Parallel Comput. 49, 136–152 (2015)MathSciNetCrossRef

23.

Novaković, J., Singer, S.: Implicit Hari-Zimmermann algorithm for the generalized SVD on the GPUs. Int. J. High. Perform. Comput. Appl. 35(2), 170–205 (2021). https://doi.org/10.1177/1094342020972772CrossRef

24.

Singer, S., Di Napoli, E., Novaković, V., Čaklović, G.: The LAPW method with eigendecomposition based on the Hari-Zimmermann generalized hyperbolic SVD. SIAM J. Sci. Comput. 42(5), C265–C293 (2020). https://doi.org/10.1137/19M1277813MathSciNetCrossRefMATH

25.

Hari, V.: Convergence of a block-oriented quasi-cyclic Jacobi method. SIAM J. Matrix Anal. Appl. 29(2), 349–369 (2007)MathSciNetCrossRef

26.

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

27.

Hari, V., Singer, S., Singer, S.: Block-oriented \(J\)-Jacobi methods for hermitian matrices. Lin. Alg. and Its Appl. 433(8–10), 1491–1512 (2010)MathSciNetCrossRef

28.

Bujanović, Z.: Drmač, Z: A contribution to the theory and practice of the block Kogbetliantz method for computing the SVD. BIT 52(4), 827–849 (2012)MathSciNetCrossRef

29.

Hari, V., Singer, S., Singer, S.: Full block \(J\)-Jacobi method for hermitian matrices. Linear Algebra Appl. 444, 1–27 (2014)MathSciNetCrossRef

30.

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

31.

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

32.

Hansen, E.R.: On cyclic Jacobi methods. SIAM J. Appl. Math. 11, 449–459 (1963)MathSciNetCrossRef

33.

Luk, F., Park, H.: On the equivalence and convergence of parallel Jacobi SVD algorithms. IEEE Tran. Comp. 38(6), 806–811 (1989)CrossRef

34.

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

35.

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

36.

van der Sluis, A.: Condition numbers and equilibration of matrices. Numer. Math. 14(1), 14–23 (1969)MathSciNetCrossRef

37.

Drmač, Z.: A Tangent Algorithm for Computing the Generalized Singular Value Decomposition. SIAM J. Numer. Anal. 35(5), 1804–1832 (1998)MathSciNetCrossRef

38.

Falk, S., Langemeyer, P.: Das Jacobische Rotations-Verfahren für reel symmetrische Matrizen-Paare I. II. Elektronische Datenverarbeitung 7, 30–34 (1960)MATH

39.

Slapničar, I., Hari, V.: On the quadratic convergence of the Falk-Langemeyer method for definite matrix pairs. SIAM J. Matrix Anal. Appl. 12(1), 84–114 (1991)MathSciNetCrossRef

40.

Forsythe, G.E., Henrici, P.: The cyclic Jacobi method for computing the principal values of a complex matrix. Trans. Am. Math. Soc. 94, 1–23 (1960)MathSciNetCrossRef

41.

Eberlein, P.J.: A Jacobi method for automatic computation of eigenvalues and eigenvectors of an arbitrary matrix. Siam J. 10, 74–88 (1962)MathSciNetMATH

42.

Eberlein, P.J., Boothroyd, J.: Solution to the eigenproblem by a norm-reducing Jacobi-type method. Numer. Math. 11, 1–12 (1968)CrossRef

43.

Hari, V., Begović Kovač, E.: On the convergence of complex Jacobi methods. Linear Multilinear Algebra 69(3), 489–514 (2019). https://doi.org/10.1080/03081087.2019.1604622MathSciNetCrossRefMATH

44.

Hari, V.: On pairs of almost diagonal matrices. Linear Algebra Appl. 148, 193–223 (1991)MathSciNetCrossRef

45.

Hari, V.: On cyclic Jacobi methods for the positive definite generalized eigenvalue problem. Ph.D. thesis, University of Hagen (1984)

46.

Mascarenhas, W.: On the convergence of the Jacobi method for arbitrary orderings. SIAM J. Matrix Anal. Appl. 16(4), 1197–1206 (1995)MathSciNetCrossRef

47.

Hari, V.: On the global convergence of the complex HZ method. SIAM J. Matrix Anal. Appl. 40(4), 1291–1310 (2019). https://doi.org/10.1137/19M1265594

48.

Hari, V.: Complex Cholesky–Jacobi algorithm for PGEP. AIP Conf. Proc. 2116, 450011 (2019). https://doi.org/10.1063/1.5114478CrossRef

Titel: On the global convergence of the block Jacobi method for the positive definite generalized eigenvalue problem
verfasst von: Vjeran Hari
Publikationsdatum: 01.06.2021
Verlag: Springer International Publishing
Erschienen in: Calcolo / Ausgabe 2/2021
Print ISSN: 0008-0624
Elektronische ISSN: 1126-5434
DOI: https://doi.org/10.1007/s10092-021-00415-8

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 2/2021

Second-order finite difference approximation for a nonlinear size-structured population model with an indefinite growth rate coupled with the environment

Superconvergence of the space-time discontinuous Galerkin method for linear nonhomogeneous hyperbolic equations

Unified compact numerical quadrature formulas for Hadamard finite parts of singular integrals of periodic functions

Pressure-robust error estimate of optimal order for the Stokes equations: domains with re-entrant edges and anisotropic mesh grading

Spectral collocation method for nonlinear Riemann–Liouville fractional differential system

Lopsided scaled HSS preconditioner for steady-state space-fractional diffusion equations