Artículo

El editor solo permite decargar el artículo en su versión post-print desde el repositorio. Por favor, si usted posee dicha versión, enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

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.

Registro:

Documento: Artículo
Título:Solving a sparse system using linear algebra
Autor:Massri, C.
Filiación:Department of Mathematics, FCEN, University of Buenos Aires, Argentina
Palabras clave:Eigenvector; Multiplication matrix; Sparse system; Toric varieties
Año:2016
Volumen:73
Página de inicio:157
Página de fin:174
DOI: http://dx.doi.org/10.1016/j.jsc.2015.06.003
Título revista:Journal of Symbolic Computation
Título revista abreviado:J. Symb. Comput.
ISSN:07477171
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_07477171_v73_n_p157_Massri

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