| Title Benchmarking and extension of fast linear algebra algorithms. |
Version française
|
Location
INRIA, Project
CAFÉ
BP 93, 06902 France
Information
Description
The Café project has developped or implemented recent asymptotically
fast algorithms for exact linear algebra [1,2,3]. For example, there are now
6 different algorithms for computing the determinants of matrices of
polynomials or the exact solutions of linear systems. Our first experimental
results indicate that choosing the appropriate algorithm to use on a given
matrix depends on several parameters, including the size of the matrix
but also the type of the coefficients of the polynomial entries (integers,
rational numbers, elements of algebraic numbers fields or finite fields),
and probably also the distribution of the degrees inside the matrix.
We therefore need a careful and exhaustive benchmark in order to determine
a strategy for automatically selecting the most appropriate algorithm in
each case. This study should also help understand the practical behavior
of those algorithms and eventually to refine and improve them.
Finally, we are also interested in extending those algorithms
to compute related quantities in linear algebra such as resultants
or cyclic vectors and/or to implement some of them on a distributed
platform.
[1] J.Abbott, M.Bronstein & T.Mulders, Fast
Deterministic Computation of Determinants of Dense Matrices , Proceedings
of ISSAC'99, ACM Press, 197-204 (1999).
[2] T.Mulders & A.Storjohann, Rational
Solutions of Singular Linear Systems , Proceedings of ISSAC'2000, ACM
Press, 242-249 (2000).
[3] T.Mulders & A.Storjohann, Triangular
Factorization of Polynomial Matrices, ISSAC'2000 Poster.
Goals
A first objective is to develop a large and varied collection of
test examples in order to gain enough data to develop a strategy for
selecting the most appropriate algorithm for a given matrix.
Further objectives, as time permits, will be to extend selected
algorithms to compute resultants and cyclic vectors (linear dependencies)
as well as to write a distributed implementation on top of the
high--level 
communication library.
Tools
Unix workstation, language Aldor, libraries 
and .
Duration
3 - 4 months, possible prolongation as a doctoral thesis if desired.