Mixed cell computation in Hom4PS-3. (March 2017)

• Record Type: Journal Article
• Authors: Chen, Tianran; Lee, Tsung-Lin; Li, Tien-Yien
• Is Part Of: Journal of symbolic computation. Volume 79:Part 3(2017)
• Page Start: 516
• Page End: 534
• Publication Date: 2017-03
• Subjects: Mixed volume -- Mixed cells -- Polyhedral homotopy -- Polynomial system -- Parallel computing; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2016.07.017
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: This article presents recent efforts in improving the efficiency and scalability of the mixed cell computation step in the context of the Polyhedral Homotopy method. Solving systems of polynomial equations is an important problem in applied mathematics. The Polyhedral Homotopy method is an important numerical method for this task. In this method, a necessary preprocessing step, known as the "mixed cell computation" problem has been the main bottleneck in the parallel efficiency and scalability. This article presents recent remarkable improvements in the parallel scalability of the algorithm that are applicable to a wide range of hardware architectures including multi-core systems, NUMA systems, computer clusters, and GPUs devices.