Date of Award
2009
Degree Type
Thesis
Degree Name
Master of Science
Program
Computer Science
Supervisor
Eric Schost
Abstract
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.
Recommended Citation
Chowdhury, Muhammad Foizul Islam, "Homotopy techniques for multiplication modulo triangular sets" (2009). Digitized Theses. 4148.
https://ir.lib.uwo.ca/digitizedtheses/4148