×

Accurate computations and applications of some classes of matrices. (English) Zbl 1444.65017

Mateos, Mariano (ed.) et al., Computational mathematics, numerical analysis and applications. Lecture notes of the XVII ‘Jacques-Louis Lions’ Spanish-French school, Gijón, Spain, June 2016. Cham: Springer. SEMA SIMAI Springer Ser. 13, 107-151 (2017).
Summary: Performing an algorithm with high relative accuracy is a very desirable goal. High relative accuracy means that the relative errors of the computations are of the order of machine precision, independently of the size of the condition number. This goal is difficult to assure although in recent years there have been some advances, in particular in the field of Numerical Linear Algebra. Up to now, computations with high relative accuracy are guaranteed only for a few classes of matrices, mainly for some subclasses of \(M\)-matrices and for some subclasses of totally positive matrices. Previously, a reparametrization of the matrices is needed. We review this procedure related with the high relative accuracy computations of these matrices. We also present some recent applications of the two classes of matrices mentioned previously. On the one hand, applications of \(M\)-matrices to the linear complementarity problem. On the other hand, applications of totally positive matrices to Computer Aided Geometric Design.
For the entire collection see [Zbl 1378.65014].

MSC:

65F99 Numerical linear algebra
65G50 Roundoff error
65K05 Numerical mathematical programming methods
65D17 Computer-aided design (modeling of curves and surfaces)

Software:

POLYNOMIAL
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alanelli, M., Hadjidimos, A.: A new iterative criterion for H-matrices. SIAM J. Matrix Anal. Appl. 29, 160-176 (2006/2007) · Zbl 1140.65031
[2] Alfa, A.S., Xue, J., Ye, Q.: Entrywise perturbation theory for diagonally dominant M-matrices with applications. Numer. Math. 90, 401-414 (1999) · Zbl 1022.15020 · doi:10.1007/s002110100289
[3] Alfa, A.S., Xue, J., Ye, Q.: Accurate computation of the smallest eigenvalue of a diagonally dominant M-matrix. Math. Comp. 71, 217-236 (2001) · Zbl 0984.65033 · doi:10.1090/S0025-5718-01-01325-4
[4] Alonso, P., Gasca, M., Peña, J.M.: Backward error analysis of Neville elimination. Appl. Numer. Math. 23, 193-204 (1997) · Zbl 0870.65021 · doi:10.1016/S0168-9274(96)00051-7
[5] Alonso, P., Delgado, J., Gallego, R., Peña, J.M.: Iterative refinement for Neville elimination. Int. J. Comput. Math. 86, 341-353 (2009) · Zbl 1159.65029 · doi:10.1080/00207160802044134
[6] Alonso, P., Delgado, J., Gallego, R., Peña, J.M.: Growth factors of pivoting strategies associated to Neville elimination. J. Comput. Appl. Math. 235, 1755-1762 (2011) · Zbl 1218.65029 · doi:10.1016/j.cam.2009.11.012
[7] Alonso, P., Delgado, J., Gallego, R., Peña, J.M.: Conditioning and accurate computations with Pascal matrices. J. Comput. Appl. Math. 252, 21-26 (2013) · Zbl 1291.65133 · doi:10.1016/j.cam.2011.12.007
[8] Ando, T.: Totally positive matrices. Linear Algebra Appl. 90, 165-219 (1987) · Zbl 0613.15014 · doi:10.1016/0024-3795(87)90313-2
[9] Andrews, G.G., Egge, E.S., Gawronnski, W., Littlejohn, L.L.: The Jacobi-Stirling numbers. J. Combin. Theory Ser. A 120 288-303 (2013) · Zbl 1261.11022 · doi:10.1016/j.jcta.2012.08.006
[10] Barreras, A., Peña, J.M.: Accurate and efficient LDU decompositions of diagonally dominant M-matrices. Electron. J. Linear Algebra 24, 153-167 (2012) · Zbl 1250.65047 · doi:10.13001/1081-3810.1585
[11] Barreras, A., Peña, J.M.: Accurate computations of matrices with bidiagonal decomposition using methods for totally positive matrices. Numer. Linear Algebra Appl. 20, 413-424 (2013) · Zbl 1313.65043 · doi:10.1002/nla.1832
[12] Barreras, A., Peña, J.M.: Accurate and efficient LDU decomposition of almost diagonally dominant Z-matrices. BIT Numer. Math. 54, 343-356 (2014) · Zbl 1298.65045 · doi:10.1007/s10543-013-0461-1
[13] Barrio, R. Peña, J.M.: Numerical evaluation of the p-th derivative of Jacobi series. Appl. Numer. Math. 43, 335-357 (2002) · Zbl 1018.65031 · doi:10.1016/S0168-9274(02)00106-X
[14] Barrio, R., Peña, J.M.: Evaluation of the derivative of a polynomial in Bernstein form. Appl. Math. Comput. 167, 125-142 (2005) · Zbl 1086.65014
[15] Berman, A., Plemmons, R.J.: Nonnegative Matrices in the Mathematical Sciences. Classics in Applied Mathematics, vol. 9, SIAM, Philadelphia (1994) · Zbl 0815.15016
[16] Carnicer, J.M., Peña, J.M.: Shape preserving representations and optimality of the Bernstein basis. Adv. Comput. Math. 1, 173-196 (1993) · Zbl 0832.41013 · doi:10.1007/BF02071384
[17] Carnicer, J.M., Peña, J.M.: Totally positive bases for shape preserving curve design and optimality of B-splines. Comput. Aided Geom. Des. 11, 633-654 (1994) · Zbl 0875.68828 · doi:10.1016/0167-8396(94)90056-6
[18] Carnicer, J.M., Peña, J.M.: Total positivity and optimal bases. In: Gasca, M., Micchelli, C.A. (eds.) Total Positivity and Its Applications. Mathematics and Its Applications, vol. 359, pp. 133-155. Kluwer Academic Publishers, Dordrecht (1996) · Zbl 0892.15002 · doi:10.1007/978-94-015-8674-0_8
[19] Carnicer, J.M., García, M., Peña, J.M.: Generalized convexity preserving transformations. Comput. Aided Geom. Des. 13, 179-197 (1995) · Zbl 0900.68404 · doi:10.1016/0167-8396(95)00021-6
[20] Chen, X., Xiang, S.: Computation of error bounds for P-matrix linear complementarity problems. Math. Program. Ser. A 106, 513-525 (2006) · Zbl 1134.90043 · doi:10.1007/s10107-005-0645-9
[21] Cottle, R.W., Pang, J.S., Stone, R.E.: The Linear Complementarity Problems. Academic Press, Boston (1992) · Zbl 0757.90078
[22] Cryer, C.W.: Some properties of totally positive matrices. Linear Algebra Appl. 15, 1-25 (1976) · Zbl 0337.15017 · doi:10.1016/0024-3795(76)90076-8
[23] Delgado, J., Peña, J.M.: A corner cutting algorithm for evaluating rational Bézier surfaces and the optimal stability of the basis. SIAM J. Sci. Comput. 29, 1668-1682 (2007) · Zbl 1187.65014 · doi:10.1137/060649148
[24] Delgado, J., Peña, J.M.: Progressive iterative approximation and bases with the fastest convergence rates. Comput. Aided Geom. Des. 24, 10-18 (2007) · Zbl 1171.65319 · doi:10.1016/j.cagd.2006.10.001
[25] Delgado, J., Peña, J.M.: Error analysis of efficient evaluation algorithms for tensor product surfaces. J. Comput. Appl. Math. 219, 156-169 (2008) · Zbl 1153.65016 · doi:10.1016/j.cam.2007.07.020
[26] Delgado, J., Peña, J.M.: Running relative error for the evaluation of polynomials. SIAM J. Sci. Comput. 31 3905-3921 (2009) · Zbl 1202.65061 · doi:10.1137/080745249
[27] Delgado, J., Peña, J.M.: Optimal conditioning of Bernstein collocation matrices. SIAM J. Matrix Anal. Appl. 31, 990-996 (2009) · Zbl 1213.65072 · doi:10.1137/080737976
[28] Delgado, J., Peña, J.M.: Running error for the evaluation of rational Bézier surfaces. J. Comput. Appl. Math. 233, 1685-1696 (2010) · Zbl 1204.65015 · doi:10.1016/j.cam.2009.02.023
[29] Delgado, J., Peña, J.M.: Running error for the evaluation of rational Bézier surfaces through a robust algorithm. J. Comput. Appl. Math. 235, 1781-1789 (2011) · Zbl 1211.65021 · doi:10.1016/j.cam.2010.04.031
[30] Delgado, J., Peña, J.M.: On the evaluation of rational triangular Bézier surfaces and the optimal stability of the basis. Adv. Comput. Math. 38, 701-721 (2013) · Zbl 1279.65021 · doi:10.1007/s10444-011-9256-6
[31] Delgado, J., Peña, J.M.: Accurate computations with collocation matrices of rational bases. Appl. Math. Comput. 219, 4354-4364 (2013) · Zbl 1432.65023
[32] Delgado, J., Peña, J.M.: Fast and accurate algorithms for Jacobi-Stirling matrices. Appl. Math. Comput. 236, 253-259 (2014) · Zbl 1336.65055
[33] Delgado, J., Peña, J.M.: Accurate evaluation of Bézier curves and surfaces and the Bernstein-Fourier algorithm. Appl. Math. Comput. 271, 113-122 (2015) · Zbl 1410.65047
[34] Delgado, J., Peña, J.M.: Accurate computations with collocation matrices of q-Bernstein polynomials. SIAM J. Matrix Anal. Appl. 36, 880-893 (2015) · Zbl 1319.65025 · doi:10.1137/140993211
[35] Delgado, J., Peña, J.M.: Algorithm 960: POLYNOMIAL: an object-oriented Matlab library of fast and efficient algorithms for polynomials. Trans. Math. Softw. 42, 19 (2016) · Zbl 1369.65021 · doi:10.1145/2814567
[36] Delgado, J., Peña, G., Peña, J.M.: Accurate and fast computations with positive extended Schoenmakers-Coffey matrices. Numer. Linear Algebra Appl. 23, 1023-1031 (2016) · Zbl 1424.65020 · doi:10.1002/nla.2066
[37] Demmel, J., Koev, P.: Accurate SVDs of weakly diagonally dominant M-matrices. Numer. Math. 98, 99-104 (2004) · Zbl 1054.65037 · doi:10.1007/s00211-004-0527-8
[38] 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) · Zbl 1096.65031 · doi:10.1137/S0895479804440335
[39] Demmel, J., Gu, M., Eisenstat, S., Slapnicar, I., Veselic, K., Drmac, Z.: Computing the singular value decomposition with high relative accuracy. Linear Algebra Appl. 299, 21-80 (1999) · Zbl 0952.65032 · doi:10.1016/S0024-3795(99)00134-2
[40] Demmel, J., Dumitriu, I., Holtz, O., Koev, P.: Accurate and efficient expression evaluation and linear algebra. Acta Numer. 17, 87-145 (2008) · Zbl 1169.65022 · doi:10.1017/S0962492906350015
[41] Dopico, F.M., Koev, P.: Perturbation theory for the LDU factorization and accurate computations for diagonally dominant matrices. Numer. Math. 119, 337-371 (2001) · Zbl 1254.65042 · doi:10.1007/s00211-011-0382-3
[42] Everitt, W.N., Kwon, K.H., Littlejohn, L.L., Wellman R., Yoon, G.J.: Jacobi-Stirling numbers, Jacobi polynomials, and the left-definite analysis of the classical Jacobi differential expression. J. Comput. Appl. Math. 208, 29-56 (2007) · Zbl 1119.33009 · doi:10.1016/j.cam.2006.10.045
[43] Fallat, S.M., Johnson, C.R.: Totally Nonnegative Matrices. Princeton University Press, Princeton/Oxford (2011) · Zbl 1390.15001 · doi:10.1515/9781400839018
[44] Farin, G.: Curves and Surfaces for Computer Aided Geometric Design. Academic Press, Boston (1988) · Zbl 0694.68004
[45] Frydman, H., Singer, B.: Total positivity and the embedding problem for Markov chains. Math. Proc. Camb. Philos. Soc. 85, 339-344 (1979) · Zbl 0411.60071 · doi:10.1017/S0305004100056152
[46] Gantmacher, F.P., Krein, M.G.: Oscillation Matrices and Kernels and Small Vibrations of Mechanical Systems (revised ed.). AMS Chelsea, Providence (2002) · Zbl 1002.74002
[47] García-Esnaola, M., Peña, J.M.: Error bounds for linear complementarity problems of B-matrices. Appl. Math. Lett. 22, 1071-1075 (2009) · Zbl 1179.90230 · doi:10.1016/j.aml.2008.09.001
[48] García-Esnaola, M., Peña, J.M.: A comparison of error bounds for linear complementarity problems of H-matrices. Linear Algebra Appl. 433, 956-964 (2010) · Zbl 1195.65077 · doi:10.1016/j.laa.2010.04.024
[49] García-Esnaola, M., Peña, J.M.: Error bounds for linear complementarity problems of B^S-matrices. Appl. Math. Lett. 25, 1379-1383 (2012) · Zbl 1247.90265 · doi:10.1016/j.aml.2011.12.006
[50] García-Esnaola, M., Peña, J.M.: Error bounds for the linear complementarity problem with a Σ-SDD matrix. Linear Algebra Appl. 438, 1339-1346 (2013) · Zbl 1261.90064 · doi:10.1016/j.laa.2012.09.018
[51] García-Esnaola, M., Peña, J.M.: Error bounds for linear complementarity problems of Nekrasov matrices. Numer. Algorithms 67, 655-667 (2014) · Zbl 1338.90406 · doi:10.1007/s11075-013-9815-7
[52] García-Esnaola, M., Peña, J.M.: B-Nekrasov matrices and error bounds for linear complementarity problems. Numer. Algorithms 72, 435-445 (2016) · Zbl 1342.90205 · doi:10.1007/s11075-015-0054-y
[53] Gasca, M., Micchelli, C.A. (eds.): Total Positivity and Its Applications. Mathematics and Its Applications, vol. 359. Kluwer Academic Publishers, Dordrecht (1996) · Zbl 0884.00045
[54] Gasca, M., Mühlbach, G.: Generalized Schur complements and a test for total positivity. Applied Numer. Math. 3, 215-232 (1987) · Zbl 0621.65013 · doi:10.1016/0168-9274(87)90049-3
[55] Gasca, M., Peña, J.M.: Total positivity and Neville elimination. Linear Algebra Appl. 165, 25-44 (1992) · Zbl 0749.15010 · doi:10.1016/0024-3795(92)90226-Z
[56] Gasca, M., Peña, J.M.: A matricial description of Neville elimination with applications to total positivity. Linear Algebra Appl. 202, 33-45 (1994) · Zbl 0804.65028 · doi:10.1016/0024-3795(94)90183-X
[57] Gasca, M., Peña, J.M.: On factorizations of totally positive matrices. In: Gasca, M., Micchelli, C.A. (eds). Total Positivity and Its Applications. Mathematics and Its Applications, vol. 359, pp. 109-130. Kluwer Academic Publishers, Dordrecht (1996) · Zbl 0891.15017 · doi:10.1007/978-94-015-8674-0_7
[58] Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. The John Hopkins University Press, Baltimore (1996) · Zbl 0865.65009
[59] Goodman, G.: A probabilistic representation of totally positive matrices. Adv. Appl. Math. 7, 236-252 (1986) · Zbl 0611.60058 · doi:10.1016/0196-8858(86)90035-7
[60] Goodman, T.N.T., Micchelli, C.A.: Corner cutting algorithms for the Bézier representation of free form curves. Linear Alg. Appl. 99, 225-252 (1988) · Zbl 0652.41003 · doi:10.1016/0024-3795(88)90134-6
[61] Goodman, T.N.T., Said, H.B.: Shape preserving properties of the generalized Ball basis. Comput. Aided Geom. Des. 8, 115-121 (1991) · Zbl 0729.65006 · doi:10.1016/0167-8396(91)90037-C
[62] Goodman, T.N.T., Oruç, H., Phillips, G.M.: Convexity and generalized Bernstein polynomials. Proc. Edinb. Math. Soc. 42, 179-190 (1999) · Zbl 0930.41010 · doi:10.1017/S0013091500020101
[63] Higham, N.J.: Accuracy and Stability of Numerical Algorithms, 2nd edn. SIAM, Philadelphia (2002) · Zbl 1011.65010 · doi:10.1137/1.9780898718027
[64] Karlin, S.: Total Positivity, vol. 1. Stanford University Press, Stanford (1968) · Zbl 0219.47030
[65] Karlin, S., McGregor, J.L.: Coincidence probabilities of birth and death processes. Pac. J. Math. 9, 1109-1140 (1959) · Zbl 0097.34102 · doi:10.2140/pjm.1959.9.1109
[66] Karlin, S., McGregor, J.L.: Coincidence probabilities. Pac J. Math. 9, 1141-1164 (1959) · Zbl 0092.34503 · doi:10.2140/pjm.1959.9.1141
[67] Koev, P.: Accurate eigenvalues and SVDs of totally nonnegative matrices. SIAM J. Matrix Anal. Appl. 27, 1-23 (2005) · Zbl 1095.65031 · doi:10.1137/S0895479803438225
[68] Koev, P.: Accurate computations with totally nonnegative matrices. SIAM J. Matrix Anal. Appl. 29, 731-751 (2007) · Zbl 1198.65057 · doi:10.1137/04061903X
[69] Koev, P.: http://math.mit.edu/ plamen/software/TNTool.html
[70] Li, L.: On the iterative criterion for generalized diagonally dominant matrices. SIAM J. Matrix Anal. Appl. 24, 17-24 (2002) · Zbl 1018.65039 · doi:10.1137/S0895479898348829
[71] Loewner, C.: On totally positive matrices. Math. Z. 63, 338-340 (1955) · Zbl 0068.25004 · doi:10.1007/BF01187945
[72] Lyche, T., Peña, J.M.: Optimally stable multivariate bases. Adv. Comput. Math. 20, 149-159 (2004) · Zbl 1041.65017 · doi:10.1023/A:1025863309959
[73] Mainar, E., Peña, J.M.: Error analysis of corner cutting algorithms. Numer. Algorithms 22, 41-52 (1999) · Zbl 0964.65008 · doi:10.1023/A:1019190220312
[74] Marco, A., Martínez, J.J.: A fast and accurate algorithm for solving Bernstein-Vandermonde linear systems. Linear Algebra Appl. 422, 616-628 (2007) · Zbl 1116.65038 · doi:10.1016/j.laa.2006.11.020
[75] Marco, A., Martínez, J.J.: Accurate computations with Said-Ball-Vandermonde matrices. Linear Algebra Appl. 432, 2894-2908 (2010) · Zbl 1189.65054 · doi:10.1016/j.laa.2009.12.034
[76] Markham, T.L.: A semigroup of totally nonnegative matrices. Linear Algebra Appl. 3, 157-164 (1970) · Zbl 0206.04003 · doi:10.1016/0024-3795(70)90011-X
[77] Mathias, R., Pang, J.S.: Error bounds for the linear complementarity problem with a P-matrix. Linear Algebra Appl. 132, 123-136 (1990) · Zbl 0711.90077 · doi:10.1016/0024-3795(90)90058-K
[78] Micchelli, C.A., Pinkus A.: Descartes systems from corner cutting. Constr. Approx. 7, 195-208 (1991) · Zbl 0784.65017 · doi:10.1007/BF01888152
[79] Mongelli, P.: Total positivity properties of Jacobi-Stirling numbers. Adv. Appl. Math. 48, 354-364 (2012) · Zbl 1237.05007 · doi:10.1016/j.aam.2011.06.008
[80] Ojiro, K., Niki, H., Usui, M.: A new criterion for the H-matrix property. J. Comput. Appl. Math. 150, 293-302 (2003) · Zbl 1022.65048 · doi:10.1016/S0377-0427(02)00666-0
[81] Peña, J.M. (ed.): Shape Preserving Representations in Computer Aided Geometric Design. Nova Science Publishers, Commack (1999) · Zbl 1005.68163
[82] Peña, J.M.: B-splines and optimal stability. Math. Comput. 66, 1555-1560 (1997) · Zbl 0890.65011 · doi:10.1090/S0025-5718-97-00897-1
[83] Peña, J.M.: On the optimal stability of bases of univariate functions. Numer. Math. 91, 305-318 (2002) · Zbl 1004.65020 · doi:10.1007/s002110100327
[84] Peña, J.M.: A note on the optimal stability of bases of univariate functions. Numer. Math. 103, 151-154 (2006) · Zbl 1152.65025 · doi:10.1007/s00211-005-0660-z
[85] Peña, J.M.: LDU decompositions with L and U well conditioned. Electron. Trans. Numer. Anal. 18, 198-208 (2004) · Zbl 1083.65033
[86] Peña, J.M.: Eigenvalue bounds for some classes of P-matrices. Numer. Linear Algebra Appl. 16, 871-882 (2009) · Zbl 1224.15040 · doi:10.1002/nla.660
[87] Peña, J.M.: Tests for the recognition of total positivity. SeMA J. 62, 61-73 (2013) · Zbl 1273.65042 · doi:10.1007/s40324-013-0008-z
[88] Peña, J.M., Sauer, T.: On the multivariate Horner scheme. SIAM J. Numer. Anal. 37, 1186-1197 (2000) · Zbl 0961.65007 · doi:10.1137/S0036142997324150
[89] Peña, J.M., Sauer, T.: On the multivariate Horner scheme II: running error analysis. Computing 65, 313-322 (2000) · Zbl 0984.65006 · doi:10.1007/s006070070002
[90] Phillips, G.M.: Bernstein polynomials based on the q-integers. The heritage of P. L. Chebyshev: a Festschrift in honor of the 70th birthday of T. J. Rivlin. Ann. Numer. Math. 4, 511-518 (1997) · Zbl 0881.41008
[91] Pinkus, A.: Totally Positive Matrices. Cambridge Tracts in Mathematics, vol. 181. Cambridge University Press, Cambridge (2010) · Zbl 1185.15028
[92] Schmeltz, G.: Variationsreduzierende Kurvendarstellungen und Krümmungskriterien für Bézierflächen, Thesis, Fachbereich Mathematik, Technische Hochschule Darmstadt (1992)
[93] Schumaker, L.L., Volk, W.: Efficient evaluation of multivariate polynomials. Comput. Aided Geom. Des. 3, 149-154 (1986) · Zbl 0606.65007 · doi:10.1016/0167-8396(86)90018-X
[94] Whitney, A.M.: A reduction theorem for totally positive matrices. J. d’Analyse Math. 2, 88-92 (1952) · Zbl 0049.17104 · doi:10.1007/BF02786969
[95] Ye, Q.: Computing singular values of diagonally dominant matrices to high relative accuracy. Math. Comp. 77, 2195-2230 (2008) · Zbl 1198.65077 · doi:10.1090/S0025-5718-08-02112-1
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.