A qd-type method for computing generalized singular values of BF matrix pairs with sign regularity to high relative accuracy

Huang, Rong

doi:10.1090/mcom/3444

A qd-type method for computing generalized singular values of BF matrix pairs with sign regularity to high relative accuracy
HTML articles powered by AMS MathViewer

by Rong Huang HTML | PDF

Math. Comp. 89 (2020), 229-252 Request permission

Abstract:

Structured matrices such as Vandermonde and Cauchy matrices frequently appear in various areas of modern computing, and they tend to be badly ill-conditioned, but a desirable property is that they admit accurate bidiagonal factorizations (BFs). In this paper, we propose a qd-type method to compute the generalized singular values of BF matrix pairs. A mechanism involving sign regularity of BF generators is provided to guarantee that there is no subtraction of like-signed numbers for the qd-type method. Consequently, all the generalized singular values are computed to high relative accuracy, independent of any conventional condition number. Error analysis and numerical experiments are presented to confirm the high relative accuracy.

References

O. Alter, P. O. Brown, and D. Botstein, Generalized singular decomposition for comparative analysis of genome-scale expression data sets of two different organisms, Proc. Nat. Acad. Sci. USA 100 (2003), 3351–3356.
T. Ando, Totally positive matrices, Linear Algebra Appl. 90 (1987), 165–219. MR 884118, DOI 10.1016/0024-3795(87)90313-2
Zhaojun Bai and James W. Demmel, Computing the generalized singular value decomposition, SIAM J. Sci. Comput. 14 (1993), no. 6, 1464–1486. MR 1241595, DOI 10.1137/0914085
Arkady Berenstein, Sergey Fomin, and Andrei Zelevinsky, Parametrizations of canonical bases and totally positive matrices, Adv. Math. 122 (1996), no. 1, 49–149. MR 1405449, DOI 10.1006/aima.1996.0057
Å. Björck, Numerical Methods for Least Squares Problems, SIAM, Philadelphia, PA, 1996.
Delin Chu, Lieven De Lathauwer, and Bart De Moor, A QR-type reduction for computing the SVD of a general matrix product/quotient, Numer. Math. 95 (2003), no. 1, 101–121. MR 1993940, DOI 10.1007/s00211-002-0431-z
Jorge Delgado and J. M. Peña, Accurate computations with collocation matrices of q-Bernstein polynomials, SIAM J. Matrix Anal. Appl. 36 (2015), no. 2, 880–893. MR 3361436, DOI 10.1137/140993211
James Demmel, Accurate singular value decompositions of structured matrices, SIAM J. Matrix Anal. Appl. 21 (1999), no. 2, 562–580. MR 1742810, DOI 10.1137/S0895479897328716
James Demmel, Ming Gu, Stanley Eisenstat, Ivan Slapničar, Krešimir Veselić, and Zlatko Drmač, Computing the singular value decomposition with high relative accuracy, Linear Algebra Appl. 299 (1999), no. 1-3, 21–80. MR 1723709, DOI 10.1016/S0024-3795(99)00134-2
James W. Demmel and William Gragg, On computing accurate singular values and eigenvalues of matrices with acyclic graphs, Linear Algebra Appl. 185 (1993), 203–217. MR 1213179, DOI 10.1016/0024-3795(93)90213-8
James Demmel, Ioana Dumitriu, Olga Holtz, and Plamen Koev, Accurate and efficient expression evaluation and linear algebra, Acta Numer. 17 (2008), 87–145. MR 2436010, DOI 10.1017/S0962492906350015
James Demmel and W. Kahan, Accurate singular values of bidiagonal matrices, SIAM J. Sci. Statist. Comput. 11 (1990), no. 5, 873–912. MR 1057146, DOI 10.1137/0911052
James Demmel and Plamen Koev, The accurate and efficient solution of a totally positive generalized Vandermonde linear system, SIAM J. Matrix Anal. Appl. 27 (2005), no. 1, 142–152. MR 2176813, DOI 10.1137/S0895479804440335
James Demmel and Plamen Koev, Accurate SVDs of weakly diagonally dominant $M$-matrices, Numer. Math. 98 (2004), no. 1, 99–104. MR 2076055, DOI 10.1007/s00211-004-0527-8
Froilán M. Dopico and Plamen Koev, Perturbation theory for the LDU factorization and accurate computations for diagonally dominant matrices, Numer. Math. 119 (2011), no. 2, 337–371. MR 2836090, DOI 10.1007/s00211-011-0382-3
Zlatko Drmač, A tangent algorithm for computing the generalized singular value decomposition, SIAM J. Numer. Anal. 35 (1998), no. 5, 1804–1832. MR 1639946, DOI 10.1137/S0036142995289883
Zlatko Drmač and Elizabeth R. Jessup, On accurate quotient singular value computation in floating-point arithmetic, SIAM J. Matrix Anal. Appl. 22 (2000), no. 3, 853–873. MR 1799528, DOI 10.1137/S0895479896310548
K. Vince Fernando and Beresford N. Parlett, Accurate singular values and differential qd algorithms, Numer. Math. 67 (1994), no. 2, 191–229. MR 1262781, DOI 10.1007/s002110050024
M. Gasca and J. M. Peña, A matricial description of Neville elimination with applications to total positivity, Linear Algebra Appl. 202 (1994), 33–53. MR 1288481, DOI 10.1016/0024-3795(94)90183-X
Gene Golub, Knut Sølna, and Paul Van Dooren, Computing the SVD of a general matrix product/quotient, SIAM J. Matrix Anal. Appl. 22 (2000), no. 1, 1–19. MR 1779712, DOI 10.1137/S0895479897325578
Gene H. Golub and Charles F. Van Loan, Matrix computations, 3rd ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR 1417720
Peg Howland, Moongu Jeon, and Haesun Park, Structure preserving dimension reduction for clustered text data based on the generalized singular value decomposition, SIAM J. Matrix Anal. Appl. 25 (2003), no. 1, 165–179. MR 2002905, DOI 10.1137/S0895479801393666
Rong Huang, Rank structure properties of rectangular matrices admitting bidiagonal-type factorizations, Linear Algebra Appl. 465 (2015), 1–14. MR 3274659, DOI 10.1016/j.laa.2014.09.016
Rong Huang, A periodic qd-type reduction for computing eigenvalues of structured matrix products to high relative accuracy, J. Sci. Comput. 75 (2018), no. 3, 1229–1261. MR 3798100, DOI 10.1007/s10915-017-0584-7
Rong Huang and Delin Chu, Relative perturbation analysis for eigenvalues and singular values of totally nonpositive matrices, SIAM J. Matrix Anal. Appl. 36 (2015), no. 2, 476–495. MR 3340200, DOI 10.1137/140995702
Rong Huang and Delin Chu, Computing singular value decompositions of parameterized matrices with total nonpositivity to high relative accuracy, J. Sci. Comput. 71 (2017), no. 2, 682–711. MR 3627537, DOI 10.1007/s10915-016-0315-5
Plamen Koev, Accurate eigenvalues and SVDs of totally nonnegative matrices, SIAM J. Matrix Anal. Appl. 27 (2005), no. 1, 1–23. MR 2176803, DOI 10.1137/S0895479803438225
Ana Marco and José-Javier Martínez, A fast and accurate algorithm for solving Bernstein-Vandermonde linear systems, Linear Algebra Appl. 422 (2007), no. 2-3, 616–628. MR 2305145, DOI 10.1016/j.laa.2006.11.020
Ana Marco and José-Javier Martínez, Accurate computations with Said-Ball-Vandermonde matrices, Linear Algebra Appl. 432 (2010), no. 11, 2894–2908. MR 2639252, DOI 10.1016/j.laa.2009.12.034
J. J. Martínez and J. M. Peña, Fast algorithms of Björck-Pereyra type for solving Cauchy-Vandermonde linear systems, Appl. Numer. Math. 26 (1998), no. 3, 343–352. MR 1609143, DOI 10.1016/S0168-9274(97)00102-5
Pietro Mongelli, Total positivity properties of Jacobi-Stirling numbers, Adv. in Appl. Math. 48 (2012), no. 2, 354–364. MR 2873882, DOI 10.1016/j.aam.2011.06.008
Sofiya Ostrovska, On the Lupaş $q$-transform, Comput. Math. Appl. 61 (2011), no. 3, 527–532. MR 2764046, DOI 10.1016/j.camwa.2010.11.025
Victor Y. Pan, Structured matrices and polynomials, Birkhäuser Boston, Inc., Boston, MA; Springer-Verlag, New York, 2001. Unified superfast algorithms. MR 1843842, DOI 10.1007/978-1-4612-0129-8
Victor Y. Pan, How bad are Vandermonde matrices?, SIAM J. Matrix Anal. Appl. 37 (2016), no. 2, 676–694. MR 3504989, DOI 10.1137/15M1030170
C. C. Paige, Computing the generalized singular value decomposition, SIAM J. Sci. Statist. Comput. 7 (1986), no. 4, 1126–1146. MR 857786, DOI 10.1137/0907077
C. C. Paige and M. A. Saunders, Towards a generalized singular value decomposition, SIAM J. Numer. Anal. 18 (1981), no. 3, 398–405. MR 615522, DOI 10.1137/0718026
Beresford N. Parlett, The new qd algorithms, Acta numerica, 1995, Acta Numer., Cambridge Univ. Press, Cambridge, 1995, pp. 459–491. MR 1352476, DOI 10.1017/s0962492900002580
Cheong Hee Park and Haesun Park, Nonlinear discriminant analysis using kernel functions and the generalized singular value decomposition, SIAM J. Matrix Anal. Appl. 27 (2005), no. 1, 87–102. MR 2176809, DOI 10.1137/S0895479804442334
George M. Phillips, Interpolation and approximation by polynomials, CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, vol. 14, Springer-Verlag, New York, 2003. MR 1975918, DOI 10.1007/b97417
William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery, Numerical recipes: the art of scientific computing. Code CD-ROM v 2.06 with UNIX single-screen license, Cambridge University Press, Cambridge, 1996. MR 1414682
Konstanze Rietsch, Totally positive Toeplitz matrices and quantum cohomology of partial flag varieties, J. Amer. Math. Soc. 16 (2003), no. 2, 363–392. MR 1949164, DOI 10.1090/S0894-0347-02-00412-5
G. W. Stewart, Computing the $CS$ decomposition of a partitioned orthonormal matrix, Numer. Math. 40 (1982), no. 3, 297–306. MR 695598, DOI 10.1007/BF01396447
Charles F. Van Loan, Generalizing the singular value decomposition, SIAM J. Numer. Anal. 13 (1976), no. 1, 76–83. MR 411152, DOI 10.1137/0713009
Charles Van Loan, Computing the CS and the generalized singular value decompositions, Numer. Math. 46 (1985), no. 4, 479–491. MR 796639, DOI 10.1007/BF01389653
Qiang Ye, Computing singular values of diagonally dominant matrices to high relative accuracy, Math. Comp. 77 (2008), no. 264, 2195–2230. MR 2429881, DOI 10.1090/S0025-5718-08-02112-1