Homotopy techniques for multiplication modulo triangular sets (Q651881)

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 \(R[[Y]]\) (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.