Accurate solutions of structured generalized Kronecker product linear systems
Tóm tắt
In this paper, we consider the generalized Kronecker product (GKP) linear system associated with a class of consecutive-rank-descending (CRD) matrices arising from bivariate interpolation problems. Relying on the sign sequences of CRD matrices, we show that the associated GKP linear system is accurately solved with an “ideal” componentwise forward error. In particular, a pleasantly small componentwise relative forward error is provided to illustrate that each component of the solution is computed to high relative accuracy. We then present the sign sequences of generalized Vandermonde matrices to show that the associated GKP linear system is accurately solved with the desired componentwise forward errors. Numerical experiments are performed to confirm the high relative accuracy.
Tài liệu tham khảo
Banoczi, J.M., Chiu, N.C., Cho, G.E., Ipsen, I.C.F.: The lack of influence of the right-hand side on the accuracy of linear system solution. SIAM J. Sci. Comput. 20, 203–227 (1998)
Björck, A., Pereyra, V.: Solution of Vandermonde systems of equations. Math. Comp. 24, 893–903 (1970)
Boros, T., Kailath, T., Olshevsky, V.: A fast parallel björck-pereyra-type algorithm for solving Cauchy linear equations. Linear Algebra Appl. 302/303, 265–293 (1999)
Caliari, M., De Marchi, S., Vianello, M.: Bivariate polynomial interpolation on the square at new nodal sets. Appl. Math. Comput. 165, 261–274 (2005)
Delgado, J., Peña, J.M.: Accurate computations with collocation matrices of rational bases. Appl. Math. Comput. 219, 4354–4364 (2013)
Delgado, J., Peña, J.M.: Accurate computations with collocation matrices of q-Bernstein polynomials. SIAM J. Matrix Anal. Appl. 36, 880–893 (2015)
Demmel, J., Kahan, W.: Accurate singular values of bidiagonal matrices. SIAM J. Sci Stat. Comp. 11, 873–912 (1990)
Demmel, 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)
Demmel, J., Koev, P.: The accurate and efficient solution of a totally positive generalized Vandermonde linear system. SIAM J. Matrix Anal. Appl. 27, 142–152 (2005)
Demmel, J., Koev, P.: Accurate and efficient evaluation of Schur and Jack functions. Math. Comp. 75, 223–239 (2006)
Demmel, J., Dumitriu, I., Holtz, O., Koev, P.: Accurate and efficient expression evaluation and linear algebra. Acta Numer. 17, 87–145 (2008)
Dopico, F.M., Koev, P.: Accurate symmetric rank revealing and eigendecompositions of symmetric structured matrices. SIAM J. Matrix Anal. Appl. 28, 1126–1156 (2006)
Dopico, F.M., Koev, P.: Perturbation theory for the LDU factorization and accurate computations for diagonally dominant matrices. Numer. Math. 119, 337 (2011)
Dopico, F.M., Molera, J.M.: Accurate solution of structured linear systems via rank-revealing decompositions. IMA J. Numer. Anal. 32, 1096–1116 (2012)
Gasca, M., Martínez, J.J.: On the solvability of bivariate Hermite-Birkhoff interpolation problems. J. Comput. Appl. Math. 32, 77–82 (1990)
Gasca, M., Peña, J.M.: Total positivity and Neville elimination. Linear Algebra Appl. 165, 25–44 (1992)
Gasca, M., Peña, J.M.: Total positivity, QR factorization and Neville elimination. SIAM J. Matrix Anal. 14, 1132–1140 (1993)
Gasca, M., Peña, J.M.: A matricial description of Neville elimination with applications to total positivity. Linear Algebra Appl. 202, 33–53 (1994)
Huang, R., Liu, J.Z., Zhu, L.: Accurate solutions of diagonally dominant tridiagonal linear systems. BIT 54, 711–727 (2014)
Huang, R.: Rank structure properties of rectangular matrices admitting bidiagonal-type factorizations. Linear Algebra Appl. 465, 1–14 (2015)
Huang, R.: A periodic qd-type reduction for computing eigenvalues of structured matrix products to high relative accuracy. J. Sci. Comput. 75, 1229–1261 (2018)
Huang, R.: Accurate solutions of product linear systems associated with rank-structured matrices. J. Comput. Appl. Math. 347, 108–127 (2019)
Huang, R.: Accurate solutions of weighted least squares problems associated with rank-structured matrices. Appl. Numer. Math. 146, 416–435 (2019)
Huang, R.: A qd-type method for computing generalized singular values of BF matrix pairs with sign regularity to high relative accuracy. Math. Comp. 89, 229–252 (2020)
Koev, P.: Accurate eigenvalues and SVDs of totally nonnegative matrices. SIAM J. Matrix Anal. Appl. 27, 1–23 (2005)
Koev, P.: Accurate computations with totally nonnegative matrices. SIAM J. Matrix Anal. Appl. 29, 731–751 (2007)
Koev, P.: http://math.mit.edu/plamen/software/TNTool.html
Macdonald, I.G.: Symmetric Functions and Hall Polynomials, 2nd ed. Oxford University Press (1998)
Marco, A., Martínez, J.J.: A fast and accurate algorithm for solving Bernstein-Vandermonde linear systems. Linear Algebra Appl. 422, 616–628 (2007)
Marco, A., Martínez, J.J.: Unique solvability in bivariate Hermite interpolation. Electron. Trans. Numer. Anal. 34, 20–30 (2008)
Marco, A., Martínez, J.J., Peña, J. M.: Accurate bidiagonal decomposition of totally positive Cauchy-Vandermonde matrices and applications. Linear Algebra Appl. 517, 63–84 (2017)
Marco, A., Martínez, J.J., Viaña, R.: Accurate polynomial interpolation by using the Bernstein basis. Numer. Algor. 75, 655–674 (2017)
Martínez, J.J., Peña, J. M.: Factorizations of Cauchy-Vandermonde matrices. Linear Algebra Appl. 284, 229–237 (1998)
Martínez, J.J.: A generalized Kronecker product and linear systems. Int. J. Math. Educ. Sci. Technol. 30, 137–141 (1999)
Varsamis, D.N., Karampetakis, N.P.: On the Newton bivariate polynomial interpolation with applications. Syst. Sign. Process. 25, 179–209 (2014)
Yang, Z., Huang, R., Zhu, W.: Accurate computations for eigenvalues of products of Cauchy-polynomial-Vandermonde matrices. Numer. Algor. https://doi.org/10.1007/s11075-019-00816-5 (2019)