On the complexity of the Lickteig–Roy subresultant algorithm
1
CNRS (LIX, UMR 7161), Laboratoire d'informatique de l'École polytechnique, Campus de l'École polytechnique, 1, rue Honoré d'Estienne d'Orves, Bâtiment Alan Turing, CS35003, 91120 Palaiseau, France
|
Publication type: Journal Article
Publication date: 2019-05-01
scimago Q2
wos Q2
SJR: 0.533
CiteScore: 2.2
Impact factor: 1.1
ISSN: 07477171, 1095855X
Computational Mathematics
Algebra and Number Theory
Abstract
In their 1996 article, Lickteig and Roy introduced a fast “divide and conquer” variant of the subresultant algorithm which avoids coefficient growth in defective cases. The present article concerns the complexity analysis of their algorithm over effective rings endowed with the partially defined division routine. We achieve essentially the same kind of complexity bound as over effective fields. As a consequence we obtain new convenient complexity bounds for gcds, especially when coefficients are in abstract polynomial rings where evaluation/interpolation schemes are not supposed to be available.
Found
Nothing found, try to update filter.
Found
Nothing found, try to update filter.
Top-30
Journals
|
1
2
3
4
5
6
|
|
|
Journal of Complexity
6 publications, 40%
|
|
|
Journal of Symbolic Computation
2 publications, 13.33%
|
|
|
ACM Communications in Computer Algebra
1 publication, 6.67%
|
|
|
Applicable Algebra in Engineering, Communications and Computing
1 publication, 6.67%
|
|
|
Foundations of Computational Mathematics
1 publication, 6.67%
|
|
|
Linear Algebra and Its Applications
1 publication, 6.67%
|
|
|
Lecture Notes in Computer Science
1 publication, 6.67%
|
|
|
1
2
3
4
5
6
|
Publishers
|
1
2
3
4
5
6
7
8
9
|
|
|
Elsevier
9 publications, 60%
|
|
|
Association for Computing Machinery (ACM)
3 publications, 20%
|
|
|
Springer Nature
3 publications, 20%
|
|
|
1
2
3
4
5
6
7
8
9
|
- We do not take into account publications without a DOI.
- Statistics recalculated weekly.
Are you a researcher?
Create a profile to get free access to personal recommendations for colleagues and new articles.
Metrics
15
Total citations:
15
Citations from 2024:
3
(20%)
Cite this
GOST |
RIS |
BibTex
Cite this
GOST
Copy
Lecerf G. On the complexity of the Lickteig–Roy subresultant algorithm // Journal of Symbolic Computation. 2019. Vol. 92. pp. 243-268.
GOST all authors (up to 50)
Copy
Lecerf G. On the complexity of the Lickteig–Roy subresultant algorithm // Journal of Symbolic Computation. 2019. Vol. 92. pp. 243-268.
Cite this
RIS
Copy
TY - JOUR
DO - 10.1016/j.jsc.2018.04.017
UR - https://doi.org/10.1016/j.jsc.2018.04.017
TI - On the complexity of the Lickteig–Roy subresultant algorithm
T2 - Journal of Symbolic Computation
AU - Lecerf, Grégoire
PY - 2019
DA - 2019/05/01
PB - Elsevier
SP - 243-268
VL - 92
SN - 0747-7171
SN - 1095-855X
ER -
Cite this
BibTex (up to 50 authors)
Copy
@article{2019_Lecerf,
author = {Grégoire Lecerf},
title = {On the complexity of the Lickteig–Roy subresultant algorithm},
journal = {Journal of Symbolic Computation},
year = {2019},
volume = {92},
publisher = {Elsevier},
month = {may},
url = {https://doi.org/10.1016/j.jsc.2018.04.017},
pages = {243--268},
doi = {10.1016/j.jsc.2018.04.017}
}