Homotopy techniques for multiplication modulo triangular sets
The paper contains significant contributions towards the estimation of the cost of polynomial multiplication modulo a triangular set {\textbf{T}} whose elements are monic with respect to the leading variables and reduced modulo the ideal generated by their predecessors. The polynomials are supposed to have coefficients in a commutative ring. The approach, inspired by previous work of \textit{X. Li}, \textit{M. Moreno Maza} and \textit{É. Schost} [``Fast arithmetic for triangular sets: from theory to practice, in: ISSAC 2007. Proceedings of the 32nd international symposium on symbolic and algebraic computation. New York, NY: Association for Computing Machinery (ACM). 269--276 (2007; Zbl 1190.68093)], relies on the use of evaluation and interpolation techniques. In order to ensure that these methods work, the original triangular set is replaced by a new one, defined over \(RY\) (where \(Y\) is a new variable) and having roots in the power series ring. Returning from the deformed traingular set is conceptually easy, the crux of the matter is a sharp estimation on the arithmetical work required in this excursion. The main novelty is a study of precision-related issues concerning the power series computations and how they relate to the monomial support of {\textbf{T}}. The outcome of the study is a general bound for two functions controlling the complexity of the algorithm introduced here for multiplication modulo a triangular set. The bound can be improved in the case when the polynomials in {\textbf{T}} are sparse or have low total degree by inspecting the vertices of a certain simplex. This results in a quasi-linear time complexity for several important families of polynomials. By means of examples it is also shown that small changes in the assumptions can induce large overheads. The multiplication algorithm studied in the paper under review is employed to perform addition of algebraic numbers in small characteristics. A comparison with the well-known resultant-based approach to this problem confirms the timings predicted by the complexity analysis.
- A simple and fast algorithm for computing exponentials of power series
- Advances in Cryptology - EUROCRYPT 2004
- Algorithmic Number Theory
- Algorithms in invariant theory
- Calcul de résolvantes avec les modules de Cauchy
- Computation of the decomposition group of a triangular ideal
- Evaluating Polynomials at Fixed Sets of Points
- EVALUATION PROPERTIES OF SYMMETRIC POLYNOMIALS
- Fast arithmetic for triangular sets: from theory to practice
- Fast computation of special resultants
- Faster integer multiplication
- scientific article; zbMATH DE number 4128945 (Why is no real title available?)
- scientific article; zbMATH DE number 16654 (Why is no real title available?)
- scientific article; zbMATH DE number 3533996 (Why is no real title available?)
- scientific article; zbMATH DE number 1253989 (Why is no real title available?)
- scientific article; zbMATH DE number 2151224 (Why is no real title available?)
- scientific article; zbMATH DE number 2151230 (Why is no real title available?)
- Lifting techniques for triangular decompositions
- Modern computer algebra
- Multivariate power series multiplication
- Newton's method and FFT trading
- On computer-assisted classification of coupled integrable equations
- On fast multiplication of polynomials over arbitrary algebras
- On the complexity of the D5 principle
- Simple multivariate polynomial multiplication
- The p-adic valuation of k-central binomial coefficients
- The Magma algebra system. I: The user language
- The truncated fourier transform and applications
- Using Galois ideals for computing relative resolvents
- Fast arithmetic for triangular sets: from theory to practice
- Efficient arithmetic in successive algebraic extension fields using symmetries
- Computing in degree \(2^k\)-extensions of finite fields of odd characteristic
- Accelerated tower arithmetic
- On the complexity of the D5 principle
- Modular composition modulo triangular sets and applications
- Relaxed Hensel lifting of triangular sets
- Fast arithmetic for triangular sets: from theory to practice
This page was built for publication: Homotopy techniques for multiplication modulo triangular sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q651881)
