Thu, 13 Jun 2002
14:00 -
15:00
Rutherford Appleton Laboratory, nr Didcot
Some complexity considerations in sparse LU factorization
Prof Arne S. Drud
(ARKI Consulting and Development)
Abstract
The talk will discuss unsymmetric sparse LU factorization based on
the Markowitz pivot selection criterium. The key question for the
author is the following: Is it possible to implement a sparse
factorization where the overhead is limited to a constant times
the actual numerical work? In other words, can the work be bounded
by o(sum(k, M(k)), where M(k) is the Markowitz count in pivot k.
The answer is probably NO, but how close can we get? We will give
several bad examples for traditional methods and suggest alternative
methods / data structure both for pivot selection and for the sparse
update operations.