×

zbMATH — the first resource for mathematics

Dixon-EDF: the premier method for solution of parametric polynomial systems. (English) Zbl 1393.68192
Kotsireas, Ilias S. (ed.) et al., Applications of computer algebra, Kalamata, Greece, July 20–23, 2015. Cham: Springer (ISBN 978-3-319-56930-7/hbk; 978-3-319-56932-1/ebook). Springer Proceedings in Mathematics & Statistics 198, 237-256 (2017).
Summary: Using examples of interest from real problems, we will discuss the Dixon-EDF resultant as a method of solving parametric polynomial systems. We will briefly describe the method itself, then discuss problems arising in geometric computing, flexibility of structures, pose estimation, robotics, image analysis, physics, differential equations, and others. We will compare Dixon-EDF to several respected implementations of Gröbner bases algorithms on several systems. We find that Dixon-EDF is greatly superior, usually by orders of magnitude, in both CPU usage and RAM usage.
For the entire collection see [Zbl 1379.13001].

MSC:
68W30 Symbolic computation and algebraic computation
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
13P15 Solving polynomial systems; resultants
Software:
Fermat; Maple
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 1. Bricard, R.: Mémoire sur la théorie de l’octaèdre articulé. J. Math. Pures Appl. 3, pp. 113-150 (1897). (English translation: · JFM 28.0624.01
[2] 2. Carrà-Ferro, G.: A resultant theory for the systems of two ordinary algebraic differential equations. Appl. Algebra Eng. Commun. Comput. 8 , 539-560 (1997) · Zbl 0999.12008
[3] 3. Connelly, R., Sabitov, I., Walz, A.: The bellows conjecture. Contrib. Algebra Geom. 38 , 1-10 (1997) · Zbl 0939.52009
[4] 4. Coutsias, E., Seok, C., Jacobson, M.P., Dill, K.A.: A kinematic view of loop closure. J. Comput. Chem. 25 (4), 510-528 (2004)
[5] 5. Coutsias, E., Seok, C., Wester, M.J., Dill, K.A.: Resultants and loop closure. Int. J. Quantum Chem. 106 (1), 176-189 (2005) · Zbl 1188.68262
[6] 6. Cox, D., Little, J., O’Shea, D.: Using Algebraic Geometry. Graduate Texts in Mathematics, vol. 185. Springer, New York (1998)
[7] 7. Dixon, A.L.: The eliminant of three quantics in two independent variables. Proc. Lond. Math. Soc. 6 , 468-478 (1908) · JFM 39.0219.02
[8] 8. Faugere, J.-C.: A new efficient algorithm for computing Gröbner bases (F4). J. Pure Appl. Algebra 139 , 61-88 (1999) · Zbl 0930.68174
[9] 9. Faugere, J.-C.: Personal communication, July 8 (2014)
[10] 10. Gentleman, W., Johnson, S.: The evaluation of determinants by expansion by minors and the general problem of substitution. Math. Comput. 28 (126), 543-548 (1974) · Zbl 0278.65031
[11] 11. Lewis, R.H.: Computer algebra system Fermat.
[12] 12. Lewis, R.H.: Fermat code for Dixon-EDF.
[13] 13. Lewis, R.H.: Heuristics to accelerate the Dixon resultant. Math. Comput. Simul. 77 (4), 400-407 (2008) · Zbl 1138.65037
[14] 14. Lewis, R., Bridgett, S.: Conic tangency equations arising from Apollonius problems in biochemistry. Math. Comput. Simul. 61 (2), 101-114 (2003) · Zbl 1016.51014
[15] 15. Lewis, R.H., Coutsias,E.A.: Algorithmic search for flexibility using resultants of polynomial systems. In: Automated Deduction in Geometry, 6th International Workshop, ADG, 2006. LNCS. Springer. 4869 , 68-79 (2007) · Zbl 1195.68115
[16] 16. Lewis, R.H., Coutsias, E.A.: Flexibility of Bricard’s Linkages and Other Structures via Resultants and Computer Algebra. Math. Comput. Simul. (2014).
[17] 17. Lewis, R.H., Stiller, Peter: Solving the recognition problem for six lines using the Dixon resultant. Math. Comput. Simul. 49 , 203-219 (1999)
[18] 18. Nachtwey, P.: Delta Computer Systems, personal communication (2009)
[19] 19. Palancz, B., Lewis, R.H., Zaletnyik, P., Awange, J.: Computational study of the 3D affine transformation part I. 3-point problem (2008).
[20] 20. Palancz, B., Awange, J., Zaletnyik, P., Lewis, R.H.: Linear homotopy solution of nonlinear systems of equations in geodesy. J. Geod. (2009).
[21] 21. Post to reddit (2014).
[22] 22. Ritt, J.F.: Differential Equations from the Algebraic Standpoint, College Publications 14. American Mathematical Society, New York (1932)
[23] 23. Steel, A.: Personal communications, September 2-7 (2015)
[24] 24. Sturmfels, B.: Solving systems of polynomial equations. In: CBMS Regional Conference Series in Mathematics 97 (2003). American Mathematical Society, Providence · Zbl 1101.13040
[25] 25. Thorpe, M., Lei, M., Rader, A.J., Jacobs, D.J., Kuhn, L.: Protein flexibility and dynamics using constraint theory. J. Mol. Gr. Model. 19 , 60-69 (2001)
[26] 26. Tot, J.: Spinning double
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.