@article{BoPoQu16,
title = "Computer algebra methods for the stability analysis of differential systems with commensurate time-delays",
journal = "IFAC-PapersOnLine",
volume = "49",
number = "10",
pages = "194 - 199",
year = "2016",
note = "",
issn = "2405-8963",
doi = "http://dx.doi.org/10.1016/j.ifacol.2016.07.528",
url = "http://www.sciencedirect.com/science/article/pii/S240589631630742X",
author = "Yacine Bouzidi and Adrien Poteaux and Alban Quadrat",
}
@inproceedings{PoRy15,
author = {Poteaux, Adrien and Rybowicz, Marc},
title = {Improving Complexity Bounds for the Computation of Puiseux Series over Finite Fields},
booktitle = {Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation},
series = {ISSAC '15},
year = {2015},
isbn = {978-1-4503-3435-8},
location = {Bath, United Kingdom},
pages = {299--306},
numpages = {8},
url = {http://doi.acm.org/10.1145/2755996.2756650},
doi = {10.1145/2755996.2756650},
acmid = {2756650},
publisher = {ACM},
address = {New York, NY, USA},
keywords = {algebraic curves, algebraic functions, complexity, finite fields, genus, puiseux series},
}
@incollection{BKLPPU14,
year={2014},
isbn={978-3-319-10514-7},
booktitle={Computer Algebra in Scientific Computing},
volume={8660},
series={Lecture Notes in Computer Science},
editor={Gerdt, VladimirP. and Koepf, Wolfram and Seiler, WernerM. and Vorozhtsov, EvgeniiV.},
doi={10.1007/978-3-319-10515-4_3},
title={An Algorithm for Converting Nonlinear Differential Equations to Integral Equations with an Application to Parameter Estimation from Noisy Data},
url={http://dx.doi.org/10.1007/978-3-319-10515-4_3},
publisher={Springer International Publishing},
author={Boulier, François and Korporal, Anja and Lemaire, François and Perruquetti, Wilfrid and Poteaux, Adrien and Ushirobira, Rosane},
pages={28-43},
language={English}
}
@article{PoSc13a,
year={2013},
issn={1016-3328},
journal={computational complexity},
doi={10.1007/s00037-013-0063-y},
title={Modular Composition Modulo Triangular Sets and Applications},
url={http://dx.doi.org/10.1007/s00037-013-0063-y},
publisher={SP Birkhäuser Verlag Basel},
keywords={Triangular set; modular composition; power projection; finite fields; complexity; 68W30},
author={Poteaux, Adrien and Schost, \'Eric},
pages={1-54},
language={English},
abstract = "We generalize Kedlaya and Umans’ modular composition algorithm to the multivariate case. As a main application, we give fast algorithms for many operations involving triangular sets (over a finite field), such as modular multiplication, inversion, or change of order. For the first time, we are able to exhibit running times for these operations that are almost linear, without any overhead exponential in the number of variables. As a further application, we show that, from the complexity viewpoint, Charlap, Coley, and Robbins’ approach to elliptic curve point counting can be competitive with the better known approach due to Elkies."
}
@article{PoSc13b,
title = "On the complexity of computing with zero-dimensional triangular sets ",
journal = "Journal of Symbolic Computation ",
volume = "50",
number = "0",
pages = "110 - 138",
year = "2013",
note = "",
issn = "0747-7171",
doi = "10.1016/j.jsc.2012.05.008",
url = "http://www.sciencedirect.com/science/article/pii/S0747717112001083",
author = "Adrien Poteaux and \'Eric Schost",
keywords = "Triangular sets",
keywords = "Modular composition",
keywords = "Power projection",
keywords = "Change of order",
keywords = "Equiprojectable decomposition ",
abstract = "We study the complexity of some fundamental operations for triangular sets in dimension zero. Using Las Vegas algorithms, we prove that one can perform such operations as change of order, equiprojectable decomposition, or quasi-inverse computation with a cost that is essentially that of modular composition. Over an abstract field, this leads to a subquadratic cost (with respect to the degree of the underlying algebraic set). Over a finite field, in a boolean \{RAM\} model, we obtain a quasi-linear running time using Kedlaya and Umansʼ algorithm for modular composition. Conversely, we also show how to reduce the problem of modular composition to change of order for triangular sets, so that all these problems are essentially equivalent. Our algorithms are implemented in Maple; we present some experimental results. "
}
@article{PoRy12,
title = "Good reduction of Puiseux series and applications ",
journal = "Journal of Symbolic Computation ",
volume = "47",
number = "1",
pages = "32 - 63",
year = "2012",
note = "",
issn = "0747-7171",
doi = "10.1016/j.jsc.2011.08.008",
url = "http://www.sciencedirect.com/science/article/pii/S0747717111001209",
author = "Adrien Poteaux and Marc Rybowicz",
keywords = "Puiseux series",
keywords = "Algebraic functions",
keywords = "Finite fields",
keywords = "Symbolic–numeric algorithm ",
abstract = "We have designed a new symbolic–numeric strategy for computing efficiently and accurately floating point Puiseux series defined by a bivariate polynomial over an algebraic number field. In essence, computations modulo a well-chosen prime number p are used to obtain the exact information needed to guide floating point computations. In this paper, we detail the symbolic part of our algorithm. First of all, we study modular reduction of Puiseux series and give a good reduction criterion for ensuring that the information required by the numerical part is preserved. To establish our results, we introduce a simple modification of classical Newton polygons, that we call “generic Newton polygons”, which turns out to be very convenient. Finally, we estimate the size of good primes obtained with deterministic and probabilistic strategies. Some of these results were announced without proof at ISSAC’08. "
}
@article{PoRy11,
author = {Poteaux, Adrien and Rybowicz, Marc},
title = {Complexity bounds for the rational Newton-Puiseux algorithm over finite fields},
journal = {Applicable Algebra in Engineering, Communication and Computing},
publisher = {Springer Berlin / Heidelberg},
issn = {0938-1279},
keyword = {Computer Science},
pages = {187-217},
volume = {22},
issue = {3},
url = {http://dx.doi.org/10.1007/s00200-011-0144-6},
note = {10.1007/s00200-011-0144-6},
year = {2011},
abstract = "We carefully study the number of arithmetic operations required to compute rational Puiseux expansions of a bivariate polynomial F over a finite field. Our approach is based on the rational Newton-Puiseux algorithm introduced by D. Duval. In particular, we prove that coefficients of F may be significantly truncated and that certain complexity upper bounds may be expressed in terms of the output size. These preliminary results lead to a more efficient version of the algorithm with a complexity upper bound that improves previously published results. We also deduce consequences for the complexity of the computation of the genus of an algebraic curve defined over a finite field or an algebraic number field. Our results are practical since they are based on well established subalgorithms, such as fast multiplication of univariate polynomials with coefficients in a finite field."
}
@article{GaPo11,
title = "Computing monodromy via continuation methods on random Riemann surfaces ",
journal = "Theoretical Computer Science ",
volume = "412",
number = "16",
pages = "1492 - 1507",
year = "2011",
note = "Symbolic and Numerical Algorithms ",
issn = "0304-3975",
doi = "10.1016/j.tcs.2010.11.047",
url = "http://www.sciencedirect.com/science/article/pii/S0304397510006857",
author = "Andr\'e Galligo and Adrien Poteaux",
keywords = "Bivariate polynomial",
keywords = "Plane curve",
keywords = "Random Riemann surface",
keywords = "Absolute factorization",
keywords = "Algebraic geometry",
keywords = "Continuation methods",
keywords = "Monodromy",
keywords = "Symmetric group",
keywords = "Algorithms",
keywords = "Maple code ",
abstract = "We consider a Riemann surface X defined by a polynomial f ( x , y ) of degree d , whose coefficients are chosen randomly. Hence, we can suppose that X is smooth, that the discriminant δ ( x ) of f has d ( d − 1 ) simple roots, Δ , and that δ ( 0 ) ≠ 0 , i.e. the corresponding fiber has d distinct points { y 1 , … , y d } . When we lift a loop 0 ∈ γ ⊂ C − Δ by a continuation method, we get d paths in X connecting { y 1 , … , y d } , hence defining a permutation of that set. This is called monodromy. Here we present experimentations in Maple to get statistics on the distribution of transpositions corresponding to loops around each point of Δ . Multiplying families of “neighbor” transpositions, we construct permutations and the subgroups of the symmetric group they generate. This allows us to establish and study experimentally two conjectures on the distribution of these transpositions and on transitivity of the generated subgroups. Assuming that these two conjectures are true, we develop tools allowing fast probabilistic algorithms for absolute multivariate polynomial factorization, under the hypothesis that the factors behave like random polynomials whose coefficients follow uniform distributions. "
}
@InCollection{AiJuPo12,
author = {M. Aigner and B. J\"uttler and A. Poteaux},
title = {Approximate Implicitization of Space Curves},
booktitle = {Numerical and Symbolic Scientific Computing},
series = {Texts and Monographs in Symbolic Computation},
editor = {U. Langer and R. Corless and H. Hong and T. Ida and M. Kreuzer and B. Salvy and D. Wang and P. Paule},
publisher = {Springer Vienna},
pages = {1-19},
volume = {1},
doi = {10.1007/978-3-7091-0794-2_1},
year = {2012},
}
@article{SoJuPo10,
author = {Xinghua Song and Bert J\"uttler and Adrien Poteaux},
title = {Hierarchical Spline Approximation of the Signed Distance Function},
journal ={International Conference on Shape Modeling and Applications},
volume = {0},
isbn = {978-0-7695-4072-6},
year = {2010},
pages = {241-245},
doi = {http://doi.ieeecomputersociety.org/10.1109/SMI.2010.18},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
abstract = "We present a method to approximate the signed distance function of a smooth curve or surface by using polynomial splines over hierarchical T-meshes (PHT splines). In particular, we focus on closed parametric curves in the plane and implicitly defined surfaces in space."
}
@inproceedings{PoGa09,
author = {Galligo, Andr\'{e} and Poteaux, Adrien},
title = {Continuations and monodromy on random riemann surfaces},
booktitle = {SNC '09: Proceedings of the 2009 conference on Symbolic numeric computation},
year = {2009},
isbn = {978-1-60558-664-9},
pages = {115--124},
location = {Kyoto, Japan},
doi = {http://doi.acm.org/10.1145/1577190.1577210},
publisher = {ACM},
address = {New York, NY, USA},
abstract = {Our main motivation is to analyze and improve factorization algorithms for bivariate polynomials in C[x,y], which proceed by continuation methods.
We consider a Riemann surface X defined by a polynomial f(x,y) of degree d, whose coefficients are choosen randomly. Hence we can supose that X is smooth, that the discriminant δ(x) of f has d(d-1) simple roots, Δ, that δ(0) ≠ 0 i.e. the corresponding fiber has d distinct points {y1,...,yd}. When we lift a loop 0 ∈ γ ⊂ C - Δ by a continuation method, we get d paths in X connecting {y1,...,yd}, hence defining a permutation of that set. This is called monodromy.
Here we present experimentations in Maple to get statistics on the distribution of transpositions corresponding to the loops turning around each point of Δ. Multiplying families of "consecutive" transpositions, we construct permutations then subgroups of the symmetric group. This allows us to establish and study experimentally some conjectures on the distribution of these transpositions then on transitivity of the generated subgroups.
These results provide interesting insights on the structure of such Riemann surfaces (or their union) and eventually can be used to develop fast algorithms.}
}
@inproceedings{PoRy08,
author = {Poteaux, Adrien and Rybowicz, Marc},
title = {Good reduction of puiseux series and complexity of the Newton-Puiseux algorithm over finite fields},
booktitle = {ISSAC '08: Proceedings of the twenty-first international symposium on Symbolic and algebraic computation},
year = {2008},
isbn = {978-1-59593-904-3},
pages = {239--246},
location = {Linz/Hagenberg, Austria},
doi = {http://doi.acm.org/10.1145/1390768.1390802},
publisher = {ACM},
address = {New York, NY, USA},
abstract = "In [12], we sketched a numeric-symbolic method to compute Puiseux series with floating point coefficients. In this paper, we address the symbolic part of our algorithm. We study the reduction of Puiseux series coefficients modulo a prime ideal and prove a good reduction criterion sufficient to preserve the required information, namely Newton polygon trees. We introduce a convenient modification of Newton polygons that greatly simplifies proofs and statements of our results. Finally, we improve complexity bounds for Puiseux series calculations over finite fields, and estimate the bit-complexity of polygon tree computation."
}
@inproceedings{Po07,
author = {Poteaux, Adrien},
title = {Computing monodromy groups defined by plane algebraic curves},
booktitle = {SNC '07: Proceedings of the 2007 international workshop on Symbolic-numeric computation},
year = {2007},
isbn = {978-1-59593-744-5},
pages = {36--45},
location = {London, Ontario, Canada},
doi = {http://doi.acm.org/10.1145/1277500.1277509},
publisher = {ACM},
address = {New York, NY, USA},
abstract = "We present a symbolic-numeric method to compute the monodromy group of a plane algebraic curve viewed as a ramified covering space of the complex plane. Following the definition, our algorithm is based on analytic continuation of algebraic functions above paths in the complex plane. Our contribution is three-fold : first of all, we show how to use a minimum spanning tree to minimize the length of paths ; then, we propose a strategy that gives a good compromise between the number of steps and the truncation orders of Puiseux expansions, obtaining for the first time a complexity result about the number of steps; finally, we present an efficient numerical-modular algorithm to compute Puiseux expansions above critical points,which is a non trivial task."
}
@phdthesis{Po08,
author = {Adrien Poteaux},
title = {Calcul de d\'eveloppements de Puiseux et application au calcul du groupe de monodrmie d'une courbe alg\'ebrique plane},
school = {Universit\'e de Limoges},
year = {2008},
}
%the abstract is in these proceedings.
@article{posterPo07,
author = {Giesbrecht, Mark W. and Kotsireas, Ilias and Lobo, Austin},
title = {ISSAC 2007 poster abstracts},
journal = {ACM Commun. Comput. Algebra},
volume = {41},
issue = {1-2},
month = {March},
year = {2007},
issn = {1932-2240},
pages = {38--72},
numpages = {35},
url = {http://doi.acm.org/10.1145/1296772.1296775},
doi = {http://doi.acm.org/10.1145/1296772.1296775},
acmid = {1296775},
publisher = {ACM},
address = {New York, NY, USA},
}
@article{DaMaPoSc10,
author = {Dahan, Xavier and Maza, Marc Moreno and Schost, \'{E}ric and Poteaux, Adrien},
title = {Almost linear time operations with triangular sets},
journal = {ACM Commun. Comput. Algebra},
issue_date = {September/December 2010},
volume = {44},
issue = {3/4},
month = {January},
year = {2011},
issn = {1932-2240},
pages = {103--104},
numpages = {2},
url = {http://doi.acm.org/10.1145/1940475.1940486},
doi = {http://doi.acm.org/10.1145/1940475.1940486},
acmid = {1940486},
publisher = {ACM},
address = {New York, NY, USA},
}
@article{IsPo11,
author = {Islam, Md. Nazrul and Poteaux, A.},
title = {Connectivity queries on curves in Rn},
journal = {ACM Commun. Comput. Algebra},
issue_date = {March/June 2011},
volume = {45},
issue = {1/2},
month = {July},
year = {2011},
issn = {1932-2240},
pages = {117--118},
numpages = {2},
url = {http://doi.acm.org/10.1145/2016567.2016584},
doi = {http://doi.acm.org/10.1145/2016567.2016584},
acmid = {2016584},
publisher = {ACM},
address = {New York, NY, USA},
}