We present an extension of the QR method to simultaneously compute the joint eigenvalues of a finite family of commuting matrices. The problem is motivated by the task of finding solutions of a polynomial system. Several examples are included.
@article{bwmeta1.element.doi-10_2478_s11533-011-0106-z,
author = {Vanesa Cort\'es and Juan Pe\~na and Tomas Sauer},
title = {Simultaneous triangularization of commuting matrices for the solution of polynomial equations},
journal = {Open Mathematics},
volume = {10},
year = {2012},
pages = {277-291},
zbl = {1245.65041},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_2478_s11533-011-0106-z}
}
Vanesa Cortés; Juan Peña; Tomas Sauer. Simultaneous triangularization of commuting matrices for the solution of polynomial equations. Open Mathematics, Tome 10 (2012) pp. 277-291. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_2478_s11533-011-0106-z/
[1] Auzinger W., Stetter H.J., An elimination algorithm for the computation of all zeros of a system of multivariate polynomial equations, In: Numerical Mathematics, Singapore, 1988, Internat. Schriftenreihe Numer. Math., 86, Birkhäuser, Basel, 1988, 11–30 | Zbl 0658.65047
[2] Bunse-Gerstner A., Byers R., Mehrmann V., A chart of numerical methods for structured eigenvalue problems, SIAM J. Matrix Anal. Appl., 1992, 13(2), 419–453 http://dx.doi.org/10.1137/0613028 | Zbl 0757.65040
[3] Bunse-Gerstner A., Byers R., Mehrmann V., Numerical methods for simultaneous diagonalization, SIAM J. Matrix Anal. Appl., 1993, 14(), 927–949 http://dx.doi.org/10.1137/0614062 | Zbl 0786.65030
[4] Cox D., Little J., O’shea D., Ideals, Varieties and Algorithms, 2nd ed., Undergrad. Texts Math., Springer, New York, 1997
[5] Gantmacher F.R., The Theory of Matrices. II, Chelsea, New York, 1959 | Zbl 0085.01001
[6] Golub G.H, Van Loan C.F., Matrix Computations, 3rd ed., Johns Hopkins Stud. Math. Sci., Johns Hopkins University Press, Baltimore, 1996
[7] Gonzales-Vega L., Rouillier F., Roy M.-F., Symbolic recipes for polynomial system solving, In: Some Tapas in Computer Algebra, Algorithms Comput. Math., 4, Springer, Berlin, 1999, 34–65 | Zbl 0966.13020
[8] Melenk H., Möller H.M., Neun W., Symbolic solution of large stationary chemical kinetics problems, Impact Comput. Sci. Engrg., 1989, 1(2), 138–167 http://dx.doi.org/10.1016/0899-8248(89)90027-X | Zbl 0704.65039
[9] Moler C., The QR algorithm, Cleve’s Corner, Mathworks Newsletters, 1995, available at www.mathworks.com/company/newsletters/news_notes/pdf/sum95cleve.pdf
[10] Möller H.M., Sauer T., H-bases I: The foundation, In: Curve and Surface Fitting, Saint-Malo, 1999, Innov. Appl. Math., Vanderbilt University Press, Nashville, 2000, 325–332
[11] Möller H.M., Sauer, T., H-bases II: Application to numerical problems, In: Curve and Surface Fitting, Saint-Malo, 1999, Innov. Appl. Math., Vanderbilt University Press, Nashville, 2000, 333–342
[12] Möller H.M., Sauer T., H-bases for polynomial interpolation and system solving, Adv. Comput. Math., 2000, 12(4), 335–362 http://dx.doi.org/10.1023/A:1018937723499 | Zbl 0943.65059
[13] Möller H.M., Stetter H.J., Multivariate polynomial equations with multiple zeros solved by matrix eigenproblems, Numer. Math., 1995, 70(3), 311–329 http://dx.doi.org/10.1007/s002110050122 | Zbl 0851.65029
[14] Möller H.M., Tenberg R., Multivariate polynomial system solving using intersections of eigenspaces, J. Symbolic Comput., 2001, 32(5), 513–531 http://dx.doi.org/10.1006/jsco.2001.0476 | Zbl 1084.65523
[15] Peña J.M., A class of P-matrices with applications to the localization of the eigenvalues of a real matrix, SIAM J. Matrix Anal. Appl., 2001, 22(4), 1027–1037 http://dx.doi.org/10.1137/S0895479800370342 | Zbl 0986.15015
[16] Peña J.M., On an alternative to Gerschgorin circles and ovals of Cassini, Numer. Math., 2003, 95(2), 337–345 http://dx.doi.org/10.1007/s00211-002-0427-8 | Zbl 1032.15014
[17] Sauer T., Polynomial interpolation in several variables: lattices, differences, and ideals, In: Topics in Multivariate Approximation and Interpolation, Stud. Comput. Math., 12, Elsevier, Amsterdam, 2006, 191–230 http://dx.doi.org/10.1016/S1570-579X(06)80009-1 | Zbl 1205.41004
[18] Sauer T., Wagenführ D., Polynomial systems, H-bases, and an application from kinematic transforms, In: Ninth International Conference Zaragoza-Pau on Applied Mathematics and Statistics, Monogr. Semin. Mat. García Galdeano, 33, Prensas Univ. Zaragoza, Zaragoza, 2006, 185–196 | Zbl 1115.65333
[19] Scott D.S., On the accuracy of the Gerschgorin circle theorem for bounding the spread of a real symmetric matrix, Linear Algebra Appl., 1985, 65, 147–155 http://dx.doi.org/10.1016/0024-3795(85)90093-X
[20] Stetter H.J., Matrix eigenproblems at the heart of polynomial system solving, SIGSAM Bull., 1996, 30(4), 22–25 http://dx.doi.org/10.1145/242961.242966 | Zbl 1097.65530
[21] Trefethen L.N, Bau D. III, Numerical Linear Algebra, SIAM, Philadelphia, 1997 http://dx.doi.org/10.1137/1.9780898719574
[22] Wilkinson J.H., The Algebraic Eigenvalue Problem, Clarendon Press, Oxford, 1965 | Zbl 0258.65037