@inproceedings{IPY+2019,
author = {Imbach, R{\'e}mi
and Pan, Victor Y.
and Yap, Chee
and Kotsireas, Ilias S.
and Zaderman, Vitaly},
editor = {England, Matthew
and Koepf, Wolfram
and Sadykov, Timur M.
and Seiler, Werner M.
and Vorozhtsov, Evgenii V.},
title = {Root-Finding with Implicit Deflation},
booktitle = {Computer Algebra in Scientific Computing},
year = {2019},
publisher = {Springer International Publishing},
address = {Cham},
pages = {236--245},
abstract = {Functional iterations such as Newton's are a popular tool for polynomial root-finding. We consider realistic situation where some (e.g., better-conditioned) roots have already been approximated and where further computations is directed to the approximation of the remaining roots. Such a situation is also realistic for root by means of subdivision iterations. A natural approach of applying explicit deflation has been much studied and recently advanced by one of the authors of this paper, but presently we consider the alternative of implicit deflation combined with the mapping of the variable and reversion of an input polynomial. We also show another unexplored direction for substantial further progress in this long and extensively studied area. Namely we dramatically increase the local efficiency of root-finding by means of the incorporation of fast algorithms for multipoint polynomial evaluation and Fast Multipole Method.},
isbn = {978-3-030-26831-2},
url = {https://link.springer.com/chapter/10.1007/978-3-030-26831-2_16}
}
@inproceedings{IM2023,
author = {Imbach, R\'{e}mi and Moroz, Guillaume},
title = {Fast evaluation and root finding for polynomials with floating-point coefficients},
year = {2023},
isbn = {9798400700392},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3597066.3597112},
doi = {10.1145/3597066.3597112},
abstract = {Evaluating or finding the roots of a polynomial f(z) = f0 + ⋅⋅⋅ + fdzd with floating-point number coefficients is a ubiquitous problem. By using a piecewise approximation of f obtained with a careful use of the Newton polygon of f, we improve state-of-the-art upper bounds on the number of operations to evaluate and find the roots of a polynomial. In particular, if the coefficients of f are given with m significant bits, we provide for the first time an algorithm that finds all the roots of f with a relative condition number lower than 2m, using a number of bit operations quasi-linear in the bit-size of the floating-point representation of f. Notably, our new approach handles efficiently polynomials with coefficients ranging from 2− d to 2d, both in theory and in practice.},
booktitle = {Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation},
pages = {325–334},
numpages = {10},
location = {, Troms\o{}, Norway, },
series = {ISSAC '23}
}
@inproceedings{IP2022,
title = {Accelerated Subdivision for Clustering Roots of Polynomials Given by Evaluation Oracles},
author = {Imbach, R{\'e}mi and Pan, Victor Y},
booktitle = {Computer Algebra in Scientific Computing: 24th International Workshop, CASC 2022, Gebze, Turkey, August 22--26, 2022, Proceedings},
pages = {143--164},
year = {2022},
organization = {Springer}
}
@inproceedings{IP2021,
title = {Root radii and subdivision for polynomial root-finding},
author = {Imbach, R{\'e}mi and Pan, Victor Y},
booktitle = {Computer Algebra in Scientific Computing: 23rd International Workshop, CASC 2021, Sochi, Russia, September 13--17, 2021, Proceedings 23},
pages = {136--156},
year = {2021},
organization = {Springer}
}
@article{IPY2021,
title = {Clustering Complex Zeros of Triangular Systems of Polynomials},
author = {Imbach, R{\'e}mi and Pouget, Marc and Yap, Chee},
journal = {Mathematics in Computer Science},
volume = {15},
number = {2},
pages = {271--292},
year = {2021},
publisher = {Springer},
url = {https://doi.org/10.1007/s11786-020-00482-0}
}
@inproceedings{IP2019,
author = {Imbach, R{\'e}mi
and Pan, Victor Y.},
editor = {Slamanig, Daniel
and Tsigaridas, Elias
and Zafeirakopoulos, Zafeirakis},
title = {New Practical Advances in Polynomial Root Clustering},
booktitle = {Mathematical Aspects of Computer and Information Sciences},
year = {2020},
publisher = {Springer International Publishing},
address = {Cham},
pages = {122--137},
abstract = {We report an ongoing work on clustering algorithms for complex roots of a univariate polynomial p of degree d with real or complex coefficients. As in their previous best subdivision algorithms our root-finders are robust even for multiple roots of a polynomial given by a black box for the approximation of its coefficients, and their complexity decreases at least proportionally to the number of roots in a region of interest (ROI) on the complex plane, such as a disc or a square, but we greatly strengthen the main ingredient of the previous algorithms. We build the foundation for a new counting test that essentially amounts to the evaluation of a polynomial p and its derivative {\$}{\$}p'{\$}{\$}, which is a major benefit, e.g., for sparse polynomials p. Moreover with evaluation at about {\$}{\$}{\backslash}log (d){\$}{\$}points (versus the previous record of order d) we output correct number of roots in a disc whose contour has no roots of p nearby. Our second and less significant contribution concerns subdivision algorithms for polynomials with real coefficients. Our tests demonstrate the power of the proposed algorithms.},
isbn = {978-3-030-43120-4}
}
@inproceedings{IP2020,
author = {Imbach, R\'{e}mi and Pan, Victor Y.},
title = {New Progress in Univariate Polynomial Root Finding},
year = {2020},
isbn = {9781450371001},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3373207.3404063},
doi = {10.1145/3373207.3404063},
booktitle = {Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation},
pages = {249–256},
numpages = {8},
keywords = {subdivision, polynomial root finding, root counting},
location = {Kalamata, Greece},
series = {ISSAC ’20}
}
@inproceedings{IPY2018,
author = {Imbach, R{\'e}mi
and Pan, Victor Y.
and Yap, Chee},
editor = {Davenport, James H.
and Kauers, Manuel
and Labahn, George
and Urban, Josef},
title = {Implementation of a Near-Optimal Complex Root Clustering Algorithm},
booktitle = {Mathematical Software -- ICMS 2018},
year = {2018},
publisher = {Springer International Publishing},
address = {Cham},
pages = {235--244},
abstract = {We describe Ccluster, a software for computing natural {\$}{\$}{\backslash}varepsilon {\$}{\$}$\epsilon$-clusters of complex roots in a given box of the complex plane. This algorithm from Becker et al. (2016) is near-optimal when applied to the benchmark problem of isolating all complex roots of an integer polynomial. It is one of the first implementations of a near-optimal algorithm for complex roots. We describe some low level techniques for speeding up the algorithm. Its performance is compared with the well-known MPSolve library and Maple.},
isbn = {978-3-319-96418-8}
}
@article{IMP2018,
title = {Reliable Location with Respect to the Projection of a Smooth Space Curve},
journal = {Reliable Computing},
volume = {26},
number = {},
pages = {13 - 55},
year = {2018},
url = {https://interval.louisiana.edu/reliable-computing-journal/tables-of-contents.html#Volume_26},
author = {R{\'e}mi Imbach and Guillaume Moroz and Marc Pouget}
}
@article{IMP2017,
title = {A certified numerical algorithm for the topology of resultant and discriminant curves },
journal = {Journal of Symbolic Computation },
volume = {80, Part 2},
number = {},
pages = {285 - 306},
year = {2017},
note = {},
issn = {0747-7171},
doi = {http://dx.doi.org/10.1016/j.jsc.2016.03.011},
url = {http://www.sciencedirect.com/science/article/pii/S0747717116300128},
author = {R{\'e}mi Imbach and Guillaume Moroz and Marc Pouget},
keywords = {Topology of algebraic curves},
keywords = {Resultant},
keywords = {Discriminant},
keywords = {Subresultant},
keywords = {Numerical algorithm},
keywords = {Singularities},
keywords = {Interval arithmetic},
keywords = {Node and cusp singularities },
abstract = {Abstract Let C be a real plane algebraic curve defined by the resultant of two polynomials (resp. by the discriminant of a polynomial). Geometrically such a curve is the projection of the intersection of the surfaces P ( x , y , z ) = Q ( x , y , z ) = 0 (resp. P ( x , y , z ) = ∂ P ∂ z ( x , y , z ) = 0 ), and generically its singularities are nodes (resp. nodes and ordinary cusps). State-of-the-art numerical algorithms compute the topology of smooth curves but usually fail to certify the topology of singular ones. The main challenge is to find practical numerical criteria that guarantee the existence and the uniqueness of a singularity inside a given box B, while ensuring that B does not contain any closed loop of C . We solve this problem by first providing a square deflation system, based on subresultants, that can be used to certify numerically whether B contains a unique singularity p or not. Then we introduce a numeric adaptive separation criterion based on interval arithmetic to ensure that the topology of C in B is homeomorphic to the local topology at p. Our algorithms are implemented and experiments show their efficiency compared to state-of-the-art symbolic or homotopic methods. }
}
@article{IMS2017,
title = {A robust and efficient method for solving point distance problems by homotopy},
author = {Imbach, R{\'e}mi and Mathis, Pascal and Schreck, Pascal},
journal = {Mathematical Programming: Series A and B},
volume = {163},
number = {1-2},
pages = {115--144},
year = {2017},
publisher = {Springer-Verlag Berlin, Heidelberg},
url = {http://dx.doi.org/10.1007/s10107-016-1058-7}
}
@techreport{Imbach2016c,
title = {{A Subdivision Solver for Systems of Large Dense Polynomials}},
author = {Imbach, R{\'e}mi},
url = {https://hal.inria.fr/hal-01293526},
type = {Technical Report},
number = {RT-0476},
pages = {13},
institution = {{INRIA Nancy}},
year = {2016},
month = mar,
keywords = { Large Dense Polynomials ; Real Solutions ; Interval Arithmetic ; Subdivision ; Adaptive Multi-Precision},
pdf = {https://hal.inria.fr/hal-01293526/file/RT-476.pdf},
hal_id = {hal-01293526},
hal_version = {v2}
}
@inproceedings{IMP16b,
title = {Numeric and Certified Isolation of the Singularities of the Projection of a Smooth Space Curve},
author = {Imbach, R{\'e}mi
and Moroz, Guillaume
and Pouget, Marc},
editor = {Kotsireas, Ilias S.
and Rump, Siegfried M.
and Yap, Chee K.},
booktitle = {Mathematical Aspects of Computer and Information Sciences: 6th International Conference, MACIS 2015, Berlin, Germany, November 11-13, 2015, Revised Selected Papers},
year = {2016},
publisher = {Springer International Publishing},
address = {Cham},
pages = {78--92},
isbn = {978-3-319-32859-1},
doi = {10.1007/978-3-319-32859-1_6},
url = {http://dx.doi.org/10.1007/978-3-319-32859-1_6}
}
@article{ISM2014,
title = {Leading a continuation method by geometry for solving geometric constraints},
author = {Imbach, R\'{e}mi and Schreck, Pascal and Mathis, Pascal},
journal = {Computer-Aided Design},
volume = {46},
pages = {138--147},
year = {2014},
publisher = {Elsevier},
pdf = {./articles/imbach2013leading.pdf}
}
@inproceedings{MSI2012,
title = {Decomposition of geometrical constraint systems with reparameterization},
author = {Mathis, Pascal and Schreck, Pascal and Imbach, R\'{e}mi},
booktitle = {Proceedings of the 27th Annual ACM Symposium on Applied Computing},
pages = {102--108},
year = {2012},
organization = {ACM},
url = {http://dl.acm.org/citation.cfm?id=2245298}
}
@inproceedings{IMS2011,
title = {Tracking method for reparametrized geometrical constraint systems},
author = {Imbach, R\'{e}mi and Mathis, Pascal and Schreck, Pascal},
booktitle = {2011 13th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing},
pages = {31--38},
year = {2011},
organization = {IEEE},
pdf = {./articles/imbach2011tracking.pdf}
}
@inproceedings{IMP2015,
title = {A Certified Numerical Approach to Describe the Topology of Projected Curves},
author = {Imbach, R\'{e}mi and Moroz, Guillaume and Pouget, Marc},
booktitle = {Journ\'{e}es de l'Association Fran\c{c}aise d'Informatique Graphique},
year = {2015},
pdf = {./articles/imbach2015certified.pdf}
}
@inproceedings{IMP2012,
title = {Une approche par d\'{e}composition et reparam\'{e}trisation de syst\`{e}mes de contraintes g\'{e}om\'{e}triques},
author = {Imbach, R\'{e}mi and Mathis, Pascal and Schreck, Pascal},
booktitle = {Journ\'{e}es du Groupe de Travail en Mod\'{e}lisation G\'{e}om\'{e}trique},
year = {2012},
pdf = {./articles/imbach2012approche.pdf}
}
@phdthesis{imbach2013,
title = {R{\'e}solution de contraintes g{\'e}om{\'e}triques en guidant une m{\'e}thode homotopique par la g{\'e}om{\'e}trie},
author = {Imbach, R{\'e}mi},
year = {2013},
school = {Universit\'{e} de Strasbourg},
pdf = {./articles/imbach_remi_2013_ED269.pdf}
}
@techreport{IPY2018techrep,
title = {{Implementation of a Near-Optimal Complex Root Clustering Algorithm}},
author = {Imbach, R{\'e}mi and Pan, Victor Y. and Yap, Chee},
url = {https://hal.archives-ouvertes.fr/hal-01822137},
type = {Research Report},
institution = {{TU Kaiserslautern ; City University of New York ; Courant Institute of Mathematical Sciences, New York University}},
year = {2018},
month = jun,
pdf = {https://hal.archives-ouvertes.fr/hal-01822137/file/imbach_pan_yap.pdf},
hal_id = {hal-01822137},
hal_version = {v1}
}
This file was generated by bibtex2html 1.98.