Research Projects

Project 8 (Lextriangular in Positive Dimension in AXIOM)   A first goal is to generalize the lextriangular algorithm such it can take as input the lexicographical Gröbner basis of any polynomial ideal, without restriction to the dimension zero case. A second goal is to implement this new algorithm in AXIOM where the dimension zero case is already available.

Project 9 (From characteristic sets to Gröbner bases)   In [ALM99] the authors show how a characteristic set C (that is a particular kind of triangular set) of a prime ideal $\cal {P}$ of $\bf k$[x₁,..., x_n] can be obtained in $\cal {O}$(1) computing time from a lexicographical Gröbner basis G of $\cal {P}$. The only known algorithm for reconstructing G from C is essentially the computation of a Gröbner basis of the saturated ideal of C. This process appears to be very expensive. I beleieve that, at least in dimension zero, a much cheaper algorithm exists. The goal of this project is to discover it! Tests and implementation could be realized in AXIOM or MAPLE.

Project 10 (Task Management for TRIADE in MAPLE)   The top level procedure of the TRIADE algorithm is a task manager, which is meant to be implemented on a distributed environment. Indeed, this procedure is a branch-and-cut algorithm. This means that a running task T₁ may be aborted before it is completed because the completion of another running T₂ shows that T₁ is superfluous. Therefore, performing {T₁, T₂} in a distributed environment will require less resources (time and space) than in a sequential one starting with T₁. The key point for a sequential implementation is to develop strategies that lead to perform T₂ before T₁.

The current implementations (AXIOM, ALDOR, MAPLE) of the TRIADE algorithm are all sequential and the goal of this project is to improve the existing strategies for avoiding superfluous tasks. The work will be on two fronts: algorithmic and experimental. On the algorithmic front, a better understanding of the task generation will be needed. From there, one hopes to refine the existing strategies. On the experimental front, one will have to measure the concrete effect of the various strategies. The experimentations will be conducted with the MAPLE version of TRIADE.

Project 11 (Distributed Computation with TRIADE in ALDOR)   The main concern is the same as for Project 10. However, the experimental front is emphasized. Indeed, experimentations will be conducted with the ALDOR version of TRIADE together with the $\Pi^{{{it}}}_{{}}$ library.

Project 12 (El Kahoui Gap Structure Theorem)   This project is mathematically deeper and would require little implementation. However, it will require a very good understanding of the notions developed in the course. Based on the paper [El 03] by M. El Kahoui, the aim is to answer the following questions

• Does the Gap Structure Theorem of M. El Kahoui lead to a practical subresultant algorithm over non-integral domains? products of fields?
• When two polynomials have a quasi-monic gcd over a product of fields can we effectively compute such gcd without splitting?

Answering these questions will probably lead to a research article.