More Web Proxy on the site http://driver.im/

article

Convergence to diagonal form of block Jacobi-type methods

Author:

Vjeran HariAuthors Info & Claims

Numerische Mathematik, Volume 129, Issue 3

Pages 449 - 481

https://doi.org/10.1007/s00211-014-0647-8

Published: 01 March 2015 Publication History

Abstract

We provide sufficient conditions for the general sequential block Jacobi-type method to converge to the diagonal form for cyclic pivot strategies which are weakly equivalent to the column-cyclic strategy. Given a block-matrix partition $$(A_{ij})$$ ( A i j ) of a square matrix $$\mathbf {A}$$ A , the paper analyzes the iterative process of the form $$\mathbf {A}^{(k+1)} = [\mathbf {P}^{(k)}]^*\,\mathbf {A}^{(k)}\,\mathbf {Q}^{(k)}$$ A ( k + 1 ) = [ P ( k ) ] A ( k ) Q ( k ) , $$k\ge 0$$ k 0 , $$\mathbf {A}^{(0)}=\mathbf {A}$$ A ( 0 ) = A , where $$\mathbf {P}^{(k)}$$ P ( k ) and $$\mathbf {Q}^{(k)}$$ Q ( k ) are elementary block matrices which differ from the identity matrix in four blocks, two diagonal and the two corresponding off-diagonal blocks. In our analysis of convergence a promising new tool is used, namely, the theory of block Jacobi operators. Typical applications lie in proving the global convergence of block Jacobi-type methods for solving standard and generalized eigenvalue and singular value problems.

References

[1]

Bujanović, Z., Drmaă¿, Z.: A contribution to the theory and practise of the block Kogbetliantz method for computing the SVD. BIT Numer. Math. 52(4), 827---849 (2012)

[2]

Chandrasekaran, S., Ipsen, I.: On rank-revealing QR factorizations. SIAM J. Matrix Anal. Appl. 15, 592---622 (1994)

Digital Library

[3]

Charlier, J.P., Vanbegin, M.P., Van Dooren, P.: On efficient implementation of Kogbetliantz's algorithm for computing the singular value decomposition. Numer. Math. 52, 279---300 (1988)

[4]

Demmel, J.W.: Applied numerical linear algebra. SIAM, Philadelpia (1997)

[5]

Demmel, J.W., Veselić, K.: Jacobi's method is more accurate than QR. SIAM J. Math. Anal. Appl. 13, 1204---1245 (1992)

Digital Library

[6]

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)

[7]

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

Digital Library

[8]

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

Digital Library

[9]

Dopico, F.M., Koev, P., Molera, J.M.: Implicit standard Jacobi gives high relative accuracy. Numer. Math. 113(2), 519---553 (2009)

Digital Library

[10]

Drmaă¿, Z., Veselić, K.: New fast and accurate Jacobi SVD algorithm I. SIAM J. Math. Anal. Appl. 29(4), 1322---1342 (2008)

Digital Library

[11]

Drmaă¿, Z., Veselić, K.: New fast and accurate Jacobi SVD algorithm II. SIAM J. Math. Anal. Appl. 29(4), 1343---1362 (2008)

Digital Library

[12]

Drmaă¿, Z.: A global convergence proof of cyclic Jacobi methods with block rotations. SIAM J. Math. Anal. Appl. 31(3), 1329---1350 (2009)

[13]

Eberlein, P.J.: A Jacobi-like method for the automatic computation of eigenvalues and eigenvectors of an arbitrary matrix. J. Soc. Ind. Appl. Math. 10(1), 74---88 (1962)

[14]

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

Digital Library

[15]

Eberlein, P.J., Park, H.: Efficient implementation of Jacobi algorithms and Jacobi sets on distributed memory architectures. Special issue on algorithms for hypercube computers. J. Parallel Distrib. Comput. 8, 358---366 (1990)

Digital Library

[16]

Falk, S., Langemeyer, P.: Das Jacobische Rotations-Verfahren für reelsymmetrische Matrizen-Paare I, II. Elektronische Datenverarbeitung 30---43 (1960)

[17]

Fernando, K.V.: Linear convergence of the row cyclic Jacobi and Kogbetliantz methods. Numer. Math. 56, 73---94 (1989)

Digital Library

[18]

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)

[19]

Gu, M., Eisenstat, S.C.: Efficient algorithms for computing a strong rank-revealing QR factorizations. SIAM J. Sci. Comput. 17(4), 848---869 (1996)

Digital Library

[20]

Hansen, E.R.: On Jacobi methods and block Jacobi methods for computing matrix Eigenvalues. Ph.D. thesis, Stanford University (1960)

[21]

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

[22]

Hari, V.: On the global convergence of Eberlein method for real matrices. Numer. Math. 39, 361---369 (1982)

Digital Library

[23]

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

[24]

Hari, V.: On the convergence of certain cyclic Jacobi-like norm-reducing processes for real matrices. Radovi Matem. 1, 121---147 (1985)

[25]

Hari, V.: On the convergence of cyclic Jacobi-like processes. Linear Algebra Appl. 81, 105---127 (1986)

[26]

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

[27]

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

Digital Library

[28]

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

Digital Library

[29]

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

Digital Library

[30]

Hari, V., Matejaš, J.: Accuracy of two SVD algorithms for $$2\times 2$$2×2 triangular matrices. Appl. Math. Comput. 210(1), 232---257 (2009)

Digital Library

[31]

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

[32]

Hari, V.: On block Jacobi annihilators. Proc. Algoritm. 2009, 1---13 (2009)

[33]

Hari, V., Singer, S., Singer, S.: Block-oriented J-Jacobi methods for Hermitian matrices. Linear Algebra Appl. 433(8---10), 1491---1512 (2010)

[34]

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

[35]

Henrici, P., Zimmermann, K.: An estimate for the norms of certain cyclic Jacobi operators. Linear Algebra Appl. 1, 289---501 (1968)

[36]

Hestenes, M.R.: Inversion of Matrices by Biorthonalization and Related Results. J. SIAM 6(1), 51---90 (1958)

[37]

Kogbetliantz, E.: Diagonalization of general complex matrices as a new method for solution of linear equations. Proc. Int. Congr. Math. Amsterdam 2, 356---357 (1954)

[38]

Kogbetliantz, E.: Solutions of linear equations by diagonalization of coefficient matrices. Q. Appl. Math. 13, 123---132 (1955)

[39]

Luk, F., Park, H.: On the equivalence and convergence of parallel Jacobi SVD algorithms. IEEE Trans. Comput. 38(6), 806---811 (1989)

Digital Library

[40]

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

[41]

Mascarenhas, W.F.: On the convergence of the Jacobi method for arbitrary orderings. SIAM J. Matrix Anal. Appl. 16, 1197---1209 (1995)

Digital Library

[42]

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

Digital Library

[43]

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

[44]

Mathias, R.: Accurate eigensystem computations by Jacobi methods. SIAM J. Math. Anal. Appl. 16(3), 977---1003 (1995)

Digital Library

[45]

Nazareth, L.: On the convergence of the cyclic Jacobi method. Linear Algebra Appl. 12(2), 151---164 (1975)

[46]

Novaković, V., Singer, S.: A GPU-based hyperbolic SVD algorithm. BIT Numer. Math. 51(4), 1009---1030 (2011)

[47]

Pupovci, D., Hari, V.: On the convergence of parallelized Eberlein methods. Radovi Matem. 8, 249---267 (1999)

[48]

Rhee, H.N., Hari, V.: On the global and cubic convergence of a quasi-cyclic Jacobi method. Numer. Math. 66, 97---122 (1993)

Digital Library

[49]

Rutishauser, H.: Une mthode pour le calcul des valeurs propres des matrices non symtriques. Comptes Rendus 259, 2758---2758 (1964)

[50]

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

[51]

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)

Digital Library

[52]

Singer, S., Singer, S., Novaković, V., Davidović, D., Bokulić, K., Ušćumlić, A.: Three-level parallel J-Jacobi algorithms for Hermitian matrices. Appl. Math. Comput. 218(9), 5704---5725 (2012)

[53]

Singer, S., Singer, S., Novaković, V., Ušćumlić, A., Dunjko, V.: Novel modifications of parallel Jacobi algorithms. Numer. Algorithm 59(1), 1---27 (2012)

Digital Library

[54]

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

[55]

Slapniă¿ar, I.: Highly accurate symmetric eigenvalue decomposition and hyperbolic SVD. Linear Algebra Appl. 358, 387---424 (2002)

[56]

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

Digital Library

[57]

Veselić, K., Hari, V.: A note on a one-sided Jacobi algorithm. Numer. Math. 56, 627---633 (1989)

Digital Library

[58]

Veselić, K.: A Jacobi Eigenreduction Algorithm for Definite Matrix Pairs. Numer. Math. 64(1), 241---269 (1993)

Digital Library

[59]

Voevodin, V.V.: Cislennye metody linejnoj algebry. Nauka, Moscow (1966)

[60]

Zimmermann, K.: On the convergence of the Jacobi process for ordinary and generalized eigenvalue problems. Ph.D. Thesis, Dissertation No. 4305 ETH, Zürich (1965)

Cited By

Hari V(2021)On the global convergence of the block Jacobi method for the positive definite generalized eigenvalue problemCalcolo: a quarterly on numerical analysis and theory of computation10.1007/s10092-021-00415-858:2Online publication date: 9-May-2021
https://dl.acm.org/doi/10.1007/s10092-021-00415-8
Hari V(2019)On the complex Falk–Langemeyer methodNumerical Algorithms10.1007/s11075-019-00689-883:2(451-483)Online publication date: 2-Apr-2019
https://dl.acm.org/doi/10.1007/s11075-019-00689-8
Hari V(2018)Globally convergent Jacobi methods for positive definite matrix pairsNumerical Algorithms10.1007/s11075-017-0435-579:1(221-249)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1007/s11075-017-0435-5
Show More Cited By

Recommendations

Global convergence of the restarted Lanczos and Jacobi---Davidson methods for symmetric eigenvalue problems

The Lanczos method is well known for computing the extremal eigenvalues of symmetric matrices. For efficiency and robustness a restart strategy is employed in practice, but this makes an analysis of convergence less straightforward. We prove global ...
Convergence to Singular Triplets in the Two-Sided Block-Jacobi SVD Algorithm with Dynamic Ordering

We study the convergence of computed quantities to singular triplets in the serial and parallel block-Jacobi singular value decomposition (SVD) algorithm with dynamic ordering. After eliminating possible zero singular values by two finite decompositions of ...
A Jacobi--Davidson Type SVD Method
^* Special Issue 2000 Copper Mountain Conference

We discuss a new method for the iterative computation of a portion of the singular values and vectors of a large sparse matrix. Similar to the Jacobi--Davidson method for the eigenvalue problem, we compute in each step a correction by (approximately) ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Numerische Mathematik

Numerische Mathematik Volume 129, Issue 3

March 2015

203 pages

ISSN:0029-599X

Issue’s Table of Contents

Copyright © Copyright © 2015 Springer-Verlag Berlin Heidelberg.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 March 2015

Author Tag

65F15

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hari V(2021)On the global convergence of the block Jacobi method for the positive definite generalized eigenvalue problemCalcolo: a quarterly on numerical analysis and theory of computation10.1007/s10092-021-00415-858:2Online publication date: 9-May-2021
https://dl.acm.org/doi/10.1007/s10092-021-00415-8
Hari V(2019)On the complex Falk–Langemeyer methodNumerical Algorithms10.1007/s11075-019-00689-883:2(451-483)Online publication date: 2-Apr-2019
https://dl.acm.org/doi/10.1007/s11075-019-00689-8
Hari V(2018)Globally convergent Jacobi methods for positive definite matrix pairsNumerical Algorithms10.1007/s11075-017-0435-579:1(221-249)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1007/s11075-017-0435-5
Begović Kovaă? EHari V(2018)Jacobi method for symmetric 4 x 4 matrices converges for every cyclic pivot strategyNumerical Algorithms10.1007/s11075-017-0396-878:3(701-720)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.1007/s11075-017-0396-8
Okša GYamamoto YBečka MVajteršic M(2018)Asymptotic quadratic convergence of the parallel block-Jacobi EVD algorithm with dynamic ordering for Hermitian matricesBIT10.1007/s10543-018-0711-358:4(1099-1123)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.1007/s10543-018-0711-3
Okša GYamamoto YVajteršic M(2017)Asymptotic quadratic convergence of the serial block-Jacobi EVD algorithm for Hermitian matricesNumerische Mathematik10.1007/s00211-016-0863-5136:4(1071-1095)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1007/s00211-016-0863-5

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents