License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06271.3
URN: urn:nbn:de:0030-drops-7704
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2006/770/
|
Go to the corresponding Portal |
Dumas, Jean-Guillaume ;
Pernet, Clément ;
Roch, Jean-Louis
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.
BibTeX - Entry
@InProceedings{dumas_et_al:DagSemProc.06271.3,
author = {Dumas, Jean-Guillaume and Pernet, Cl\'{e}ment and Roch, Jean-Louis},
title = {{Adaptive Triangular System Solving}},
booktitle = {Challenges in Symbolic Computation Software},
pages = {1--18},
series = {Dagstuhl Seminar Proceedings (DagSemProc)},
ISSN = {1862-4405},
year = {2006},
volume = {6271},
editor = {Wolfram Decker and Mike Dewar and Erich Kaltofen and Stephen Watt},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2006/770},
URN = {urn:nbn:de:0030-drops-7704},
doi = {10.4230/DagSemProc.06271.3},
annote = {Keywords: Adaptive and hybrid algorithms; triangular system solving; parallel and sequential degenerations}
}
|
Keywords: |
|
Adaptive and hybrid algorithms; triangular system solving; parallel and sequential degenerations |
|
Collection: |
|
06271 - Challenges in Symbolic Computation Software |
|
Issue Date: |
|
2006 |
|
Date of publication: |
|
25.10.2006 |
