Abstract:
We give a new theoretical tool to solve sparse systems with finitely many solutions. It is based on toric varieties and basic linear algebra; eigenvalues, eigenvectors and coefficient matrices. We adapt Eigenvalue theorem and Eigenvector theorem to work with a canonical rectangular matrix (the first Koszul map) and prove that these new theorems serve to solve overdetermined sparse systems and to count the expected number of solutions. © 2015 Elsevier Ltd.
Referencias:
- Apostol, T.M., (1974) Mathematical Analysis, , Addison-Wesley Publishing Co., Reading, Mass., London, Don Mills, Ont
- Auzinger, W., Stetter, H.J., An elimination algorithm for the computation of all zeros of a system of multivariate polynomial equations (1988) Internat. Schriftenreihe Numer. Math., 86, pp. 11-30. , Birkhäuser, Basel, Numerical Mathematics
- Bernstein, D.N., The number of roots of a system of equations (1975) Funkc. Anal. Prilozh., 9 (3), pp. 1-4
- Bondyfalat, D., Mourrain, B., Pan, V.Y., Computation of a specified root of a polynomial system of equations using eigenvectors (2000) Linear Algebra Appl., 319 (1-3), pp. 193-209. , 10.1016/S0024-3795(00)00190-7
- Canny, J., Generalised characteristic polynomials (1990) J. Symb. Comput., 9 (3), pp. 241-250. , 10.1016/S0747-7171(08)80012-0
- Canny, J., Emiris, I., An efficient algorithm for the sparse mixed resultant (1993) Lecture Notes Comput. Sci., 673, pp. 89-104. , Springer, Berlin.10.1007/3-540-56686-46
- Canny, J.F., Emiris, I.Z., A subdivision-based algorithm for the sparse resultant (2000) J. ACM, 47 (3), pp. 417-451. , 10.1145/337244.337247
- Corless, R.M., Gianni, P.M., Trager, B.M., A reordered Schur factorization method for zero-dimensional polynomial systems with multiple roots (1997) Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, pp. 133-140. , ACM, New York, (electronic) 10.1145/258726.258767
- Cox, D.A., Little, J.B., Schenck, H.K., Toric Varieties (2011) Graduate Studies in Mathematics, 124. , American Mathematical Society, Providence, RI
- Daney, D., Emiris, I.Z., Robust parallel robot calibration with partial information (2001) IEEE International Conference, 4, pp. 3262-3267
- De Loera, J.A., The many aspects of counting lattice points in polytopes (2005) Math. Semesterber., 52 (2), pp. 175-195. , 10.1007/s00591-005-0094-9
- Dickenstein, A., Emiris, I.Z., Multihomogeneous resultant formulae by means of complexes (2003) J. Symb. Comput., 36 (3-4), pp. 317-342. , 10.1016/S0747-7171(03)00086-5
- Solving polynomial equations. Foundations, Algorithms, and Applications (2005) Algorithms and Computation in Mathematics, 14. , Springer-Verlag, Berlin, A. Dickenstein, I.Z. Emiris (Eds.)
- Elkadi, M., Mourrain, B., Introduction à la résolution des systèmes polynomiaux (2007) Mathématiques and Applications (Berlin), 59. , Springer, Berlin.10.1007/978-3-540-71647-1
- Emiris, I.Z., (1994) Sparse elimination and applications in kinematics, , PhD thesis, UC Berkeley
- Emiris, I.Z., On the complexity of sparse elimination (1996) J. Complex., 12 (2), pp. 134-166. , 10.1006/jcom.1996.0010
- Emiris, I.Z., A general solver based on sparse resultants: numerical issues and kinematic applications, , http://hal.inria.fr/inria-00073580, Tech. Rep. RR-3110, INRIA
- Emiris, I.Z., Matrix methods for solving algebraic systems (2001) Symbolic Algebraic Methods and Verification Methods, pp. 69-78. , Springer, Vienna
- Emiris, I.Z., Canny, J.F., Efficient incremental algorithms for the sparse resultant and the mixed volume (1995) J. Symb. Comput., 20 (2), pp. 117-149. , 10.1006/jsco.1995.1041
- Emiris, I.Z., Mourrain, B., Computer algebra methods for studying and computing molecular conformations (1999) Algorithmica, 25 (2-3), pp. 372-402. , 10.1007/PL00008283
- Emiris, I.Z., Mourrain, B., Matrices in elimination theory (1999) J. Symb. Comput., 28 (1-2), pp. 3-44. , 10.1006/jsco.1998.0266
- Emiris, I.Z., Rege, A., Monomial bases and polynomial system solving (extended abstract) (1994) Proceedings of the International Symposium on Symbolic and Algebraic Computation, pp. 114-122. , ACM, New York, NY, USA. 10.1145/190347.190374
- Fulton, W., Introduction to Toric Varieties (1993) Annals of Mathematics Studies, 131. , Princeton University Press, Princeton, NJ, the William H. Roever Lectures in Geometry
- Gel'fand, I.M., Kapranov, M.M., Zelevinsky, A.V., Discriminants, Resultants, and Multidimensional Determinants (1994) Mathematics: Theory and Applications, , Birkhäuser Boston Inc., Boston, MA. 10.1007/978-0-8176-4771-1
- Graillat, S., Trébuchet, P., A new algorithm for computing certified numerical approximations of the roots of a zero-dimensional system (2009) ISSAC 2009-Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation, pp. 167-173. , ACM, New York. 10.1145/1576702.1576727
- Hafner, J.L., McCurley, K.S., Asymptotically fast triangularization of matrices over rings (1991) SIAM J. Comput., 20 (6), pp. 1068-1083. , 10.1137/0220067
- Hartshorne, R., Algebraic Geometry (1977) Graduate Texts in Mathematics, 52. , Springer-Verlag, New York
- Helmberg, G., Wagner, P., Veltkamp, G., On Faddeev-Leverrier's methods for the computation of the characteristic polynomial of a matrix and of eigenvectors (1993) Linear Algebra Appl., 185, pp. 219-233. , 10.1016/0024-3795(93)90214-9
- Jouanolou, J.-P., Le formalisme du résultant (1991) Adv. Math., 90 (2), pp. 117-263. , 10.1016/0001-8708(91)90031-2
- Kapranov, M.M., Sturmfels, B., Zelevinsky, A.V., Chow polytopes and general resultants (1992) Duke Math. J., 67 (1), pp. 189-218. , 10.1215/S0012-7094-92-06707-X
- Lazard, D., Résolution des systèmes d'équations algébriques (1981) Theor. Comput. Sci., 15 (1), pp. 77-110. , 10.1016/0304-3975(81)90064-5
- Lim, L.-H., Singular values and eigenvalues of tensors: a variational approach (2005) Computational Advances in Multi-Sensor Adaptive Processing, 2005 1st IEEE International Workshop, pp. 129-132
- Macaulay, F.S., Some formulae in elimination (1902) Proc. Lond. Math. Soc., S1-35 (1), p. 3. , 10.1112/plms/s1-35.1.3
- Massri, C., An algorithm to find a maximum of a multilinear map over a product of spheres (2013) J. Approx. Theory, 166, pp. 19-41. , 10.1016/j.jat.2012.09.007
- Mayer, G., Result verification for eigenvectors and eigenvalues (1994) Stud. Comput. Math., 5, pp. 209-276. , North-Holland, Amsterdam
- McNamee, J.M., A 2002 update of the supplementary bibliography on roots of polynomials (2002) J. Comput. Appl. Math., 142 (2), pp. 433-434. , 10.1016/S0377-0427(01)00546-5
- Möller, H.M., Stetter, H.J., Multivariate polynomial equations with multiple zeros solved by matrix eigenproblems (1995) Numer. Math., 70 (3), pp. 311-329. , 10.1007/s002110050122
- Morgan, A., Sommese, A., Computing all solutions to polynomial systems using homotopy continuation (1987) Appl. Math. Comput., 24 (2), pp. 115-138. , 10.1016/0096-3003(87)90064-6
- Mourrain, B., The 40 "generic" positions of a parallel robot (1993) Proceedings of the 1993 International Symposium on Symbolic and Algebraic Computation, pp. 173-182. , ACM, New York, NY, USA. 10.1145/164081.164120
- Mourrain, B., Computing the isolated roots by matrix methods (1998) J. Symb. Comput., 26 (6), pp. 715-738. , 10.1006/jsco.1998.0236
- Mourrain, B., An introduction to algebraic methods for solving polynomial equations (2006) Verh. Afd. Natuurkd. 1. Reeks. K. Ned. Akad. Wet. R. Neth. Acad., 53, pp. 49-94. , Arts Sci, Amsterdam
- Mourrain, B., Pan, V.Y., Multivariate polynomials, duality, and structured matrices (2000) J. Complex., 16 (1), pp. 110-180. , 10.1006/jcom.1999.0530
- Oishi, S., Fast enclosure of matrix eigenvalues and singular values via rounding mode controlled computation (2001) Linear Algebra Appl., 324 (1-3), pp. 133-146. , 10.1016/S0024-3795(00)00272-X
- Ozaki, K., Ogita, T., Rump, S.M., Oishi, S., Fast algorithms for floating-point interval matrix multiplication (2012) J. Comput. Appl. Math., 236 (7), pp. 1795-1814. , 10.1016/j.cam.2011.10.011
- Pedersen, P., Sturmfels, B., Product formulas for resultants and Chow forms (1993) Math. Z., 214 (3), pp. 377-396. , 10.1007/BF02572411
- Rouillier, F., Zimmermann, P., Efficient isolation of polynomial's real roots (2004) Proceedings of the International Conference on Linear Algebra and Arithmetic, 162, pp. 33-50. , 10.1016/j.cam.2003.08.015
- Rump, S.M., Fast and parallel interval arithmetic (1999) BIT, 39 (3), pp. 534-554. , 10.1023/A:1022374804152
- Rump, S.M., Computational error bounds for multiple or nearly multiple eigenvalues (2001) Linear Algebra Appl., 324 (1-3), pp. 209-226. , 10.1016/S0024-3795(00)00279-2
- Rump, S.M., Zemke, J.-P.M., On eigenvector bounds (2003) BIT, 43 (4), pp. 823-837. , 10.1023/B:BITN.0000009941.51707.26
- Sombra, M., A sparse effective Nullstellensatz (1999) Adv. Appl. Math., 22 (2), pp. 271-295. , 10.1006/aama.1998.0633
- Yamamoto, T., Error bounds for computed eigenvalues and eigenvectors. II (1982) Numer. Math., 40 (2), pp. 201-206. , 10.1007/BF01400539
Citas:
---------- APA ----------
(2016)
. Solving a sparse system using linear algebra. Journal of Symbolic Computation, 73, 157-174.
http://dx.doi.org/10.1016/j.jsc.2015.06.003---------- CHICAGO ----------
Massri, C.
"Solving a sparse system using linear algebra"
. Journal of Symbolic Computation 73
(2016) : 157-174.
http://dx.doi.org/10.1016/j.jsc.2015.06.003---------- MLA ----------
Massri, C.
"Solving a sparse system using linear algebra"
. Journal of Symbolic Computation, vol. 73, 2016, pp. 157-174.
http://dx.doi.org/10.1016/j.jsc.2015.06.003---------- VANCOUVER ----------
Massri, C. Solving a sparse system using linear algebra. J. Symb. Comput. 2016;73:157-174.
http://dx.doi.org/10.1016/j.jsc.2015.06.003