Multilinear Polynomial Systems: Root Isolation and Bit Complexity

Autor: Ioannis Z. Emiris, Angelos Mantzaflaris, Elias P. Tsigaridas

Publikováno v: Journal of Symbolic Computation
Journal of Symbolic Computation, Elsevier, 2021, Special Issue on Milestones in Computer Algebra (MICA 2016), 105, pp.145-164. ⟨10.1016/j.jsc.2020.06.005⟩
Journal of Symbolic Computation, 2021, Special Issue on Milestones in Computer Algebra (MICA 2016), 105, pp.145-164. ⟨10.1016/j.jsc.2020.06.005⟩

We exploit structure in polynomial system solving by considering polynomials that are linear in subsets of the variables. We focus on algorithms and their Boolean complexity for computing isolating hyperboxes for all the isolated complex roots of wel

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6b0c3ba776bf65a2a45b8ab0d8fc0334
https://hal.inria.fr/hal-02099556

Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.

Sparse Rational Univariate Representation

Autor: Angelos Mantzaflaris, Elias P. Tsigaridas, Éric Schost

Publikováno v: ISSAC 2017-International Symposium on Symbolic and Algebraic Computation
ISSAC 2017-International Symposium on Symbolic and Algebraic Computation, Jul 2017, Kaiserslautern, Germany. pp.8, ⟨10.1145/3087604.3087653⟩
ISSAC

International audience; We present explicit worst case degree and height bounds for the rational univariate representation of the isolated roots of polynomial systems based on mixed volume. We base our estimations on height bounds of resultants and w

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::483364fcc71ea41a4760c562b22d3a88
https://inria.hal.science/hal-01528377/document

The DMM bound: multivariate (aggregate) separation bounds

Autor: Bernard Mourrain, Elias P. Tsigaridas, Ioannis Z. Emiris

Publikováno v: Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation
Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation, Jul 2010, Munich, Germany. pp.243-250, ⟨10.1145/1837934.1837981⟩
Emiris, I Z, Mourrain, B & Tsigaridas, E 2010, ' The DMM Bound : Multivariate (Aggregrate) Separation Bounds ', International Symposium on Symbolic and Algebraic Computation, pp. 243-250 . https://doi.org/10.1145/1837934.1837981
ISSAC

Best paper award; International audience; In this paper we derive aggregate separation bounds, named after Davenport-Mahler-Mignotte (\dmm), on the isolated roots of polynomial systems, specifically on the minimum distance between any two such roots.

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5139a826d30129dbedd94d626603c5cd
http://arxiv.org/abs/1005.5610

A note on the complexity of univariate root isolation

Autor: Emiris, Ioannis, Tsigaridas, Elias P.

Publikováno v: [Research Report] RR-6043, INRIA. 2006, pp.18

This paper presents the average-case bit complexity of subdivision-based univariate solvers, namely those named after Sturm, Descartes, and Bernstein. By real solving we mean real root isolation. We prove bounds of $\sOB(N^5)$ for all methods, where

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=dedup_wf_001::aa518dfa438abb1663c61985a67e391c
https://hal.inria.fr/inria-00116985v5/document