Department of Mathematical Sciences

Permanent URI for this community

https://scholar.sun.ac.za/handle/10019.1/223

Browse

Browsing Department of Mathematical Sciences by browse.metadata.advisor "Basson, Dirk"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Massivelly parallel modular algorithms for the image of rational maps
    (Stellenbosch : Stellenbosch University, 2024-03) Rakotoarisoa, Hobihasina Patrick; Basson, Dirk; Bohm, Janko; Marais, Magdaleen; Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences.
    ENGLISH ABSTRACT: Modular methods are a tool which can be applied in computer algebra to signifi‑ cantly improve the performance of algorithms in characteristic 0 by addressing the problem of intermediate coefficient growth. Computations are done simul‑ taneously over multiple finite fields by reducing the input data, applying the algorithm under consideration in positive characteristic, and then lifting the modular results to the rationals via Chinese remaindering and the Farey map. Even in the existence of bad primes, error tolerance of this process ensures that for a sufficiently large set of good primes the approach terminates with the cor‑ rect answer. The method is clearly parallel and has the potential to scale across multiple computers. It has been applied for various use cases, for example, for the computation of Gröbner bases. In this thesis, we provide a generic modular approach which is applicable to polynomial data structures arising from com‑ mutative algebra and algebraic geometry, such as modules, varieties, and ratio‑ nal maps. Moreover, we develop a massively parallel framework for modular computations, which we model in terms of Petri nets. We give an implementa‑ tion relying on the SINGULAR/GPI‑SPACE framework.