Accelerated tower arithmetic
1
CNRS (UMR 7161, LIX), 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-12-01
scimago Q1
wos Q1
SJR: 0.850
CiteScore: 3.5
Impact factor: 1.8
ISSN: 0885064X, 10902708
General Mathematics
Statistics and Probability
Applied Mathematics
Control and Optimization
Numerical Analysis
Algebra and Number Theory
Abstract
Nowadays, asymptotically fast algorithms are widely used in computer algebra for computations in towers of algebraic field extensions of small height. Yet it is still unknown how to reach softly linear time for products and inversions in towers of arbitrary height. In this paper we design the first algorithm for general ground fields with a complexity exponent that can be made arbitrarily close to one from the asymptotic point of view. We deduce new faster algorithms for changes of tower representations, including the computation of primitive element representations in subquadratic time.
Found
Nothing found, try to update filter.
Found
Nothing found, try to update filter.
Top-30
Journals
|
1
2
|
|
|
Applicable Algebra in Engineering, Communications and Computing
2 publications, 18.18%
|
|
|
Journal of Complexity
2 publications, 18.18%
|
|
|
Lecture Notes in Computer Science
2 publications, 18.18%
|
|
|
Computational Complexity
1 publication, 9.09%
|
|
|
Foundations of Computational Mathematics
1 publication, 9.09%
|
|
|
Research in Number Theory
1 publication, 9.09%
|
|
|
Journal of the ACM
1 publication, 9.09%
|
|
|
1
2
|
Publishers
|
1
2
3
4
5
6
7
|
|
|
Springer Nature
7 publications, 63.64%
|
|
|
Elsevier
2 publications, 18.18%
|
|
|
Association for Computing Machinery (ACM)
1 publication, 9.09%
|
|
|
1
2
3
4
5
6
7
|
- 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
11
Total citations:
11
Citations from 2024:
2
(18.18%)
The most citing journal
Citations in journal:
2
Cite this
GOST |
RIS |
BibTex
Cite this
RIS
Copy
TY - JOUR
DO - 10.1016/j.jco.2019.03.002
UR - https://doi.org/10.1016/j.jco.2019.03.002
TI - Accelerated tower arithmetic
T2 - Journal of Complexity
AU - VAN DER HOEVEN, JORIS
AU - Lecerf, Grégoire
PY - 2019
DA - 2019/12/01
PB - Elsevier
SP - 101402
VL - 55
SN - 0885-064X
SN - 1090-2708
ER -
Cite this
BibTex (up to 50 authors)
Copy
@article{2019_VAN DER HOEVEN,
author = {JORIS VAN DER HOEVEN and Grégoire Lecerf},
title = {Accelerated tower arithmetic},
journal = {Journal of Complexity},
year = {2019},
volume = {55},
publisher = {Elsevier},
month = {dec},
url = {https://doi.org/10.1016/j.jco.2019.03.002},
pages = {101402},
doi = {10.1016/j.jco.2019.03.002}
}