2009/01/23 by Alin Bostan, Bostan, Alin, Muhammad Chowdhury +5
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #I.1.2 #Symbolic Computation (cs.SC) #cs.DS #cs.SC
paper · pdf · doi:10.48550/arxiv.0901.3657
arxiv created 2009/01/23 · arxiv updated 2009/12/01
We study the cost of multiplication modulo triangular families of polynomials. Following previous work by Li, Moreno Maza and Schost, we propose an algorithm that relies on homotopy and fast evaluation-interpolation techniques. We obtain a quasi-linear time complexity for substantial families of examples, for which no such result was known before. Applications are given to notably addition of algebraic numbers in small characteristic.