Abstract
We consider the problem of tracking one solution path defined by a polynomial homotopy on a parallel shared memory computer. Our robust path tracker applies Newton’s method on power series to locate the closest singular parameter value. On top of that, it computes singular values of the Hessians of the polynomials in the homotopy to estimate the distance to the nearest different path. Together, these estimates are used to compute an appropriate adaptive step size. For n-dimensional problems, the cost overhead of our robust path tracker is O(n), compared to the commonly used predictor-corrector methods. This cost overhead can be reduced by a multithreaded program on a parallel shared memory computer.
M. Van Barel—Supported by the Research Council KU Leuven, C1-project (Numerical Linear Algebra and Polynomial Computations), and by the Fund for Scientific Research–Flanders (Belgium), G.0828.14N (Multivariate polynomial and rational interpolation and approximation), and EOS Project no 30468160.
J. Verschelde—Supported by the National Science Foundation under grant DMS 1854513.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Adrovic, D., Verschelde, J.: Polyhedral methods for space curves exploiting symmetry applied to the cyclic n-roots problem. In: Gerdt, V.P., Koepf, W., Mayr, E.W., Vorozhtsov, E.V. (eds.) CASC 2013. LNCS, vol. 8136, pp. 10–29. Springer, Cham (2013). https://doi.org/10.1007/978-3-319-02297-0_2
Backelin, J.: Square multiples n give infinitely many cyclic n-roots. Reports, Matematiska Institutionen 8, Stockholms universitet (1989)
Bates, D.J., Hauenstein, J.D., Sommese, A.J., Wampler, C.W.: Adaptive multiprecision path tracking. SIAM J. Numer. Anal. 46(2), 722–746 (2008)
Bates, D.J., Hauenstein, J.D., Sommese, A.J., Wampler, C.W.: Numerically Solving Polynomial Systems with Bertini, vol. 25. SIAM (2013)
Bliss, N., Verschelde, J.: The method of Gauss-Newton to compute power series solutions of polynomial homotopies. Linear Algebra Appl. 542, 569–588 (2018)
Breiding, P., Timme, S.: HomotopyContinuation.jl: a package for homotopy continuation in Julia. In: Davenport, J.H., Kauers, M., Labahn, G., Urban, J. (eds.) ICMS 2018. LNCS, vol. 10931, pp. 458–465. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96418-8_54
Christianson, B.: Automatic Hessians by reverse accumulation. IMA J. Numer. Anal. 12, 135–150 (1992)
Davenport, J.H.: Looking at a set of equations. Bath Computer Science Technical report 87–06 (1987)
Fabry, E.: Sur les points singuliers d’une fonction donnée par son développement en série et l’impossibilité du prolongement analytique dans des cas très généraux. In: Annales scientifiques de l’École Normale Supérieure, vol. 13, pp. 367–399. Elsevier (1896)
Führ, H., Rzeszotnik, Z.: On biunimodular vectors for unitary matrices. Linear Algebra Appl. 484, 86–129 (2015)
Griewank, A., Walther, A.: Evaluating derivatives: principles and techniques of algorithmic differentiation, vol. 105. SIAM (2008)
Hida, Y., Li, X.S., Bailey, D.H.: Algorithms for quad-double precision floating point arithmetic. In: The Proceedings of the 15th IEEE Symposium on Computer Arithmetic (Arith-15 2001), pp. 155–162. IEEE Computer Society (2001)
Jeronimo, G., Matera, G., Solernó, P., Waissbein, A.: Deformation techniques for sparse systems. Found. Comput. Math. 9, 1–50 (2009)
Katsura, S.: Spin glass problem by the method of integral equation of the effective field. In: Coutinho-Filho, M., Resende, S. (eds.) New Trends in Magnetism, pp. 110–121. World Scientific, London (1990)
Li, T., Tsai, C.: HOM4PS-2.0para: Parallelization of HOM4PS-2.0 for solving polynomial systems. Parallel Comput. 35(4), 226–238 (2009)
McCormick, J.W., Singhoff, F., Hugues, J.: Building Parallel, Embedded, and Real-Time Applications with Ada. Cambridge University Press, Cambridge (2011)
Sommese, A.J., Verschelde, J.: Numerical homotopies to compute generic points on positive dimensional algebraic sets. J. Complexity 16(3), 572–602 (2000)
Telen, S., Van Barel, M., Verschelde, J.: A robust numerical path tracking algorithm for polynomial homotopy continuation. arXiv:1909.04984
Trias, A.: The holomorphic embedding load flow method. In: 2012 IEEE Power and Energy Society General Meeting, pp. 1–8. IEEE (2012)
Trias, A., Martin, J.L.: The holomorphic embedding loadflow method for DC power systems and nonlinear DC circuits. IEEE Trans. Circuits Syst. 63(2), 322–333 (2016)
Verschelde, J.: Algorithm 795: PHCpack: a general-purpose solver for polynomial systems by homotopy continuation. ACM Trans. Math. Softw. (TOMS) 25(2), 251–276 (1999)
Verschelde, J.: A blackbox polynomial system solver on parallel shared memory computers. In: Gerdt, V.P., Koepf, W., Seiler, W.M., Vorozhtsov, E.V. (eds.) CASC 2018. LNCS, vol. 11077, pp. 361–375. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-99639-4_25
Verschelde, J., Yu, X.: Accelerating polynomial homotopy continuation on a graphics processing unit with double double and quad double arithmetic. In: Proceedings of the 7th International Workshop on Parallel Symbolic Computation (PASCO 2015), pp. 109–118. ACM (2015)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Telen, S., Van Barel, M., Verschelde, J. (2020). Robust Numerical Tracking of One Path of a Polynomial Homotopy on Parallel Shared Memory Computers. In: Boulier, F., England, M., Sadykov, T.M., Vorozhtsov, E.V. (eds) Computer Algebra in Scientific Computing. CASC 2020. Lecture Notes in Computer Science(), vol 12291. Springer, Cham. https://doi.org/10.1007/978-3-030-60026-6_33
Download citation
DOI: https://doi.org/10.1007/978-3-030-60026-6_33
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-60025-9
Online ISBN: 978-3-030-60026-6
eBook Packages: Computer ScienceComputer Science (R0)