Computational Algebra Seminar

Sparse linear systems are frequently encoutered in different areas of computer algebra, numerical analysis, and physics. Dedicated algorithms exist for dealing with such systems, taking advantage of their tiny number of non-zero coefficients. We will concentrate on the systems occuring in computer algebra, defined over (either large or small) finite fields. We will address the structured gaussian elimination and the Wiedemann algorithm, as well as the Lanczos method (much more briefly). We will also try to discuss the recent ``block'' generalizations of the two latter algorithms, which permit a partial distribution of the computations.