Adaptive triangular system solving

Jean-Guillaume Dumas (1) , Clément Pernet (1) , Jean-Louis Roch (2)

1 LMC - IMAG - Laboratoire de Modélisation et Calcul
2 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation

We propose a new adaptive algorithm for the exact simultaneous resolution of several triangular systems over finite fields: it is composed of several practicable variants solving these systems (a pure recursive version, a reduction to the numerical dtrsm routine and a delaying of the modulus operation). Then a cascading scheme is proposed to merge these variants into an adaptive sequential algorithm. We then propose a parallelization of this resolution by a coupling of the sequential algorithm and of the parallel one in order to get the best performances on any number of processors. The resulting cascading is then an adaptation to resources. This shows that the same process has been used both for adaptation to data and to resources. We thus propose a generic framework enabling automatic adaptation of algorithms using recursive cascading.

Domaines: Calcul formel [cs.SC]

Jean-Guillaume Dumas, Clément Pernet, Jean-Louis Roch. Adaptive triangular system solving. Challenges in Symbolic Computation Software - Dagstuhl Seminar 06271, Jul 2006, Dagstuhl, Germany. pp.770. ⟨hal-00318543⟩