Accuracy of two SVD algorithms for \(2\times 2\) triangular matrices (Q1015805)

The paper proves and compares accuracy estimates of two algorithms for computing the singular value decomposition (SVD) of \(2 \times 2\) triangular matrices. The first algorithm is a new one. It is composed of four known algorithms. Two of them are used for the upper- and the other two for the lower-triangular \(2 \times 2\) matrix. The second algorithm is the existing algorithm which is coded as LAPACK auxiliary routine xLASV2. For simplicity, it is referred to it as the LAPACK algorithm. In the beginning of the paper, the formulas which define the new algorithm are briefly derived. They are based on the Voevodin formulas for computing the SVD of general \(2 \times 2\) matrices. These formulas have already been used as part of the Kogbetliantz method for computing the SVD of \(n \times n\) triangular matrices. However, for the completeness of the exposition, the formulas are derived in a new simple way, which additionally delivers several essential details which are used later. A \(2\times 2\) triangular matrix can be either upper- or lower-triangular. For the upper-triangular case, two algorithms are derived, depending on whether the left or the right rotation is applied first. They are called UL and UR algorithm. By a proper selection between these two algorithms, a new accurate algorithm for the upper-triangular case is defined. Similarly, for the lower-triangular case, two algorithms are obtained, and selection is made to obtain an accurate algorithm. A nice fact is that instead of using four pairs of formulas (used in UL, UR, LL and LR algorithms) one can use just one. A subtle error analysis of the new algorithm is provided. Some natural assumptions for the analysis are given. First, basic error analysis assumptions are accomplished, which are based on the IEEE standard. In the analysis, the nonlinear parts of the errors are not neglected, and the linear and the nonlinear part of each error are estimated separately. In addition, the signs of the errors, especially of the intermediate quantities are kept on the track. Finally, the errors of the output data are expressed in terms of some quantities which depend on the off-diagonally of the matrix. The proofs are somewhat lengthy, so they are extracted and placed in the Appendix A. The same analysis is applied to the LAPACK algorithm. The error bounds for the two algorithms are compared and the results of simple numerical tests are presented. In general, the errors obtained for the new algorithm are somewhat better than those obtained for the LAPACK algorithm. More importantly, in the case of an almost diagonal \(2\times 2\) triangular matrix, the estimates for the new algorithm are notably better than those of the LAPACK algorithm. This fact is important since each of these two algorithms can be used as the core algorithm of the Kogbetliantz method for \(n\times n\) triangular matrices. Since after some iteration, the Kogbetliantz method works with an almost diagonal matrix the new algorithm seems to be a more appropriate candidate to be used as the core of the Kogbetliantz method.