On high relative accuracy of the Kogbetliantz method. (English) Zbl 1302.65093
Summary: The relative accuracy of the Kogbetliantz method for computing the singular value decomposition of real triangular matrices is considered. Sharp relative error bounds for the computed singular values are derived. The results are obtained by estimating the norms of scaled perturbation matrices arising from errors generated in one step and one batch of commuting transformations. Perturbation matrices are scaled either from the left or right side by the inverse of the diagonal matrix.
MSC:
| 65F20 | Numerical solutions to overdetermined systems, pseudoinverses |
| 65F50 | Computational methods for sparse matrices |
Keywords:
singular value decomposition; relative accuracy; Kogbetliantz method; triangular matrices; error boundReferences:
| [1] | Bujanović, Z.; Drmač, Z., A contribution to the theory and practise of the block Kogbetliantz method for computing the SVD, BIT, 52, 4, 827-849 (2012) · Zbl 1264.65059 |
| [2] | Charlier, J. P.; Van Dooren, P., On Kogbetliantz’s SVD algorithm in the presence of clusters, Linear Algebra Appl., 95, 135-160 (1987) · Zbl 0627.65037 |
| [3] | Charlier, J. P.; Vanbegin, M.; Van Dooren, P., On efficient implementation of Kogbetliantz’s algorithm for computing the singular value decomposition, Numer. Math., 52, 279-300 (1988) · Zbl 0617.65032 |
| [4] | Dehaene, J.; Moonen, M.; Vandewalle, J., Analysis of a class of continuous-time algorithms for principal component analysis and subspace tracking, IEEE Trans. Circuits Syst. I Fund. Theory Appl., 46, 3, 364-372 (1999) · Zbl 0952.94001 |
| [5] | Drmač, Z.; Veselić, K., New fast and accurate Jacobi SVD algorithm. I, SIAM J. Matrix Anal. Appl., 29, 4, 1322-1342 (2008) · Zbl 1221.65100 |
| [6] | Fernando, K. V., Linear convergence of the row-cyclic Jacobi and Kogbetliantz methods, Numer. Math., 56, 71-91 (1989) · Zbl 0682.65018 |
| [7] | Forsythe, G. E.; Henrici, P., The cyclic Jacobi method for computing the principal values of a complex matrix, Trans. Amer. Math. Soc., 94, 1-23 (1960) · Zbl 0092.32504 |
| [8] | Hari, V., On the convergence of cyclic Jacobi-like processes, Linear Algebra Appl., 81, 105-127 (1986) · Zbl 0619.65025 |
| [9] | Hari, V., On the quadratic convergence of Jacobi algorithms, Rad. Mat., 2, 127-146 (1986) · Zbl 0596.65021 |
| [10] | Hari, V., On the quadratic convergence bounds of the serial singular value decomposition Jacobi methods for triangular matrices, SIAM J. Sci. Stat. Comput., 10, 1076-1096 (1989) · Zbl 0685.65026 |
| [11] | Hari, V., On sharp quadratic convergence bounds for the serial Jacobi methods, Numer. Math., 60, 375-406 (1991) · Zbl 0743.65036 |
| [12] | Hari, V., Accelerating the SVD block-Jacobi method, Computing, 75, 27-53 (2005) · Zbl 1079.65046 |
| [13] | Hari, V.; Veselić, K., On Jacobi methods for singular value decompositions, SIAM J. Sci. Stat. Comput., 8, 5, 741-754 (1987) · Zbl 0627.65039 |
| [14] | Hari, V.; Matejaš, J., Quadratic convergence of scaled iterates by Kogbetliantz method, Computing, 16, Suppl., 83-105 (2003) · Zbl 1038.65036 |
| [15] | Hari, V.; Zadelj-Martić, V., Parallelizing the Kogbetliantz method: A first attempt, JNAIAM J. Numer. Anal. Ind. Appl. Math., 2, 1-2, 49-66 (2007) · Zbl 1128.65028 |
| [16] | Hari, V.; Matejaš, J., Accuracy of two SVD algorithms for \(2 \times 2\) triangular matrices, Appl. Math. Comput., 210, 232-257 (2009) · Zbl 1166.65014 |
| [17] | Hari, V.; Singer, S.; Singer, S., Full block \(J\)-Jacobi method for Hermitian matrices, Linear Algebra Appl., 444, 1-27 (2014) · Zbl 1329.65075 |
| [18] | Ipsen, I. C.F., Relative perturbation results for matrix eigenvalues and singular values, (Acta Numerica 1998 (1998), Cambridge University Press: Cambridge University Press Cambridge), 151-201 · Zbl 0916.15008 |
| [19] | Kavčić, A.; Yang, B., Subspace tracking with adaptive threshold rank estimation, J. VLSI Signal Process., 14, 75-92 (1996) · Zbl 0862.94007 |
| [20] | Kogbetliantz, E., Diagonalization of general complex matrices as a new method for solution of linear equations, Proc. Internat. Congr. Math. Amsterdam, 2, 356-357 (1954) |
| [21] | Kogbetliantz, E., Solutions of linear equations by diagonalization of coefficient matrices, Quart. Appl. Math., 13, 123-132 (1955) · Zbl 0066.10101 |
| [22] | Londre, T.; Rhee, N. H., Numerical stability of the parallel Jacobi method, SIAM J. Matrix Anal. Appl., 26, 4, 985-1000 (2005) · Zbl 1079.65042 |
| [23] | Luk, F., A triangular processor array for computing singular values, Linear Algebra Appl., 77, 259-273 (1986) · Zbl 0587.65028 |
| [24] | Matejaš, J.; Hari, V., Scaled iterates by Kogbetliantz method, (Proceedings of the 1st Conference on Applied Mathematics and Computations. Proceedings of the 1st Conference on Applied Mathematics and Computations, Dubrovnik, Croatia, September 13-18, 1999 (2001), Dept. of Mathematics: Dept. of Mathematics University of Zagreb), 1-20 · Zbl 1048.65038 |
| [25] | Matejaš, J.; Hari, V., Accuracy of the Kogbetliantz method for scaled diagonally dominant triangular matrices, Appl. Math. Comput., 217, 3726-3746 (2010) · Zbl 1206.65138 |
| [26] | Moonen, M.; Van Dooren, P.; Vandewalle, J., A singular value decomposition updating algorithm for subspace tracking, SIAM J. Matrix Anal. Appl., 13, 4, 1015-1038 (1992) · Zbl 0759.65017 |
| [27] | Okša, G.; Vajteršic, M., Systolic block-Jacobi SVD algorithm for processor meshes, (Highly Parallel Computations: Algorithms and Applications (2001), WIT Press), 211-235 |
| [28] | Paige, C. C.; Van Dooren, P., On the quadratic convergence of Kogbetliantz’s algorithm for computing the singular value decomposition, Linear Algebra Appl., 77, 301-313 (1986) · Zbl 0621.65031 |
| [29] | Sameh, A. H., On Jacobi and Jacobi-like algorithms for a parallel computer, Math. Comp., 25, 118, 579-590 (1971) · Zbl 0222.65046 |
| [30] | 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 |
| [31] | van der Sluis, A., Condition numbers and equilibration of matrices, Numer. Math., 14, 1, 14-23 (1969) · Zbl 0182.48906 |
| [32] | Voevodin, V. V., Cislennye Metody Linejnoj Algebry (1966), Nauka: Nauka Moscow |
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.
