Date of Award


Degree Type


Degree Name

Master of Science


Computer Science


Eric Schost


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.



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.