Adaptive Triangular System Solving

Abstract

Large-scale applications and software systems are
getting increasingly complex. To deal with this complexity, those
systems must manage themselves in accordance with high-level guidance
from humans.  Adaptive and hybrid algorithms enable this
self-management of resources and structured inputs.

In this talk, we first propose a classification of the different
notions of adaptivity. For us, an algorithm is adaptive (or  a
poly-algorithm) when there is a choice at a high level between at
least two distinct algorithms, each of which could  solve the same
problem.  The  choice is strategic, not  tactical. It is motivated by
an increase  of the performance of the execution, depending on both
input/output data and computing resources.  

Then we propose a new adaptive algorithm for the exact simultaneous
resolution of several triangular systems over finite fields.  The
resolution of such systems is e.g. one of the two main operations in block
Gaussian elimination.  For solving triangular systems over finite
fields, the block algorithm reduces to matrix multiplication and
achieves the best known algebraic complexity.  Exact matrix
multiplication, together with matrix factorizations, over finite
fields can now be performed at the speed of the highly optimized
numerical BLAS routines. This has been established by the FFLAS and
FFPACK libraries.  In this talk we propose 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.  The adaptive
sequential algorithm is not the best parallel algorithm since its
recursion induces a dependancy. A better parallel algorithm would be
to first invert the matrix and then to multiply this inverse by the
right hand side. Unfortunately the latter requires more total
operations than the adaptive algorithm. We thus propose 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 for the
automatic adaptation of algorithms using recursive cascading.