Date of Award
Master of Science
Triangular representations are a versatile tool to manipulate systems of polynomial equations; however, many basic complexity questions are still open with respect to such objects. This matter of fact appears clearly with multiplication modulo triangu lar sets: it plays an essential part in algorithms for solving polynomial systems, but the cost of this operation remains difficult to estimate precisely.
This thesis studies the complexity of this operation. 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. Ap plications are given notably to addition of algebraic numbers in small characteristic.
Chowdhury, Muhammad Foizul Islam, "Homotopy techniques for multiplication modulo triangular sets" (2009). Digitized Theses. 4148.